Inclusion/Exclusion in Probability

  • Thread starter TranscendArcu
  • Start date
  • Tags
    Probability
In summary, for a problem in which you want to know the probability of obtaining any given card if you buy a box of cereal, Theorem 3.8 provides a way to do the calculation using intersections of the cards. The nth term in this equation goes to zero as n gets large, meaning that the equation can be effectively solved for any k.
  • #1
TranscendArcu
285
0

Homework Statement



Screen_shot_2012_04_08_at_11_50_00_AM.png


Homework Equations



Screen_shot_2012_04_09_at_8_01_34_AM.png


The Attempt at a Solution


I've done part b) so I only want to talk about part a). So I said, let Ei 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 [itex]P(E_1 \cap E_2 \cap ... \cap E_k) = (\frac{n-k}{n})^m[/itex] given that I buy m boxes of cereal. I have [itex]_n C_k[/itex] 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:

[itex]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[/itex]

Note that the nth term would go to zero.

So how does it look?
 
Physics news on Phys.org
  • #2
TranscendArcu said:

Homework Statement



Screen_shot_2012_04_08_at_11_50_00_AM.png


Homework Equations



Screen_shot_2012_04_09_at_8_01_34_AM.png


The Attempt at a Solution


I've done part b) so I only want to talk about part a). So I said, let Ei 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 [itex]P(E_1 \cap E_2 \cap ... \cap E_k) = (\frac{n-k}{n})^m[/itex] given that I buy m boxes of cereal. I have [itex]_n C_k[/itex] 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:

[itex]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[/itex]

Note that the nth term would go to zero.

So how does it look?

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

RGV
 
  • #3
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
 

1. What is the difference between inclusion and exclusion in probability?

Inclusion and exclusion are two principles in probability that are used to calculate the probability of events. Inclusion refers to the principle of including all possible outcomes in a given event, while exclusion refers to the principle of excluding certain outcomes from the event.

2. How do you calculate the probability using the inclusion-exclusion principle?

To calculate the probability using the inclusion-exclusion principle, you first calculate the probability of each individual event. Then, you subtract the sum of the probabilities of all the events from the probability of the union of all the events. This gives you the probability of the event occurring at least once.

3. What is the formula for the inclusion-exclusion principle?

The inclusion-exclusion principle can be represented by the formula P(A or B) = P(A) + P(B) - P(A and B), where P(A) and P(B) are the probabilities of events A and B, and P(A and B) is the probability of both events occurring simultaneously. This formula can be extended to any number of events.

4. What is the purpose of using the inclusion-exclusion principle in probability?

The inclusion-exclusion principle is used to calculate the probability of events that are not mutually exclusive. It allows us to account for all possible outcomes and adjust for any overlap between events, providing a more accurate probability calculation.

5. Can the inclusion-exclusion principle be used for non-binary events?

Yes, the inclusion-exclusion principle can be used for non-binary events, meaning events with more than two possible outcomes. The formula can be expanded to include all possible combinations of events and their probabilities.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
117
  • Calculus and Beyond Homework Help
Replies
6
Views
421
Replies
1
Views
533
  • Calculus and Beyond Homework Help
Replies
2
Views
660
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
358
  • Calculus and Beyond Homework Help
Replies
4
Views
604
  • Calculus and Beyond Homework Help
Replies
1
Views
90
Back
Top