6
$\begingroup$

Given a $n$-sided fair die, show that the probability $P$ that all faces from $1$ to $11$ show when doing $3n$-rolls is bounded by

$1 - 11 \cdot \frac{(n-1)^{3n}}{n^{3n}} \leq P \leq 1 - 11 \cdot \frac{11(n-1)^{3n}}{n^{3n}} + 5 \cdot 11 \cdot \frac{(n-2)^{3n}}{n^{3n}}$

I am really stuck on this one. I figured that the exact probability is very hard to find and stirling numbers are involved. So the only chance I have is to figure out what events where used for that bounds. My guess is that the left one comes from the assumtion that (Edit: Warning this is not quite correct, check the comments)

$\mathbb{P}($Faces 1-11 don't occur at all$)=\frac{|E|}{|Q|}=\frac{11 \cdot (n-1)^{3n}}{n^{3n}}$

And if you look at the complement it is that all faces 1-11 at least occur once. Surely this is a lower bound but how could I get the upper bound, I hope that I did not overlook something very easy.

  • 1
    Thank you cardinal that did the job, maybe you can write it as an answer so I can accept it :-)2011-04-19

1 Answers 1

4

The answer can be arrived at via a pretty standard application of the Bonferroni inequalities. We generalize this problem ever so slightly. Fix $1 \leq m \leq n$ and $M \geq m$. We want to find the probability of seeing each element of the set $\{1,\ldots,m\}$ within $M$ rolls of our $n$-sided die.

Let $A_i$ be the event that the $i$th outcome was not rolled in the first $M$ throws of the die. Let $A = \cup_{i=1}^m A_i$ be the event that not all of $\{1,\ldots,m\}$ are seen in the first $M$ throws. We are interested in the complement, $\bar{A}$, of this event.

A straightforward application of the Bonferroni inequalities shows that $ \renewcommand{\Pr}{\mathbb{P}} \sum_{i=1}^m \;\Pr(A_i) - \sum_{1 \leq i < j \leq m} \Pr(A_i \cap A_j) \leq \Pr(A) \leq \sum_{i=1}^m \;\Pr(A_i) \> . $

But, $\Pr(A_i) = (1-1/n)^M$ for each $i$ and $\Pr(A_i \cap A_j) = (1-2/n)^M$ for each pair $i \neq j$. This yields $ m\Big(1-\frac{1}{n}\Big)^M - \frac{m(m-1)}{2}\Big(1-\frac{2}{n}\Big)^M \leq \Pr(A) \leq m \Big(1-\frac{1}{n}\Big)^M $

Using the fact that $\Pr(\bar{A}) = 1 - \Pr(A)$ and plugging in $m = 11$ and $M = 3 n$ gives the result.


Note that if $M$ is relatively large with respect to $n$ and $m$, then we can get an exponential bound. In particular, if, for $c > 0$, $M = n \log m + c n$, then $ m(1-1/n)^M = m (1 - 1/n)^{n \log m + c n} \leq e^{-c} $ and so the probability of seeing all elements of $\{1,\ldots,m\}$ within $M = n \log m + c n$ throws is $ \Pr(\bar{A}) \geq 1 - e^{-c} \> . $