Page 470 - Discrete Mathematics and Its Applications

7.1 An Introduction to Discrete Probability 449

Probabilities of Complements and Unions of Events

We can use counting techniques to find the probability of events derived from other events.

THEOREM 1 Let E be an event in a sample space S. The probability of the event E = S − E, the comple-
mentary event of E,isgivenby

p(E) = 1 − p(E).

Proof: To find the probability of the event E = S − E, note that |E|=|S|−|E|. Hence,

|S|−|E| |E|
p(E) = = 1 − = 1 − p(E).
|S| |S|

There is an alternative strategy for finding the probability of an event when a direct approach
does not work well. Instead of determining the probability of the event, the probability of its
complement can be found. This is often easier to do, as Example 8 shows.

EXAMPLE 8 A sequence of 10 bits is randomly generated. What is the probability that at least one of these
bits is 0?

Solution: Let E be the event that at least one of the 10 bits is 0. Then E is the event that all the
bits are 1s. Because the sample space S is the set of all bit strings of length 10, it follows that

|E| 1
p(E) = 1 − p(E) = 1 − = 1 −
|S| 2 10
1 1023
= 1 − = .
1024 1024

Hence, the probability that the bit string will contain at least one 0 bit is 1023/1024. It is quite
difficult to find this probability directly without using Theorem 1. ▲

We can also find the probability of the union of two events.

THEOREM 2 Let E 1 and E 2 be events in the sample space S. Then

p(E 1 ∪ E 2 ) = p(E 1 ) + p(E 2 ) − p(E 1 ∩ E 2 ).

Proof: Using the formula given in Section 2.2 for the number of elements in the union of two
sets, it follows that

|E 1 ∪ E 2 |=|E 1 |+|E 2 |−|E 1 ∩ E 2 |.