Roll a fair die until a 6 appears for the third time. What is the chance that all six values have occurred?

Question

The question in the title is a homework question that I have been stumped on for some time. My approach thus far was to treat it as an occupancy problem. From class we derived the following formula for the probability of k faces being rolled on an r sided die after n rolls:

$$ P(Y = k) = \binom{r}{k} \big (\frac{k}{r}\big )^n \sum_{i=0}^{r}(-1)^i\binom{k}{i}\big(1-\frac{i}{k}\big)^n$$

So what I have done is set k = r = 6 and arrived at:

$$ P(Y = 6) = \sum_{i=0}^{6}(-1)^i\binom{6}{i}\big(1-\frac{i}{6}\big)^n$$

However, the problem now is that n is a random integer variable between $3$ and infinity. What I did next was attempt to model the number of rolls as a negative-binomial random variable and then compute the expectation value of the above expression inside of this distribution; however, it produces a very ugly expression which I am pretty sure is still wrong because it does not include the fact that a 6 is guaranteed to be rolled.

I basically have run out of ideas and am somewhat stuck on how to proceed. My approach may be a total red herring, so feel free to discard it in any advice you give. Also, this is homework, so please don't list a full solution. Thanks for any help!

Answer 1

First let's find the probability that the third time a $6$ appears occurs on the $n$th roll. This is simply the probability that the $n$th roll is a $6$ and exactly two rolls before it are also $6$'s, which is $\frac{{n-1 \choose 2}*5^{n-3}}{6^n}$.

Then, the probability that all five other values have occurred during the $n-3$ chances can be computed by the principle of inclusion and exclusion as $1-\frac{5*4^{n-3}}{5^{n-3}}+\frac{10*3^{n-3}}{5^{n-3}}-\frac{10*2^{n-3}}{5^{n-3}}+\frac{5}{5^{n-3}}$ when $n>3$, and $0$ when $n=3$. Multiplying these two values and summing over all $n$, you get a polynomial multiplied by exponential functions, which can each be evaluated exactly by using generating functions (or simply algebraic manipulation).

Answer 2

Define $I:=\left\{ \left(r,s\right)\in\mathbb{N}\times\mathbb{N}\mid0\leq r\leq s\leq5\right\} $.

Let $E_{r,s}$ denote the following event:

Before the first number $6$ occurs exactly $r$ distinct numbers in $\{1,2,3,4,5\}$ occur, before the second number $6$ occurs exactly $s$ distinct numbers in $\{1,2,3,4,5\}$ occur, and before the third number $6$ occurs exactly $5$ distinct numbers in $\{1,2,3,4,5\}$ occur.

This for each $\left(r,s\right)\in I$.

These events are disjoint and $E=\bigcup_{(r,s)\in I}E_{r,s}$ is the event that all values have occurred when number $6$ occurs for the third time.

So you are actually looking for $$P(E)=\sum_{\left(r,s\right)\in I}P\left(E_{r,s}\right)$$

The cardinality of $I$ is $\binom{7}{2}=21$ (so not to large to work with) and $$P\left(E_{r,s}\right)=\frac{1}{6}\times\frac{1}{6-r}\times\frac{1}{6-s}$$

So for $E=\bigcup_{(r,s)\in I}E_{r,s}$ we find:

$$P(E)=\frac{1}{6}\sum_{(r,s)\in I}\frac{1}{(6-r)(6-s)}=\frac{13489}{21600}$$

---

To clarify, taking $21215261542643456$ as example:

Suppose you start throwing and only denote numbers that have not been thrown before. This until all numbers have occurred. This result in a list $215643$. In this example number $6$ stands on place $4$ (then $r=3$) but it has equal probability to stand on any other place, and there are $6$ places. This explains the factor $\frac{1}{6}$. Then you go on, but from here you only denote the numbers $3$, $4$ and $6$. The others are simply not relevant. You end up with $463$ (then $s=4$) with probability $\frac{1}{3}$. Note that again there are equal probabilities for the place of number $6$ in list $463$. Now you go on noting only the numbers $6$ and $3$. You end up with $36$ (so that all six values have occurred) and the probability that this occurs is $\frac{1}{2}$. This explains why $P(E_{3,4})=\frac{1}{6}\times\frac{1}{3}\times\frac{1}{2}$

Answer 3

The problem seems to be taylored for inclusion-exclusion formula...

Let $I=\{1,2,3,4,5\}$. For every $i$ in $I$, let $A_i$ denote the event that $i$ does not appear before $6$ appears for the third time. For every $J\subseteq I$, let $A_J=\bigcap\limits_{i\in J}A_i$.

One asks for $1-P(A)$ where $A=\bigcup\limits_{i\in I}A_i$ is the event that one result does not appear before $6$ appears for the third time.

Then, for each $i$ in $I$, $A_i$ occurs when one wins three times at the heads or tails game of "$6$ appears before $i$", thus $P(A_i)=\frac1{2^3}$. Likewise, for every $J\subseteq I$ of size $k$, $A_J$ occurs when one wins three times at the heads or tails game of "$6$ appears before any $i$ in $J$", thus $P(A_J)=\frac1{(k+1)^3}$. Note finally that there exists ${5\choose k}$ such sets $J$.

Now, exclusion-inclusion reads $$1-P(A)=\sum_{k=0}^5(-1)^k\sum_{J\subseteq I,|J|=k}P(A_J)=\sum_{k=0}^5(-1)^k{5\choose k}\frac1{(k+1)^3}=\frac{13489}{21600}\approx62.449\%.$$

Post-hoc exercise: Show that this formula is equivalent to @drhab's suggestion if, for every $n\geqslant1$, $$\sum_{1\leqslant i\leqslant j\leqslant n}\frac1{ij}=\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac1{k^2}.$$