41
$\begingroup$

I've just played a game with my kids that basically boils down to: whoever rolls every number at least once on a 6-sided die wins.

I won, eventually, and the others finished 1-2 turns later. Now I'm wondering: what is the expectation of the length of the game?

I know that the expectation of the number of rolls till you hit a specific number is $\sum_{n=1}^\infty n\frac{1}{6}(\frac{5}{6})^{n-1}=6$.

However, I have two questions:

  1. How many times to you have to roll a six-sided die until you get every number at least once?
  2. Among four independent trials (i.e. with four players), what is the expectation of the maximum number of rolls needed? [note: it's maximum, not minimum, because at their age, it's more about finishing than about getting there first for my kids]

I can simulate the result, but I wonder how I would go about calculating it analytically.


Here's a Monte Carlo simulation in 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)
$\endgroup$
  • 11
    $\begingroup$ The Coupon collector's problem also see -- googling will give you many more hits and more info. Also try searching on that here at stats.SE. $\endgroup$ – Glen_b Jan 24 '13 at 2:29
  • 1
    $\begingroup$ @Glen_b: Thanks, i didn't know that name! $\endgroup$ – Jonas Jan 24 '13 at 3:02
  • 1
    $\begingroup$ @whuber: I'm not sure this question should have been closed. He wants the expected minimum hitting time of four trials. I was just about to fix my answer for the dynamic programming solution. $\endgroup$ – Neil G Jan 25 '13 at 2:07
  • 2
    $\begingroup$ @whuber: I will edit my post to clarify $\endgroup$ – Jonas Jan 25 '13 at 15:00
  • 3
    $\begingroup$ Relevant math.SE post: Probability distribution in the coupon collector's problem $\endgroup$ – Glen_b Sep 6 '17 at 5:29
22
+50
$\begingroup$

Because a "completely analytical approach" has been requested, here is an exact solution. It also provides an alternative approach to solving the question at Probability to draw a black ball in a set of black and white balls with mixed replacement conditions.


The number of moves in the game, $X$, can be modeled as the sum of six independent realizations of Geometric$(p)$ variables with probabilities $p=1, 5/6, 4/6, 3/6, 2/6, 1/6$, each of them shifted by $1$ (because a geometric variable counts only the rolls preceding a success and we must also count the rolls on which successes were observed). By computing with the geometric distribution, we will therefore obtain answers that are $6$ less than the desired ones and therefore must be sure to add $6$ back at the end.

The probability generating function (pgf) of such a geometric variable with parameter $p$ is

$$f(z, p) = \frac{p}{1-(1-p)z}.$$

Therefore the pgf for the sum of these six variables is

$$g(z) = \prod_{i=1}^6 f(z, i/6) = 6^{-z-4} \left(-5\ 2^{z+5}+10\ 3^{z+4}-5\ 4^{z+4}+5^{z+4}+5\right).$$

(The product can be computed in this closed form by separating it into five terms via partial fractions.)

The cumulative distribution function (CDF) is obtained from the partial sums of $g$ (as a power series in $z$), which amounts to summing geometric series, and is given by

$$F(z) = 6^{-z-4} \left(-(1)\ 1^{z+4} + (5)\ 2^{z+4}-(10)\ 3^{z+4}+(10)\ 4^{z+4}-(5)\ 5^{z+4}+(1)\ 6^{z+4}\right).$$

(I have written this expression in a form that suggests an alternate derivation via the Principle of Inclusion-Exclusion.)

From this we obtain the expected number of moves in the game (answering the first question) as

$$\mathbb{E}(6+X) = 6+\sum_{i=1}^\infty \left(1-F(i)\right) = \frac{147}{10}.$$

The CDF of the maximum of $m$ independent versions of $X$ is $F(z)^m$ (and from this we can, in principle, answer any probability questions about the maximum we like, such as what is its variance, what is its 99th percentile, and so on). With $m=4$ we obtain an expectation of

$$ 6+\sum_{i=1}^\infty \left(1-F(i)^4\right) \approx 21.4820363\ldots.$$

(The value is a rational fraction which, in reduced form, has a 71-digit denominator.) The standard deviation is $6.77108\ldots.$ Here is a plot of the probability mass function of the maximum for four players (it has been shifted by $6$ already):

Figure

As one would expect, it is positively skewed. The mode is at $18$ rolls. It is rare that the last person to finish will take more than $50$ rolls (it is about $0.3\%$).

$\endgroup$
  • $\begingroup$ This solution method was inspired by the observation that sums of geometric variables are mixtures (possibly with negative weights) of geometric variables having the same parameters. A similar relationship holds among Gamma variables (with different rate parameters). I apologize for doing the work in Mathematica, but I'm sure Matlab can carry out these calculations too :-). $\endgroup$ – whuber Feb 27 '14 at 16:45
  • 2
    $\begingroup$ This is the answer I have been hoping for. Thank you very much! I do think I should be able to calculate the numeric results in Matlab :) $\endgroup$ – Jonas Feb 27 '14 at 19:54
  • $\begingroup$ How does $f(z, p) = \frac{p}{1-(1-p)z}$ relate to the probability mass distribution of the geometric distribution? Where does the product $\prod_{i=1}^6 f(z, i/6)$ come from? I get the meaning of $F(z)$, but what is the meaning of $g(z)$? $\endgroup$ – Martijn Weterings Mar 14 at 16:13
  • 1
    $\begingroup$ I see now that $f(z,p)$ is the probability generating function. $\endgroup$ – Martijn Weterings Mar 14 at 16:18
  • $\begingroup$ @MartijnWeterings Thank you--I believe that is the more accurate and conventional term. (You can tell I tend to think of the pmf and pgf as almost the same thing, due to a long habit of using generating functions.) I will change the terminology in this post. $\endgroup$ – whuber Mar 14 at 18:15
13
$\begingroup$

ThePawn has the right idea to attack the problem with a recurrence relationship. Consider a Markov chain with states $\{0, \dotsc, 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 $\frac{i}{6}$. The probability of transition from state $i$ to state $i+1$ is $\frac{6-i}{6}$. Therefore the hitting time of the finish state is \begin{align} \sum_{i=0}^5 \frac{6}{6-i} = 14.7 \end{align}

For the maximum of four trials, consider states that are quadruples. You want to find the expected hitting time for the target state $(6,6,6,6)$. The expected hitting time of any state $j$ is the weighted average for each source state $i$ of the expected hitting time $T_i$ plus the time to go from $i$ to $j$, weighted by $p_ip_{ij}$, the probability of arriving at state $i$ and moving to $j$. You can discover the hitting times and probabilities by dynamic programming. It's not so hard since there is a traversal order to fill in the hitting times and probabilities. For example, for two die: first calculate T and p for (0,0), then for (1,0), then (1, 1), (2, 0), then (2, 1), etc.

In Python:

import numpy as np
import itertools as it
from tools.decorator import memoized  # A standard memoization decorator

SIDES = 6

@memoized
def get_t_and_p(state):
    if all(s == 0 for s in state):
        return 0, 1.0
    n = len(state)
    choices = [[s - 1, s] if s > 0 else [s]
               for s in state]
    ts = []
    ps = []
    for last_state in it.product(*choices):
        if last_state == state:
            continue
        last_t, last_p = get_t_and_p(tuple(sorted(last_state)))
        if last_p == 0.0:
            continue
        transition_p = 1.0
        stay_p = 1.0
        for ls, s in zip(last_state, state):
            if ls < s:
                transition_p *= (SIDES - ls) / SIDES
            else:
                transition_p *= ls / SIDES
            stay_p *= ls / SIDES
        if transition_p == 0.0:
            continue
        transition_time = 1 / (1 - stay_p)
        ts.append(last_t + transition_time)
        ps.append(last_p * transition_p / (1 - stay_p))
    if len(ts) == 0:
        return 0, 0.0
    t = np.average(ts, weights=ps)
    p = sum(ps)
    return t, p

print(get_t_and_p((SIDES,) * 4)[0])
$\endgroup$
  • 1
    $\begingroup$ You've missed the expected maximum number of rolls in four independent repititions of the game. $\endgroup$ – probabilityislogic Jan 24 '13 at 6:22
  • $\begingroup$ Ah, I just noticed that. I think you mean minimum, but yes. $\endgroup$ – Neil G Jan 24 '13 at 6:23
  • $\begingroup$ @NeilG: I actually mean maximum (see my updated question), though I assume that the strategy is the same for min and max. Can you please elaborate on the dynamic programming strategy? $\endgroup$ – Jonas Jan 25 '13 at 15:06
  • $\begingroup$ @Jonas: updated for maximum. I have a lot of work, but I might be able to code this up for you later. $\endgroup$ – Neil G Jan 25 '13 at 16:03
  • 2
    $\begingroup$ @NeilG: Thanks. I had hoped to get a completely analytical approach, but the DP code is quite instructional as well. $\endgroup$ – Jonas Jan 30 '13 at 4:05
6
$\begingroup$

Quick and dirty Monte Carlo estimate in R of the length of a game for 1 player:

N = 1e5
sample_length = function(n) { # random game length
    x = numeric(0)
    while(length(unique(x)) < n) x[length(x)+1] = sample(1:n,1)
    return(length(x))
}
game_lengths = replicate(N, sample_length(6))

Results: $\hat{\mu}=14.684$, $\hat{\sigma} = 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):

grouped_lengths = matrix(game_lengths, ncol=4)
min_lengths = apply(grouped_lengths, 1, min)

Results: $\hat{\mu}=9.44$, $\hat{\sigma} = 2.26$, so a 95% confidence interval for the mean is $[9.411,9.468]$.

$\endgroup$
  • 1
    $\begingroup$ I arrived at a very similar result with a Matlab simulation, but I was curious about how I would solve this analytically. Also, since I play with my kids, they all want to finish the game, regardless of who wins, so I do want to ask about the maximum. $\endgroup$ – Jonas Jan 24 '13 at 3:01
5
$\begingroup$

How about a recursive relation with respect to the remaining number $m$ of sides you have to obtain in order to win.

$$T_{1} = 6$$ $$T_{m} = 1 + \frac{6 - m}{6}T_{m} + \frac{m}{6}T_{m-1}$$

Basically, the last relation is saying that the number of time to roll the $m$ remaining different numbers is equal to $1$ plus:

  • $T_{m}$ if you roll the one of the $6 - m$ numbers already rolled (probability $\frac{6 - m}{6}$)
  • $T_{m-1}$ if you roll one of the $m$ remaining numbers (probability $\frac{m}{6}$)

Numerical application of this relation gives $14.7$.

$\endgroup$
  • $\begingroup$ Something seems wrong with this answer. Shouldn't it be a summation at the end? $T_i = T_{i-1} + \frac{6}{6-i + 1}$. $\endgroup$ – Neil G Jan 24 '13 at 2:57
  • 1
    $\begingroup$ Yes sorry made a mistake, I am correcting it $\endgroup$ – ThePawn Jan 24 '13 at 3:04
  • $\begingroup$ I hope you don't mind that I added an answer. 14.7 is correct, but the recurrence relationship is still flawed… $\endgroup$ – Neil G Jan 24 '13 at 3:07
  • $\begingroup$ No problem, should have been careful the first time :). Your answer is great. $\endgroup$ – ThePawn Jan 24 '13 at 3:11
5
$\begingroup$

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 is $\frac{5}{6}$, so it'll take $\frac{6}{5}$ (1.2) rolls on average.

You then need to roll any number other than the first two. The chance of this happening is $\frac{4}{6}$, so it'll take $\frac{6}{4}$ (1.5) rolls on average.

You then need to roll any number other than the first three. The chance of this happening is $\frac{3}{6}$, so it'll take $\frac{6}{3}$ (2) rolls on average.

And so on until we successfully complete our 6th roll:

$\frac{6}{6} + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1} = 14.7\ rolls$

This answer is similar to Neil G's answer, only, without the markov chain.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
-4
$\begingroup$

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'.

$\endgroup$
  • 6
    $\begingroup$ That would answer the question 'to guarantee with absolute certainty to get every number at least once'. For the question that was asked, the answer is a random variable, the distribution of which can be well approximated. $\endgroup$ – Glen_b Jun 5 '13 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.