Inclusion/Exclusion in Probability

[TranscendArcu]

Homework Statement

Homework Equations

The Attempt at a Solution

I've done part b) so I only want to talk about part a). So I said, let E_i be the event that I do not get the kth players card. It seems logical that the union of all the E-complements should be one.

Theorem 3.8 clearly makes use of intersections, so I'll compute for any k failures to get pictures $P(E_1 \cap E_2 \cap ... \cap E_k) = (\frac{n-k}{n})^m$ given that I buy m boxes of cereal. I have $_n C_k$ ways of failing to pick some k number of pictures. Thus, following the " subtract the probabilities of all possible two-way intersections, add the probability of all three-way intersections"-principle of Theorem 3.8, I can write as the k's vary:

$1 - (_n C _1)(\frac{n-1}{n})^m + (_n C _2)(\frac{n-2}{n})^m - (_n C _3)(\frac{n-3}{n})^m + ... + (-1)^{n-1}(_n C _{n-1})(\frac{1}{n})^m$

Note that the nth term would go to zero.

So how does it look?

 

[Ray Vickson]

Homework Statement

Homework Equations

The Attempt at a Solution

I've done part b) so I only want to talk about part a). So I said, let E_i be the event that I do not get the kth players card. It seems logical that the union of all the E-complements should be one.

Theorem 3.8 clearly makes use of intersections, so I'll compute for any k failures to get pictures $P(E_1 \cap E_2 \cap ... \cap E_k) = (\frac{n-k}{n})^m$ given that I buy m boxes of cereal. I have $_n C_k$ ways of failing to pick some k number of pictures. Thus, following the " subtract the probabilities of all possible two-way intersections, add the probability of all three-way intersections"-principle of Theorem 3.8, I can write as the k's vary:

$1 - (_n C _1)(\frac{n-1}{n})^m + (_n C _2)(\frac{n-2}{n})^m - (_n C _3)(\frac{n-3}{n})^m + ... + (-1)^{n-1}(_n C _{n-1})(\frac{1}{n})^m$

Note that the nth term would go to zero.

So how does it look?

Easier: Let $E_i = \{ \text{ do not get card } i \}, i=1,2, \ldots,n$ in m boxes. You want to compute $1-P\{ E_1 \cup E_2 \cup \cdots \cup E_n \}.$ For each i we have that E_i occurs if fail m times to obtain card i, which means that
$$P\{E_i\} = \left(\frac{n-1}{n}\right)^m, i=1,2, \ldots, n.$$ For any $i \neq j$ the event $E_i \cap E_j$ occurs if in m purchases we always obtain one of the other (n-2) cards, so
$$P\{ E_i \cap E_j\} = \left( \frac{n-1}{n}\right)^m, i \leq i < j \leq n,$$
etc.

RGV

 

[Ray Vickson]

My guess would be that part (b) is much more difficult, since for large m and n the computation using the formula in (a) would be subject to extreme roundoff-error effects. Possibly formula (a) should be regarded as useless for computational purposes! Of course, if you use several hundred to several thousand digits of precision, that would get around the problem, but barring that, an iterative approach is probably better, (or any approach that avoids subtractions of large or similarly-sized terms).

RGV