# Rolling a k-sided fair die n times and not see all k numbers fall

If we throw a k-sided fair die n times, what is the probability that we will never get one of its k numbers? Further, what is the probability that two, three, or more of its numbers will never occur in the results? (presume the faces are unique - numbered 1 to k)

More formally, if the occurrence count of the number $i$ after $n$ throws with a fair, uniquely numbered die is $X_i$ and $\sum_{i}{X_i}=n$, let's define a "zero occurrence" set $S = \{ x_i \mid x_i = 0 \}$. S contains all the numbers that didn't occur during the $n$ throws. If we consider $Y$ to be the size of the set S, $Y = \left\vert S\right\vert$, the question is asking for a closed form expression of the pmf of $Y$ that would allow computing the probabilities.

I have very little so far:

$$P(Y=1)= P(X_1=0, X_2 > 0, \ldots, X_k>0) + P(X_1>0, X_2 = 0, \ldots, X_k>0) + \ldots + P(X_1>0, X_2 > 0, \ldots, X_k=0) = k P(X_1=0, X_2 > 0, \ldots, X_k>0)=\sum\limits_{\{x_1,x_2,\ldots, x_k\}\in P} \frac{n!}{x_1!\ldots x_k!}{p_1^{x_1}\ldots p_k^{x_k}}$$ I struggle to get anything useful from the multinomial pmf, since to calculate its cdf, you have to sum over different partitions of n elements into k-1 bins. Finding the set of possible partitions $P$, where $P = \{\{x_1,x_2,\ldots,x_k\}\mid x_1 = 0 \land \sum_i{x_i} = n \}\}$ is np hard and there are ${n-1}\choose{k-2}$ probabilities we would have to sum up (we have k-1 bins to redistribute n throws). I wonder whether there is a way to derive a result which doesn't involve partitioning and summing up the probabilities.

• Hint : Denote $P_k$ = probability that $k$ fixed numbers do not appear and use inclusion/exclusion to calculate the desired probability. – Peter Jul 1 '16 at 11:52
• Do you want the probability that exactly $m$ faces are missing, or that at least $m$ faces are missing? The probability $1$ or more is missing involves Stirling numbers of the second kind. – André Nicolas Jul 1 '16 at 12:30
• I'm asking about the probability distribution of the count of "non-observed numbers" during n trials. ("non-observed numbers" are numbers that occurred 0 times). To give a direct answer to your question: knowing both would be ideal, but if possible I would like to know at least the probability of exactly $m$ faces missing. – means-to-meaning Jul 1 '16 at 13:42

There are $\binom ky$ ways to choose $y$ sides that occur, $\def\stir#1#2{\left\{{#1\atop#2}\right\}}\stir ny$ ways to partition the $n$ throws into $y$ non-empty subsets and $y!$ ways to assign the $y$ subsets to the $y$ sides, so the probability that exactly $y$ sides occur in $n$ throws is

\begin{align} \frac{y!\binom ky\stir ny}{k^n}=k^{-n}\binom ky\sum_{j=0}^y(-1)^{y-j}\binom yjj^n\;, \end{align}

where $\stir ny$ is a Stirling number of the second kind.

If we throw a k-sided fair die n times, what is the probability that we will never get one of its k numbers? Further, what is the probability that two, three, or more of its numbers will never occur in the results? (presume the faces are unique - numbered 1 to k)

Maybe I have misunderstood the problem but it looks much easier to me.

The probability we will never get one of its k numbers in n rolls is just

$\left(\frac{k-1}{k}\right)^n$

For instance, the probability that number 3 does not occur if a 6 sided (fair) dice is rolled 7 times is

$\left(\frac{6-1}{6}\right)^7\approx 27.91\%$

And the probabilty that two, three, or more of its numbers will never occur in the results can be expressed in a similar way.

• I think the OP is looking for the probability that at least one of the numbers does not occur. – Peter Jul 1 '16 at 12:07
• Maybe. But I don´t see that the first paragraph can be interpretated in different ways. But you can post your own answer. – callculus Jul 1 '16 at 12:25
• Thanks for your answer, it's very clear. I was asking about the probability of the "count of non-occurred numbers". It seems to me there is a difference, as the probability of the count of "non-occurred" numbers being 1 when throwing once with a six-sided die is 0 (5 numbers will not occur with probability 1) and not $[(k-1)/k]^1$. Your answer is definitely correct for one interpretation of the 1st paragraph though. Thank you! – means-to-meaning Jul 1 '16 at 13:28