Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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