2
$\begingroup$

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:

\begin{equation}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}} \end{equation} 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.

$\endgroup$
  • 1
    $\begingroup$ Hint : Denote $P_k$ = probability that $k$ fixed numbers do not appear and use inclusion/exclusion to calculate the desired probability. $\endgroup$ – Peter Jul 1 '16 at 11:52
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Jul 1 '16 at 12:30
  • $\begingroup$ 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. $\endgroup$ – means-to-meaning Jul 1 '16 at 13:42
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think the OP is looking for the probability that at least one of the numbers does not occur. $\endgroup$ – Peter Jul 1 '16 at 12:07
  • $\begingroup$ Maybe. But I don´t see that the first paragraph can be interpretated in different ways. But you can post your own answer. $\endgroup$ – callculus Jul 1 '16 at 12:25
  • $\begingroup$ 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! $\endgroup$ – means-to-meaning Jul 1 '16 at 13:28

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.