Consider n independent trials in which each trial results in one of the outcomes 1, . . . , k with respective probabilities p1, . . . , pk,

ki

=1 pi = 1.

Suppose further that n > k, and that we are interested in determining the probability that each outcome occurs at least once. If we let Ai denote the event that outcome i does not occur in any of the n trials, then the desired probability is 1−P(

ki

=1 Ai), and it can be obtained by using the inclusion–exclusion theorem as follows:

Transcribed Image Text:

k P (A) = P(A)- P(A) - P(AA) i=1 i j>i + P(AAA) + (-1)+1 P(AAk) - i f>i k>j