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
    The probability that $1-11$ don't occur at all is $\left(\frac{n-11}{n}\right)^{3n}$ as you have to make sure each die is greater than 11. But the complement is only that at least one of $1-11$ occurs, not that all of them do.2011-04-19
  • 0
    I am afraid you are right.2011-04-19
  • 1
    @user3123: Note that $5 \cdot 11$ can be unsimplified to $\binom{11}{2}$, and think *inclusion-exclusion*.2011-04-19
  • 3
    **Hint**: Let $A_i$ denote the event that the number $i$ is *not* seen in the first $3n$ rolls. Now use the Bonferroni inequalities (aka inclusion-exclusion) on $\cup_{i=1}^{11} A_i$.2011-04-19
  • 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} \> . $$