2Axioms of probability
IA Probability
2.2 Inequalities and formulae
Theorem (Boole’s inequality). For any A
1
, A
2
, ···,
P
∞
[
i=1
A
i
!
≤
∞
X
i=1
P(A
i
).
This is also known as the “union bound”.
Proof.
Our third axiom states a similar formula that only holds for disjoint sets.
So we need a (not so) clever trick to make them disjoint. We define
B
1
= A
1
B
2
= A
2
\ A
1
B
i
= A
i
\
i−1
[
k=1
A
k
.
So we know that
[
B
i
=
[
A
i
.
But the B
i
are disjoint. So our Axiom (iii) gives
P
[
i
A
i
!
= P
[
i
B
i
!
=
X
i
P (B
i
) ≤
X
i
P (A
i
) .
Where the last inequality follows from (iii) of the theorem above.
Example. Suppose we have countably infinite number of biased coins. Let
A
k
= [
k
th toss head] and
P
(
A
k
) =
p
k
. Suppose
P
∞
1
p
k
< ∞
. What is the
probability that there are infinitely many heads?
The event “there is at least one more head after the
i
th coin toss” is
S
∞
k=i
A
k
.
There are infinitely many heads if and only if there are unboundedly many coin
tosses, i.e. no matter how high
i
is, there is still at least more more head after
the ith toss.
So the probability required is
P
∞
\
i=1
∞
[
k=i
A
k
!
= lim
i→∞
P
∞
[
k=i
A
k
!
≤ lim
i→∞
∞
X
k=i
p
k
= 0
Therefore P(infinite number of heads) = 0.
Example (Erd¨os 1947). Is it possible to colour a complete
n
-graph (i.e. a graph
of
n
vertices with edges between every pair of vertices) red and black such that
there is no k-vertex complete subgraph with monochrome edges?
Erd¨os said this is possible if
n
k
2
1−
(
k
2
)
< 1.
We colour edges randomly, and let
A
i
= [
i
th subgraph has monochrome edges].
Then the probability that at least one subgraph has monochrome edges is
P
[
A
i
≤
X
P(A
i
) =
n
k
2 · 2
−
(
k
2
)
.
The last expression is obtained since there are
n
k
ways to choose a subgraph; a
monochrome subgraph can be either red or black, thus the multiple of 2; and
the probability of getting all red (or black) is 2
−
(
k
2
)
.
If this probability is less than 1, then there must be a way to colour them in
which it is impossible to find a monochrome subgraph, or else the probability is
1. So if
n
k
2
1−
(
k
2
)
< 1, the colouring is possible.
Theorem (Inclusion-exclusion formula).
P
n
[
i
A
i
!
=
n
X
1
P(A
i
) −
X
i
1
<i
2
P(A
i
1
∩ A
j
2
) +
X
i
1
<i
2
<i
3
P(A
i
1
∩ A
i
2
∩ A
i
3
) − ···
+ (−1)
n−1
P(A
1
∩ ··· ∩ A
n
).
Proof. Perform induction on n. n = 2 is proven above.
Then
P(A
1
∪ A
2
∪ ···A
n
) = P(A
1
) + P(A
2
∪ ··· ∪ A
n
) − P
n
[
i=2
(A
1
∩ A
i
)
!
.
Then we can apply the induction hypothesis for
n −
1, and expand the mess.
The details are very similar to that in IA Numbers and Sets.
Example. Let 1
,
2
, ··· , n
be randomly permuted to
π
(1)
, π
(2)
, ··· , π
(
n
). If
i = π(i) for all i, we say we have a derangement.
Let A
i
= [i = π(i)].
Then
P
n
[
i=1
A
i
!
=
X
k
P(A
k
) −
X
k
1
<k
2
P(A
k
1
∩ A
k
2
) + ···
= n ·
1
n
−
n
2
1
n
1
n − 1
+
n
3
1
n
1
n − 1
1
n − 2
+ ···
= 1 −
1
2!
+
1
3!
− ··· + (−1)
n−1
1
n!
→ e
−1
So the probability of derangement is 1 − P(
S
A
k
) ≈ 1 − e
−1
≈ 0.632.
Recall that, from inclusion exclusion,
P(A ∪ B ∪ C) = P(A) + P(B) + P(C) − P(AB) − P(BC) − P(AC) + P(ABC),
where
P
(
AB
) is a shorthand for
P
(
A ∩ B
). If we only take the first three terms,
then we get Boole’s inequality
P(A ∪ B ∪ C) ≤ P(A) + P(B) + P(C).
In general
Theorem (Bonferroni’s inequalities). For any events
A
1
, A
2
, ··· , A
n
and 1
≤
r ≤ n, if r is odd, then
P
n
[
1
A
i
!
≤
X
i
1
P(A
i
1
) −
X
i
1
<i
2
P(A
i
1
A
i
2
) +
X
i
1
<i
2
<i
3
P(A
i
1
A
i
2
A
i
3
) + ···
+
X
i
1
<i
2
<···<i
r
P(A
i
1
A
i
2
A
i
3
···A
i
r
).
If r is even, then
P
n
[
1
A
i
!
≥
X
i
1
P(A
i
1
) −
X
i
1
<i
2
P(A
i
1
A
i
2
) +
X
i
1
<i
2
<i
3
P(A
i
1
A
i
2
A
i
3
) + ···
−
X
i
1
<i
2
<···<i
r
P(A
i
1
A
i
2
A
i
3
···A
i
r
).
Proof. Easy induction on n.
Example. Let Ω =
{
1
,
2
, ··· , m}
and 1
≤ j, k ≤ m
. Write
A
k
=
{
1
,
2
, ··· , k}
.
Then
A
k
∩ A
j
= {1, 2, ··· , min(j, k)} = A
min(j,k)
and
A
k
∪ A
j
= {1, 2, ··· , max(j, k)} = A
max(j,k)
.
We also have P(A
k
) = k/m.
Now let 1
≤ x
1
, ··· , x
n
≤ m
be some numbers. Then Bonferroni’s inequality
says
P
[
A
x
i
≥
X
P(A
x
i
) −
X
i<j
P(A
x
i
∩ A
x
j
).
So
max{x
1
, x
2
, ··· , x
n
} ≥
X
x
i
−
X
i
1
<i
2
min{x
1
, x
2
}.