Какое ожидаемое количество раз вы должны бросить кубик, пока каждая сторона не появится 3 раза?
Этот вопрос был задан в начальной школе в Новой Зеландии, и он был решен с помощью моделирования. Каково аналитическое решение этой проблемы?
Какое ожидаемое количество раз вы должны бросить кубик, пока каждая сторона не появится 3 раза?
Этот вопрос был задан в начальной школе в Новой Зеландии, и он был решен с помощью моделирования. Каково аналитическое решение этой проблемы?
Ответы:
Предположим, что все стороны с имеют равные шансы. Давайте обобщим и найдем ожидаемое количество бросков, необходимое для того, чтобы сторона 1 появилась n 1 раз, сторона 2 появилась n 2 раза, ..., а сторона d появилась n d раз. Поскольку идентичности сторон не имеют значения (все они имеют равные шансы), описание этой цели может быть сжато: предположим, что i 0 сторон не должно появляться вообще, i 1 сторон должно появляться только один раз, ... и я пd=6 1 n1 2 n2 d nd i0 i1 in из сторон должны появляться раз. Пусть i = ( i 0 , i 1 , … , i n ) обозначает эту ситуацию и записывает e ( i ) для ожидаемого количества бросков. Вопрос требует e ( 0 , 0 , 0 , 6 ) : i 3 =n=max(n1,n2,…,nd)
Легкое повторение доступно. На следующем броске, сторона , которая появляется , соответствует одному из : то есть, либо мы не должны видеть его, или нам нужно один раз увидеть, ..., или мы должны увидеть п более раз. j - сколько раз нам нужно было это увидеть.ij n j
Когда , нам не нужно было это видеть, и ничего не меняется. Это происходит с вероятностью i 0 / d .J = 0 я0/ д
Когда нам нужно было увидеть эту сторону. Теперь есть еще одна сторона, которую нужно увидеть j раз, и еще одна сторона, которую нужно увидеть j - 1 раз. Таким образом, i j становится i j - 1, а i j - 1 становится i j + 1 . Пусть эта операция над компонентами i обозначена i ⋅ j , так чтоj>0 j j−1 ij ij−1 ij−1 ij+1 i i⋅j
Это происходит с вероятностью .ij/d
Мы просто должны посчитать этот бросок кубика и использовать рекурсию, чтобы сказать нам, сколько еще бросков ожидается. По законам ожидания и полной вероятности,
(Давайте поймем, что всякий раз, когда , соответствующий член в сумме равен нулю.)ij=0
Если , мы закончили и e ( i ) = 0 . В противном случае мы можем решить для e ( i ) , давая желаемую рекурсивную формулуi0=d e(i)=0 e(i)
Обратите внимание, что - общее количество событий, которые мы хотим увидеть. Операция ⋅ j уменьшает эту величину на единицу для любого j > 0, если i j > 0 , что всегда имеет место. Поэтому эта рекурсия заканчивается на глубине точно | я | (равно 3 ( 6 ) =
Я вычисляю, что
Это показалось мне очень маленьким, поэтому я запустил симуляцию (используя32.669 0.027
R
). После более трех миллионов бросков костей эта игра была завершена более 100 000 раз, при средней длине . Стандартная ошибка этой оценки составляет 0,027 : разница между этим средним и теоретическим значением незначительна, что подтверждает точность теоретического значения.Распределение длин может представлять интерес. (Очевидно, он должен начинаться в , минимальное количество бросков, необходимое для сбора всех шести сторон по три раза каждый.)18
Реализация
Хотя рекурсивный расчете е ( я ) я я
R
E
%.%
прямо сопоставимо с формулой( 1 ) 1 1 0
R
e(c(0,0,0,6))
Накопленная ошибка округления с плавающей запятой уничтожила последние две цифры (что должно быть,
68
а не06
).Наконец, вот оригинальная реализация Mathematica, которая дала точный ответ. Запоминание осуществляется посредством идиоматического
e[i_] := e[i] = ...
выражения, исключающего почти всеR
предварительные сведения. Внутренне, тем не менее, две программы делают то же самое одинаково.источник
Оригинальная версия этого вопроса началась с вопроса:
Распределение количества рулонов требуется ... так, что каждая сторона появляется в 3 раза
Позволять:N= min { n :Икся≥ 3∀я} . N :п( N≤ н )знак равноп( Х∀я≥ 3||н )
т.е. найти cdfп( N≤ н ) просто рассчитать для каждого значения n = { 18 , 19 , 20 , … } :
Вот, например, код Mathematica, который делает это, какN увеличивается с 18 до 60. Это в основном однострочный:
... который дает точный cdf какN увеличивается:
Вот сюжет из cdfп( N≤ н ) в зависимости от N :
Чтобы получить PMFп( N= п ) , просто первое отличие cdf:
Конечно, распределение не имеет верхней границы, но мы можем легко найти здесь столько значений, сколько необходимо. Подход является общим и должен работать так же хорошо для любой желаемой комбинации требуемых сторон.
источник