Попалась на днях одна симпатичная вероятностная задача. В исходной постановке, она достаточно несложная, но более общий вопрос на эту тему для меня пока что открыт
( Read more... )
Что значит "в какой-то момент"? "Существует шаг, при котором сумма равна ровно n"? То есть когда оказалось после очередного (неважно, какого по номеру) броска сумма n, то мы останавливаемся?
А под "исходной постановкой, в которой она достаточно несложная", вы имели ввиду монетку? Как решать в случае в всего двух возможных значений, я вроде понимаю.
Я запустилъ игру два миллiона разъ, записывая, сколько разъ были найдены разныя значенiя отъ 1 до 100, и нашелъ, что вѣроятность выигрыша какъ функцiя n дается слѣдующимъ графикомъ.
( ... )
Там сами точные значения можно найти явно, но вот как они при этом будут упорядочены - это загадка. Там, где линия на графике примерно постоянная, имеет место некий странный колеблющийся процесс.
Меня удивило то, что достаточно сложное на вид явление возникло на такой просто формулируемой основе.
Да, похоже на то, что здесь природа сравнения сродни тригонометрической. Хотя, если говорить о сравнении синусов, то эта задача сводится к нахождению приближённых значений для числа п, то есть её можно считать принципиально решённой.
Рассмотрим к - гранный кубик. Обозначим f(n) ту самую вероятность выигрыша. f задается рекурсивной формулой:
f(0) = 1 ; f(x<0) = 0
f(n) = ( f(n-1) + f(n-2) + ... + f(n-k) ) /k
Для k = 2
2f(n) - f(n-1) - f(n-2) = 0
Изестно, что все выражения подобного рода можно расчитать как f(n) = a1*x1^n + b1*x2^n + ... где a1 a2 ... - коэффициенты, расчитываемые по начальному условию f(0) = 1, f(<0) = 0
( ... )
Спасибо за изложенные соображения. Насчёт предельного значения я не думал, но оно, похоже, и в самом деле равно 2/(k+1).
То, что именно при n=k получается максимум, доказывается прямо, при помощи неравенств. Формула для значения максимальной вероятности получается по индукции.
Рассматривается случайное блуждание на целой полупрямой, выпущенное из нуля, с переходными вероятностями, равномерно распределенными от 1 до d, и спрашивается о вероятности посетить точку n (обозначим ее p_n). Эти вероятности удовлетворяют следующим рекуррентным соотношениям, выражающими исходную вероятность через взвешенную сумму таковых вероятностей после первого шага:
Да, я примерно так же рассуждал. Из рекуррентной формулы понятно, что p(1) < ... < p(6), а дальше каждое следующее число есть среднее от 6 предыдущих, и по индукции понятно, что оно строго меньше p(6). Но в целом картина упорядочения не вполне ясна. Скажем, что стоит за тем фактом, что p(7) расположено между p(3) и p(4)?
Comments 24
Reply
Reply
Как решать в случае в всего двух возможных значений, я вроде понимаю.
Reply
Reply
( ... )
Reply
Меня удивило то, что достаточно сложное на вид явление возникло на такой просто формулируемой основе.
Reply
Reply
Reply
Reply
Reply
Обозначим f(n) ту самую вероятность выигрыша.
f задается рекурсивной формулой:
f(0) = 1 ; f(x<0) = 0
f(n) = ( f(n-1) + f(n-2) + ... + f(n-k) ) /k
Для k = 2
2f(n) - f(n-1) - f(n-2) = 0
Изестно, что все выражения подобного рода можно расчитать как f(n) = a1*x1^n + b1*x2^n + ... где
a1 a2 ... - коэффициенты, расчитываемые по начальному условию f(0) = 1, f(<0) = 0 ( ... )
Reply
Reply
То, что именно при n=k получается максимум, доказывается прямо, при помощи неравенств. Формула для значения максимальной вероятности получается по индукции.
Reply
p_1 = 1/d,
p_2 = 1/d + p_1/d,
p_3 = 1/d + p_1/d + p_2/d,
...
p_d = 1/d + p_1/d + p_2/d + ... p_{d-1}/d,
а для всех n>d
p_n = (p_{n-1} + ... p_{n-d})/d,
откуда видно, что p_n максимально при n=d.
Reply
Reply
Leave a comment