Exercise 1.8.13 in Grimmett & Stirzaker's 'Probability and Random Processes'

Question

The question asks to prove Waring's theorem shown below:

$P(N_k)=\sum_{i=0}^{n-k}(-1)^i$ ${k+1}\choose{k}$ $S_{k+i}$ where $S_j= \sum_{i_1<i_2<...i_j} P(A_1 \cap A_2 ... \cap A_j )$

Where $P(N_k)$ is the probability of selecting exactly k out of a possible N events occurs.

I'm then asked to use the theorem to calculate the probability that out of the purchase of six packets of Corn flakes (each of which contains one of 5 possible busts), you end up with exactly three distinct busts.

The answer is:

$P(N_3) =$${5}\choose{3}$ $\alpha_3$ - ${5}\choose{4}$ ${4}\choose{3}$ $\alpha_4$+${5}\choose{3}$ $\alpha_5$

Where $\alpha_j$ is the probability that the j most recent vice-chancellors are obtained.

I'm confused by the solution in several respects:

1.) Why is $\alpha_j$ is the probability that the j most recent vice-chancellors rather than just any 3 from 5 as I would expect when applying the theorem.

2.) Why is the second term multiplied by 2 binomial coefficients (mathematically I see that to get 3 from 4 you need to know how many sets of 4 you have, but this does not appear to be given in the original formula?)

3.) How should I express the answer in terms on the original theorem nomenclature?

We are starting from having 3 items so $i=3$?

The number of individual events is k=3?

The total possible number of events is $n=5$?

but if this were correct the formula should read:

$P(N_3)=\sum_{i=3}^{2}(-1)^3$ ${k+1}\choose{k}$ $S_{k+i}$ where $S_j= \sum_{i_1<i_2<...i_j} P(A_1 \cap A_2 ... \cap A_j )$

This is clearly wrong?

Also why does the face that there are 6 packets being opening not appear in the formula? Surely as you increase the number of packets the probability of having 3 distinct busts should increase?

Answer 1

Let $f_j$ be the indicator function of $A_j$ and $g_k$ that of $n_k$. Write $[n]=\{1,\ldots,n\}$. Then \begin{align} g_k&=\sum_{I:I\subseteq[n]\atop |I|=k} \prod_{j\in I}f_j \prod_{j\notin I}(1-f_j)\\ &=\sum_{I:I\subseteq[n]\atop |I|=k} \sum_{J:I\subseteq J\subseteq[n]}(-1)^{|J|-k}\prod_{j\in J}f_j\\ &=\sum_{J:|J|\subseteq [n]\atop |J|\ge k} (-1)^{|J|-k}\prod_{j\in J}f_j\sum_{I:\subseteq J\atop|I|=k}1\\ &=\sum_{J:|J|\subseteq [n]\atop |J|\ge k} (-1)^{|J|-k}\binom{|J|}k\prod_{j\in J}f_j\\ &=\sum_{m=k}^n(-1)^{m-k}\binom mk\sum_{J:|J|\subseteq [n]\atop |J|=m}\prod_{j\in J}f_j. \end{align} Now take expectation of both sides.

Answer 2

(I realize this is an old question, but posting in case others come here like I did trying to understand the solution.) The connection between Waring's theorem and the stated probability of $N_3$,

$$ \mathbb{P}(N_3) = {5 \choose 3}\alpha_3 - {5 \choose 4}{4 \choose 3}\alpha_4 + {5 \choose 3}\alpha_5\text{,} $$

is as follows. Let $A_i$ be the event that a copy of the the $i$th bust is obtained, $1 \leq i \leq 5$, and for $1 \leq j \leq 5$, let

$$ \alpha_j = \mathbb{P}(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j})\text{,} $$

given six packets purchased. The probability $\alpha_3$ is calculated in exercise 1.3.4, and the other two may be calculated similarly. Then,

$$ \begin{aligned} \mathbb{P}(N_3) &= \sum_{i=0}^{5-3}(-1)^{i}{3+i \choose 3}\sum_{i_1 < i_2 < \cdots < i_{3+i}}\mathbb{P}(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_{3+i}})\\ &= \sum_{i_1 < i_2 < i_3}\alpha_3 - {4 \choose 3}\sum_{i_1 < i_2 < i_3 < i_4}\alpha_4 - {5 \choose 3}\sum_{i_1 < i_2 < i_3 < i_4 < i_5}\alpha_5\\ &= {5 \choose 3}\alpha_3 - {4 \choose 3}{5 \choose 4}\alpha_4 - {5 \choose 3}{5 \choose 5}\alpha_5\\ &= {5 \choose 3}\alpha_3 - {5 \choose 4}{4 \choose 3}\alpha_4 - {5 \choose 3}\alpha_5\text{.}\\ \end{aligned} $$

(The approximation I arrive at is 0.3469 with $\alpha_4 = 3359/15625$ and $\alpha_5 = 72/625$.)