10
$\begingroup$

What is the probability of having to roll a (six sided) dice at least 8 times before you get to see all of the numbers at least once?

I don't really have a clue how to work this out.

Edit: If we are trying to find the number of situations where all of the numbers are shown, for seven rolls, a favorable outcome would be one in which there are two numbers the same, for example: 1123456. These numbers can be arranged in 7!/2!5! ways, and there are 6 different numbers that could be repeated. So the probability of getting all 6 numbers with 7 throws is (6*7!/2!5!)/6^7 = 126/279936. Is that right? Then 1 minus this is the probability?

Edit: prob. of not getting all six numbers with seven rolls = 1-prob of getting all six numbers with seven rolls

Six numbers same with seven rolls means one number repeated twice 7!/2! ways of doing this for each repeated number 6*(7!/2!) is number of ways of getting all six numbers with seven rolls. Total number of outcomes 6^7. Prob of getting all six numbers with seven rolls = (6*(7!/2!))/6^7 = 0.054 Prob of not getting all six numbers with seven rolls (=prob of needing at least 8 rolls to get all numbers) = 1-0.054 = 0.946

$\endgroup$
  • 2
    $\begingroup$ Let $p$ be the probability that in $7$ rolls you see all faces at least once. We find $p$. Then the answer to the original problem is $1-p$. It should not be too hard to find $p$, by counting the "favourables" and dividing by $6^7$. $\endgroup$ – André Nicolas Aug 6 '15 at 13:34
  • 1
    $\begingroup$ As a further hint to counting the "favorables" for $p$, note that if you roll 7 times you will see at least one number repeated. But if this happens more than once you will not get to see all 6 numbers. $\endgroup$ – David K Aug 6 '15 at 13:50
  • 1
    $\begingroup$ The title and text of the question don't match. Please clarify whether "at least" is intended, as in the text, or "exactly", as the title appears to imply. $\endgroup$ – joriki Aug 6 '15 at 14:17
  • $\begingroup$ To clarify are you asking what is the probability of needing exactly 8 rolls to see all numbers or 8 or more rolls? $\endgroup$ – Warren Hill Aug 7 '15 at 8:20
6
$\begingroup$

Rephrase the question:

What is the probability of not seeing all $6$ values when rolling a die $7$ times?


Find the probability of the complementary event:

What is the probability of seeing all $6$ values when rolling a die $7$ times?


Use the inclusion/exclusion principle in order to count the number of ways:

  • Include the number of ways to roll a die $7$ times and see up to $6$ different values: $\binom66\cdot6^7$
  • Exclude the number of ways to roll a die $7$ times and see up to $5$ different values: $\binom65\cdot5^7$
  • Include the number of ways to roll a die $7$ times and see up to $4$ different values: $\binom64\cdot4^7$
  • Exclude the number of ways to roll a die $7$ times and see up to $3$ different values: $\binom63\cdot3^7$
  • Include the number of ways to roll a die $7$ times and see up to $2$ different values: $\binom62\cdot2^7$
  • Exclude the number of ways to roll a die $7$ times and see up to $1$ different values: $\binom61\cdot1^7$

Divide the result by the total number of ways, which is $6^7$:

$$\frac{\binom66\cdot6^7-\binom65\cdot5^7+\binom64\cdot4^7-\binom63\cdot3^7+\binom62\cdot2^7-\binom61\cdot1^7}{6^7}=\frac{35}{648}$$


Calculate the probability of the original event by subtracting the result from $1$:

$$1-\frac{35}{648}=\frac{613}{648}\approx94.6\%$$

$\endgroup$
  • $\begingroup$ Nice use of inclusion/exclusion! Simulated probability of seeing all 6 faces in 7 rolls in my Answer is 0.0544 ± 0.001, compared to exact 35/648 = 0.0540 in this Answer. $\endgroup$ – BruceET Aug 7 '15 at 8:46
  • $\begingroup$ @BruceTrumbo: Thanks :) $\endgroup$ – barak manos Aug 7 '15 at 8:50
6
$\begingroup$

(Edit: Answer is for the probability of seeing all the numbers for $n$ rolls)

For exactly $n$ rolls, the problem can be solved using a markov chain

\begin{align*} A&= \begin{pmatrix}0 & 1 & 0 & 0 & 0 & 0 & 0\cr 0 & \frac{1}{6} & \frac{5}{6} & 0 & 0 & 0 & 0\cr 0 & 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0\cr 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0\cr 0 & 0 & 0 & 0 & \frac{2}{3} & \frac{1}{3} & 0\cr 0 & 0 & 0 & 0 & 0 & \frac{5}{6} & \frac{1}{6}\cr 0 & 0 & 0 & 0 & 0 & 0 & 1\end{pmatrix} \end{align*}

where the rows and columns are the number of faces of the die seen.

The probability of seeing all the faces in exactly 8 rolls is $(A^8)[0,6]$, which is $\dfrac{665}{5832}\approx 0.11402606310014$

For any $n$, it can be found by finding the generating function $G(z)$ and in turn finding the coefficient of $z^n$

\begin{align*} \mathbb{P}(n) = 1-\frac{20}{2^n}+15\left(\frac{2}{3}\right)^n+\frac{15}{3^n}-6\left(\frac{5}{6}\right)^n-\frac{6}{6^n} \end{align*}

$\endgroup$
  • $\begingroup$ That was my original solution (should be $1-\frac{665}{5832}$, BTW)... But I then realized that "at least 8 times before you get to see all of the numbers" meant that you were allowed to see all of the numbers by the $8$th trial, so you need to replace $8$ with $7$ in your answer. $\endgroup$ – barak manos Aug 7 '15 at 12:55
  • $\begingroup$ Oh, okay. I solved for the probability of seeing all the numbers for n rolls. $\endgroup$ – gar Aug 7 '15 at 13:24
  • $\begingroup$ Very elegant. Clarity of presentation could be improved for quick reading (and more upvotes). I suggest to: make the first sentence bold, correcting for n=7 so that the answers match, small subtitle "general solution" at the end. $\endgroup$ – Symeof Sep 23 '15 at 21:36
1
$\begingroup$

Perhaps this is of some help, even if not your final answer.

If a fair die is rolled 8 times and $X$ is the number of different faces seen, then simulation of a million performances of the 8-roll experiment shows the following approximate distribution of $X$, in which the margin of simulation error is about $\pm 0.001.$

         1        2        3        4        5        6 
  0.000003 0.002275 0.069393 0.363681 0.450468 0.114180 

Of course, $P(X = 1) = 1/6^7 = 0.000004$ to 6 places. To get $P(X = 6),$ consider that one face may be seen three times, or two different faces may each be seen twice. A straightforward computation of other probabilities in the distribution seems feasible but increasingly tedious. Perhaps there are clever combinatorial methods that make some of them easier.

However, pending clarification, I'm still not sure if $P(X = 6)$ is exactly the probability you're trying to find.

Notes:

(a) For a 7-roll experiment an analogous simulation gives $0.0544 \pm 0.001,$ which does not agree with your result $126/279936 \approx 0.00045.$ (I do not believe you are considering all possible permutations of the numbers that occur only once.)

(b) For a 6-roll experiment a simulation gives $0.015496 \pm 0.001,$ compared with the exact $6!/6^6 = 0.0154321.$ Clearly, the probability of getting all 6 faces is 7 rolls must be larger than that.

(c) A related problem is the number of rolls $W$ required before all 6 faces are seen. Then $E(W) = 6/6 + 6/5 + \dots + 6/1 = 14.7.$ For more on this, see the 'coupon collecting problem'.

$\endgroup$
1
$\begingroup$

Here's another way of looking at it, along the lines suggested by barak manos.

Note that 7 rolls containing all 6 values must contain a duplicate. There are $\binom{7}{2}\cdot 6$ choices for the duplicate entries. Thus, the desired probability is given by

$$1-\frac{\binom{7}{2}\cdot 6\cdot 5!}{6^7} = 1-\frac{70}{1296}=\frac{613}{648}.$$

$\endgroup$

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.