How often do you have to roll a 6-sided die to obtain every number at least once?

Question

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)

Answer 1

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):

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\%$).

Answer 2

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])

Answer 3

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]$.

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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