Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Ross Millikan Apr 19 '11 at 17:07
    
I am afraid you are right. –  Listing Apr 19 '11 at 17:12
1  
@user3123: Note that $5 \cdot 11$ can be unsimplified to $\binom{11}{2}$, and think inclusion-exclusion. –  André Nicolas Apr 19 '11 at 17:25
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$. –  cardinal Apr 19 '11 at 17:27
1  
Thank you cardinal that did the job, maybe you can write it as an answer so I can accept it :-) –  Listing Apr 19 '11 at 17:36

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer

Your Answer

 
discard

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.