§3 Probability
§3.1 Notation and set operations
3.1.1 Recall that Ω is a sample space. Consider events A, B ⊂ Ω.
Notation Meaning Examples
A∪B either A or B {1, 2, 3} ∪ {1, 3, 5} = {1, 2, 3, 5}
{x ≤ 1} ∪ {x < 0} = {x ≤ 1}
A∩B both A and B {1, 2, 3} ∩ {1, 3, 5} = {1, 3}
{x ≤ 1} ∩ {x < 0} = {x < 0}
A\B A but not B {1, 2, 3} \ {1, 3, 5} = {2}
{x ≤ 1} \ {x < 0} = {0 ≤ x ≤ 1}
A⊂B A implies B {1, 2} ⊂ {0, 1, 2, 3}, {x < 0} ⊂ {x ≤ 1}
3.1.2 For any event A, “not A” is denoted by Ac (= Ω \ A), the complement of A in Ω.
Example. If Ω = {0, 1, 2, 3, . . .}, {1, 2, 3}c = {0, 4, 5, . . .}.
3.1.3 Denote an “impossible event” by ∅, the empty set.
Note: Ω can be regarded as a “certain” event.
3.1.4 Some useful set operations: (Let A, B, A1 , A2 , . . . be any events in Ω.)
(A1 ∪ A2 ) ∪ A3 = A1 ∪ (A2 ∪ A3 ) (A1 ∩ A2 ) ∩ A3 = A1 ∩ (A2 ∩ A3 )
(A1 ∩ A2 ∩ · · · ) ∪ B = (A1 ∪ B) ∩ (A2 ∪ B) ∩ · · · (A1 ∪ A2 ∪ · · · ) ∩ B = (A1 ∩ B) ∪ (A2 ∩ B) ∪ · · ·
B \ (A1 ∪ A2 ∪ · · · ) = (B \ A1 ) ∩ (B \ A2 ) ∩ · · · B \ (A1 ∩ A2 ∩ · · · ) = (B \ A1 ) ∪ (B \ A2 ) ∪ · · ·
c
(A1 ∪ A2 ∪ · · · ) = Ac1 ∩ Ac2 ∩ ··· (A1 ∩ A2 ∩ · · · )c = Ac1 ∪ Ac2 ∪ · · ·
A \ B = A ∩ Bc
§3.2 Axioms of probability
3.2.1 Definition. A probability on the sample space Ω is an assignment of a non-negative value
P(A) to each event A such that
(i) P(Ω) = 1;
(ii) if A ∩ B = ∅, then P(A ∪ B) = P(A) + P(B);
(iii) if A1 ⊂ A2 ⊂ · · · , then P(A1 ∪ A2 ∪ · · · ) = limn→∞ P(An ).
11
Remarks: The 3 axioms which define “probability” have the following implications.
(i) says that Ω always occurs (since it contains all possible outcomes).
(ii) says that if A and B are mutually exclusive (i.e. A and B CANNOT occur simultaneously),
then the probability that either A or B occurs is the sum of the probabilities of A and B.
(iii) says that if A1 implies A2 , A2 implies A3 etc., then the probability that at least one of the
events A1 , A2 , . . . occurs is the probability of An when n → ∞.
3.2.2 “Combinatorial probability” assumes that Ω is a finite set and that for any ω ∈ Ω,
1
P({ω}) = .
no. of outcomes in Ω
We can verify easily that “combinatorial probability” satisfies the 3 axioms in §3.2.1 and is
therefore a special case of “probability”.
3.2.3 A few useful facts: (Let A, B, A1 , A2 , . . . be any events in Ω.)
P(Ac ) = 1 − P(A) P(∅) = 0
P(B) = P(B ∩ A) + P(B \ A) A ⊂ B ⇒ P(A) ≤ P(B)
P(A ∪ B) = P(A) + P(B) − P(A ∩ B) P(A ∪ B) ≤ P(A) + P(B)
P(A1 ∪ A2 ∪ · · · ) ≤ P(A1 ) + P(A2 ) + · · ·
§3.3 Inclusion-Exclusion Formula
3.3.1 Theorem. For any events A1 , A2 , . . . , An ,
n
X X
P(A1 ∪ A2 ∪ · · · ∪ An ) = (−1)j−1 P(Ai1 ∩ Ai2 ∩ · · · ∩ Aij ).
j=1 i1 <i2 <···<ij
3.3.2 Example. For n = 4,
P(A1 ∪ A2 ∪ A3 ∪ A4 )
= P(A1 ) + P(A2 ) + P(A3 ) + P(A4 )
− P(A1 ∩ A2 ) + P(A1 ∩ A3 ) + P(A1 ∩ A4 ) + P(A2 ∩ A3 ) + P(A2 ∩ A4 ) + P(A3 ∩ A4 )
+ P(A1 ∩ A2 ∩ A3 ) + P(A1 ∩ A2 ∩ A4 ) + P(A1 ∩ A3 ∩ A4 ) + P(A2 ∩ A3 ∩ A4 )
− P(A1 ∩ A2 ∩ A3 ∩ A4 ).
12
3.3.3 Example. (Umbrella problem)
N people go to a party on a rainy night. At the end of party, people take their umbrellas at
random. What is the probability that no one gets the right umbrella?
Solution:
Let Ai be the event that guest i gets his/her umbrella correctly. Then the probabilty that at least 1
guest gets the right umbrella is
N
X X
P(A1 ∪ A2 ∪ · · · ∪ AN ) = (−1)j−1 P(Ai1 ∩ Ai2 ∩ · · · ∩ Aij ).
j=1 i1 <i2 <···<ij
By symmetry,
P(Ai1 ∩ Ai2 ∩ · · · ∩ Aij )
= P(A1 ∩ A2 ∩ · · · ∩ Aj )
= P(guests 1, 2, . . . , j get correct umbrellas)
No. of ways of allocating N umbrellas with guests 1 to j getting correct ones
=
No. of ways of allocating N umbrellas
(N − j)!
= .
N!
There are Nj different combinations of i1 , . . . , ij so that i1 <i2 <···<ij has Nj terms.
P
Thus
N XN
j−1 (N − j)! N 1
X
P(A1 ∪ A2 ∪ · · · ∪ AN ) = (−1) = (−1)j−1
N! j j!
j=1 j=1
1 1 1
= 1 − + − · · · + (−1)N −1 .
2! 3! N!
Hence
P(no one gets correct umbrella) = 1 − P(A1 ∪ A2 ∪ · · · ∪ AN )
X (−1)j N
1 1 1
= − + · · · + (−1)N = .
2! 3! N! j!
j=0
Note that the above answer → e−1 as N → ∞.
3.3.4 Exercise. Find the probability that exactly k people get correct umbrellas.
13
