An interesting problem of tossing a fair die successively

Question

A fair die is tossed successively. Let $X$ denote the number of tosses until each of the six possible outcomes occurs at least once. Find the probability mass function of $X$. I'm also given this $hint$: For $1\leq i \le6$ let $E_i$ be the event that the outcome $i$ does not occur during the first $n$ tosses of the die. First calculate $P(X>n)$ by writing the event $X>n$ in terms of $E_1, E_2,...E_6$.

I know that $P(X>n)=1-P(X<n)$ and from $P(X<n)$ we can find the probability mass function. But I dont know how to find $P(X<n)$.

I looked and the answer is $$(\frac56)^{n-1}-5(\frac46)^{n-1}+10(\frac36)^{n-1}-10(\frac26)^{n-1}+5(\frac16)^{n-1}\quad for \quad n\ge6$$ I tried to derive how this was found but I found the alternating signs to be tricky and I'm also confused with why the coefficients are what they are.

Answer 1

Let $Y_j$ be the number of tosses after there have been $j-1$ distinct outcomes until there have been $j$ distinct outcomes. Thus $Y_1 = 1$ (i.e. the first toss always is one of the six outcomes), $X = Y_1 + Y_2 + \ldots + Y_6$, and $Y_1, \ldots, Y_6$ are independent. $Y_j$ for $j = 2$ to $6$ is a (shifted) geometric random variable, so its probability generating function is easy to find, ...

Answer 2

Another way: Let $A_{i,n}$ be the event that the number $i$ is not rolled after $n$ rolls. Then the probability you're looking for is $1-P(A_{1,n} \cup ... \cup A_{6,n}) $

You can compute the second term using inclusion-exclusion.

Edit: In case this isn't clear, this gives you $P(X \leq n)$

Then do $P(X=n)= P(X \leq n) - P(X \leq n-1)$

Answer 3

Note that $X=\sum\limits_{k=1}^6T_k$ where $T_k$ is the number of tosses between the appearances of the $k-1$th new result and the $k$th new result. Thus, $T_1=1$, $T_2$ is geometric with parameter $\frac56$, and so on until $T_6$ which is geometric with parameter $\frac16$.

The generating function of a random variable $T$ geometric with parameter $p$ is $\mathrm E(s^T)=ps/(1-(1-p)s)$ hence $$ \mathrm E(s^X)=\prod_{k=1}^6\frac{\frac{k}6s}{1-(1-\frac{k}6)s}=\frac{5!}{6^5}s^6\cdot\prod_{k=1}^5\frac1{1-\frac{k}6s}. $$ The decomposition of the last product in simple fractions is $$ \prod_{k=1}^5\frac1{1-\frac{k}6s}=\sum_{k=1}^5\frac{c_k}{1-\frac{k}6s},\qquad c_k=\prod_{1\leqslant i\leqslant 5}^{i\ne k}\frac1{1-\frac{i}k}, $$ hence $$ \mathrm E(s^X)=\frac{5!}{6^5}s^6\cdot\sum_{k=1}^5c_k\sum_{n\geqslant0}\left(\frac{k}6s\right)^n. $$ The coefficients of each power of $s$ must coincide hence, for every $n\geqslant0$, $$ \mathbb P(X=n+6)=\frac{5!}{6^5}\cdot\sum_{k=1}^5c_k\left(\frac{k}6\right)^n. $$