Ideas of Chance in Computer Science 485
introduced in Section 1.3 also help in computing the probability of events (with or without
uniform probability densities).
As a simple example, suppose we know that an event E in a sample space Q is the
disjoint union of two other events A and B. To find the probability of the event E, we sum
up the probabilities of the individual outcomes in E. This can be done by summing the
probabilities of outcomes in A (which gives P (A)), summing the probabilities of outcomes
in B (which gives P(B)), and then adding the two totals together (which gives P(A) +
P(B)). No double counting occurs, because A and B are disjoint. Each outcome in E
contributes its probability, since it belongs either to A or to B. In other words, if A n B =
0, then
P(A U B)= L
wEAUB
= p(,)+ E p(a)
WEA WEB
= P(A) + P(B)
This observation extends to collections of more than two mutually disjoint sets and
gives the Additive Principle of Disjoint Events.
Additive Principle of Disjoint Events
If El, E 2 ... , E, are pairwise disjoint subsets of a sample space Q2, then
P(Ul<,i< Ei) = E P(Ei)
l<i<n
In other words, the probability of a union of pairwise disjoint events is the sum of
their probabilities. This statement remains valid for countably infinite collections of
pairwise disjoint subsets of a countably infinite sample space.
We now use this principle to obtain several useful relationships among the probabilities
of events.
Theorem 1. (Elementary Probability Facts) Let Q be a sample space endowed with
a probability density p, and let E and F be subsets of Q2. Then:
(a) E C F implies P(E) <_ P(F).
(b) P(E) = P(E n F) + P(E n F) where F = Q2 - F.
(c) P(E) = >Ji P(E n Ai) where Q2 = Un=lAi for some n E N and the set of Ai's form
a partition of 02.
(d) P(E U F) = P(E) + P(F) - P(E n F).
Proof.
(a) Since E C F, set F can be written as the disjoint union of E and (F - E). Hence, by
the Additive Principle of Disjoint Events,
P(F) = P(E) + P(F- E)
Since probabilities are nonnegative, P(E) < P(F).
