PROOF 181

Prove.

The birthday problem is counted by the complement

On a probability space.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

What you may use

A1P(X) ≥ 0
non-negativity of probability
A2P(Ω) = 1
probability of the whole
A3disjoint ⟹ P(X∪Y) = P(X)+P(Y)
additivity of probability
A4X ∪ Xᶜ = Ω, X ∩ Xᶜ = ∅
properties of the complement
A5multiply the number of choices at each step
product rule
A6equiprobable ⟹ P(X) = |X|/|Ω|
equiprobability assumption (365 days uniform)
Ea = b ⟹ apply the same operation to both sides
properties of equality
Ncomputation with real numbers is determinate
rules of computation

D1Aᶜ is what is not A
definition of the complementary event
L1P(Aᶜ) = 1 − P(A)
Lemma 1 — complement rule
D2Ω: all birthday assignments
sample space and event
L2|Ω| = 365ⁿ
Lemma 2
L3|Aᶜ| = (365)ₙ
Lemma 3
T1P(Aᶜ) = (365)ₙ / 365ⁿ
Theorem 1
T2P(A) = 1 − (365)ₙ/365ⁿ
Theorem 2

Nothing outside this list may be cited.

Definition D1

For an event A, Aᶜ denotes all outcomes of Ω that do not belong to A.

Proof.

Aᶜ is the event that A does not occur.convention

∎

Lemma L1

For every event A, P(Aᶜ) = 1 − P(A)

Proof.

(1)A ∪ Aᶜ = Ω and A ∩ Aᶜ = ∅.D1, A4

(2)The two events are disjoint, so P(A) + P(Aᶜ) = P(Ω)(1), A3

(3)P(Ω) = 1A2

(4)P(A) + P(Aᶜ) = 1(2), (3)

(5)Subtracting P(A) from both sides gives P(Aᶜ) = 1 − P(A)(4), E

(6)In particular P(Aᶜ) ≥ 0, so P(A) ≤ 1.(5), A1, N

∎

Definition D2

Take a year to have 365 days, and let Ω be the set of all assignments of one birthday to each of n people. Let A be the event that at least two people share a birthday.

Proof.

(1)An outcome is (b₁, …, bₙ), where each bᵢ is one of the 365 days.convention

(2)Therefore Aᶜ is the event that all n birthdays are distinct.(1), D1

∎

Lemma L2

|Ω| = 365ⁿ

Proof.

(1)There are 365 possibilities for b₁.D2

(2)There are n positions, and no position is constrained by the others.D2

(3)Multiplying the number of choices at each step gives |Ω| = 365ⁿ(1), (2), A5

∎

Lemma L3

If n ≤ 365, then |Aᶜ| = 365 · 364 ⋯ (365 − n + 1)

Proof.

(1)Suppose n ≤ 365.assumption

(2)There are 365 possibilities for b₁.D2

(3)b₂ must differ from b₁, so there are 364 possibilities.(2), D2

(4)In the same way, bᵢ must differ from all i−1 preceding ones, so there are 365 − (i−1) possibilities.(1), (3), D2

(5)Multiplying the number of choices at each step gives |Aᶜ| = 365 · 364 ⋯ (365 − n + 1)(2), (3), (4), A5

(6)This product is written (365)ₙ.(5), convention

∎

Theorem T1

If n ≤ 365, then P(Aᶜ) = (365)ₙ / 365ⁿ

Proof.

(1)All outcomes of Ω are equiprobable, so P(Aᶜ) = |Aᶜ| / |Ω|A6

(2)|Aᶜ| = (365)ₙL3

(3)|Ω| = 365ⁿL2

(4)P(Aᶜ) = (365)ₙ / 365ⁿ(1), (2), (3)

∎

Theorem T2

If n ≤ 365, then P(A) = 1 − (365)ₙ / 365ⁿ

Proof.

(1)P(Aᶜ) = 1 − P(A)L1

(2)P(A) = 1 − P(Aᶜ)(1), E

(3)P(Aᶜ) = (365)ₙ / 365ⁿT1

(4)P(A) = 1 − (365)ₙ / 365ⁿ(2), (3)

(5)In Aᶜ each position carries exactly one condition, so the product rule applies directly. In A the pairs sharing a birthday can overlap, so A cannot be counted by a single product.L3, D2, A5

∎

Remark

Can A6 be removed from this proof?

That the 365 days are all equally likely is an assumption of the stage, not an axiom of probability. Remove it and see how much survives.