Я только что сыграл в игру со своими детьми, которая сводится к следующему: кто бы ни бросил каждое число хотя бы один раз на шестистороннем кубике, выигрывает.
В конце концов я выиграл, а остальные закончили на 1-2 хода позже. Теперь мне интересно: какова ожидаемая продолжительность игры?
Я знаю , что математическое ожидание количества рулонов до вас ударил несколько специфичный .
Однако у меня есть два вопроса:
- Сколько раз вам приходится бросать шестигранный кубик, пока вы не получите каждое число хотя бы один раз?
- Каково ожидание максимального количества бросков из четырех независимых испытаний (т.е. с четырьмя игроками) ? [примечание: это максимум, а не минимум, потому что в их возрасте это больше о завершении, чем о том, чтобы добраться туда сначала для моих детей]
Я могу смоделировать результат, но мне интересно, как бы я рассчитал его аналитически.
Вот симуляция Монте-Карло в Matlab
mx=zeros(1000000,1);
for i=1:1000000,
%# assume it's never going to take us >100 rolls
r=randi(6,100,1);
%# since R2013a, unique returns the first occurrence
%# for earlier versions, take the minimum of x
%# and subtract it from the total array length
[~,x]=unique(r);
mx(i,1)=max(x);
end
%# make sure we haven't violated an assumption
assert(numel(x)==6)
%# find the expected value for the coupon collector problem
expectationForOneRun = mean(mx)
%# find the expected number of rolls as a maximum of four independent players
maxExpectationForFourRuns = mean( max( reshape( mx, 4, []), [], 1) )
expectationForOneRun =
14.7014 (SEM 0.006)
maxExpectationForFourRuns =
21.4815 (SEM 0.01)
Ответы:
Поскольку был запрошен «полностью аналитический подход», вот точное решение. Это также обеспечивает альтернативный подход к решению вопроса о вероятности нарисовать черный шар в наборе из черных и белых шаров со смешанными условиями замены .
Количество ходов в игре,Икс , может быть смоделировано как сумма шесть независимых реализаций геометрического ( р ) переменных с вероятностями р = 1 , 5 / 6 , 4 / 6 , 3 / 6 , 2 / 6 , 1 / 6 , каждый из них сдвинут на 1 (потому что геометрическая переменная считает только броски, предшествующиеуспех, и мы должны также подсчитать количество бросков, на которых были достигнуты успехи). Вычисляя с геометрическим распределением, мы, следовательно, получим ответы, которые на 6 меньше, чем желаемые, и поэтому должны быть уверены, что добавим 6 обратно в конце.
Производящая функция вероятности (PGF) такой геометрической переменной с параметромп является
Следовательно, pgf для суммы этих шести переменных
(Произведение может быть вычислено в этой закрытой форме, разделив его на пять слагаемых через частичные дроби.)
Кумулятивная функция распределения (CDF) получается из частичных суммg (в виде степенного ряда по z ), который составляет суммирование геометрических рядов, и определяется как
(Я написал это выражение в форме, которая предлагает альтернативный вывод по принципу включения-исключения.)
Отсюда получаем ожидаемое количество ходов в игре (отвечая на первый вопрос) как
CDF максимума изm независимых версий X равен F(z)m (и из этого мы, в принципе, можем ответить на любые вероятностные вопросы о максимуме, который нам нравится, например, какова его дисперсия, каков ее 99-й процентиль, и так далее). С м = 4 мы получаем ожидание
(Значение представляет собой рациональную дробь, которая в сокращенной форме имеет знаменатель из 71 цифры.) Стандартное отклонение составляет6.77108…. Вот график функции вероятности массы максимума для четырех игроков (она уже смещена на 6 ):
Как и следовало ожидать, это положительно перекошен. Режим на18 рулонов. Редко, когда последний, кто закончит, получит более 50 бросков (это около 0.3% ).
источник
ThePawn has the right idea to attack the problem with a recurrence relationship. Consider a Markov chain with states{0,…,6} corresponding to the count of the number of distinct dice rolls that have happened. State 0 is the start state, and state 6 is the finish state. Then, the probability of transition from state i to itself is i6 . The probability of transition from state i to state i+1 is 6−i6 . Therefore the hitting time of the finish state is
In Python:
источник
Quick and dirty Monte Carlo estimate in R of the length of a game for 1 player:
Results:μ^=14.684 , σ^=6.24 , so a 95% confidence interval for the mean is [14.645,14.722] .
To determine the length of a four-player game, we can group the samples into fours and take the average minimum length over each group (you asked about the maximum, but I assume you meant the minimum since, the way I read it, the game ends when someone succeeds at getting all the numbers):
Results:μ^=9.44 , σ^=2.26 , so a 95% confidence interval for the mean is [9.411,9.468] .
источник
How about a recursive relation with respect to the remaining numberm of sides you have to obtain in order to win.
Basically, the last relation is saying that the number of time to roll them remaining different numbers is equal to 1 plus:
Numerical application of this relation gives14.7 .
источник
A simple and intuitive explanation to the first question:
You first need to roll any number. This is easy, it'll always take exactly 1 roll.
You then need to roll any number other than the first one. The chance of this happening is56 , so it'll take 65 (1.2) rolls on average.
You then need to roll any number other than the first two. The chance of this happening is46 , so it'll take 64 (1.5) rolls on average.
You then need to roll any number other than the first three. The chance of this happening is36 , so it'll take 63 (2) rolls on average.
And so on until we successfully complete our 6th roll:
This answer is similar to Neil G's answer, only, without the markov chain.
источник
the probability density function (or discrete equivalent) for getting the next new number is:
f = sum( p * ( 1 - p )^( i - 1 ) , i = 1 .. inf )
where p is the probability per roll, 1 when no numbers have been rolled, 5/6 after 1, 4/6 .. down to 1/6 for the last number
the expected value, mu = sum( i * p * ( 1 - p )^( i - 1 ), i = 1 .. inf ) letting n = i - 1, and bringing p outside the summation,
mu = p * sum( ( n + 1 ) * ( 1 - p )^n, n = 0 .. inf )
mu = p * sum( n(1-p)^n, n = 0 .. inf ) + p * sum( (1-p)^n, n = 0 .. inf ) mu = p * (1-p) / (1-p-1)^2 + p * 1/ (1-(1-p))
mu = p * ( 1 - p ) / p^2 + p/p
mu = ( 1 - p ) / p + p/p
mu = ( 1 - p + p ) / p
mu = 1 / p
The sum of the expected values (mus) for ps of 1, 5/6, 4/6, 3/6, 2/6, and 1/6 is 14.7 as previously reported, but 1/p per required number is general regardless of die size
similarly, we can calculate the standard deviation analytically
sigma^2 = sum( ( i - mu )^2 * p * ( 1 - p )^( i - 1 ), i = 1 .. inf )
I will spare you the algebra here, but sigma^2 = (1-p)/p^2
In the case of 6, the sum of sigma^2 for each step is 38.99 for a standard deviation of about 6.24, again, as simulated
источник
Question 1 was:
How many times do you have to roll a six-sided dice until you get every number at least once?
Obviously, the correct answer must be 'infinite'.
источник