LeoMath

Foundations of probability · Section 1 of 3

Probability spaces

Sample space, events and three axioms; why the birthday problem defies intuition.

about 12 min

Start from a problem

Problem

In a class of 30 people, what is the probability that at least two share a birthday?

Most people's first answer: a year has 365 days and 30 people fill less than a tenth of it, so perhaps 8%.

The true answer is above 70%. An intuition this far off means we have not yet said what "probability" is computing: what are all the possible outcomes? Which part of them is "some two share a day"? By what rule do chances add up? The answers to these three questions, taken together, are a probability space.

Observe

Play first, read later. Drag the group size n: the black curve is the theoretical probability. Then press "Simulate" to draw a whole class's birthdays at random; the red dot is the frequency so far. At what size does the probability first pass one half?

Interactive experimentThe birthday problem
  • some two share a day
  • exponential bound1−e−n(n−1)/730
  • someone shares the first person's day
1−365⋅364⋯(365−n+1)365npairs 253exact 0.507297exponential bound 0.500002someone shares the first person's day 0.058571
classes simulated 0with a shared day 0frequency —

Experiment idea from: github.com/huzhuofan1020-svg/GDGX

What did you observe?Play first, then answer. Read the explanation only after you have thought it through.

  1. 1.Drag the group size from 10 to 60. Where does the curve rise fastest? From how many people on is the probability above one half?
  2. 2.At n = 23 “some two share a day” is about 50%, yet “someone shares the first person's day” is only about 6%. What is the difference?
  3. 3.Simulate only 10 classes: how far is the frequency from the theory? And after 1000 classes?
Conjecture

The curve climbs much faster than the head count, because what can collide is not a "person" but a pair. n people form (n2)=n(n−1)2 pairs; 23 people already make 253 pairs, each matching with chance 1365. Pairs grow like n2, so we need nowhere near 365 people: twenty-odd will do.

To turn this guess into something provable, we first need a precise framework.

Definition

Definition 1.1Sample space and events

The set Ω of all possible outcomes of a random experiment is its sample space; its elements ω are outcomes. Subsets of Ω are events. When the outcome ω lies in A, we say the event A occurs.

Events are sets, so set operations are the logic of events: A∪B is "A or B occurs", A∩B is "both occur", Ac=Ω∖A is "A does not occur". If A∩B=⌀, the events are mutually exclusive.

Example 1.1The sample space of the birthday problem

Number the n people; each birthday is one of the days {1,…,365}. An outcome is an ordered n-tuple ω=(d1,…,dn), so

Ω={1,…,365}n,|Ω|=365n.

"Some two share a day" is the event A={ω: di=dj for some i≠j}; its complement Ac is "the n birthdays are all different".

Definition 1.2Probability (Kolmogorov's axioms)

Let Ω be finite or countable. A function P assigning a real number P(A) to every event A⊆Ω is a probability if

  1. non-negativity: P(A)≥0;
  2. normalisation: P(Ω)=1;
  3. countable additivity: if A1,A2,… are pairwise mutually exclusive, then P(⋃iAi)=∑iP(Ai).

The pair (Ω,P) is then a probability space.

The axioms say what a probability satisfies, not what any particular event's probability is. The numbers come from a model. The simplest model is "every outcome is equally likely":

Definition 1.3Classical probability

If Ω is finite and all outcomes have the same probability, then for every event A

P(A)=|A||Ω|.

In the classical model, a probability question becomes a counting question: how many outcomes does A contain?

Theorems and proofs

There are only three axioms, but every everyday rule follows from them.

Theorem 1.1Basic properties of probability

For all events A,B:

  1. P(⌀)=0;
  2. P(Ac)=1−P(A);
  3. if A⊆B then P(A)≤P(B);
  4. P(A∪B)=P(A)+P(B)−P(A∩B).
Proof

(1) Take A1=Ω and A2=A3=⋯=⌀. They are pairwise exclusive, so countable additivity gives P(Ω)=P(Ω)+∑i≥2P(⌀), hence ∑i≥2P(⌀)=0; every term is non-negative, so P(⌀)=0.

With (1), additivity also holds for finitely many exclusive events (pad the list with empty sets).

(2) A and Ac are exclusive with union Ω, so P(A)+P(Ac)=P(Ω)=1.

(3) B=A∪(B∖A), an exclusive union, so P(B)=P(A)+P(B∖A)≥P(A).

(4) A∪B=A∪(B∖A) and B=(A∩B)∪(B∖A) are both exclusive unions. Hence P(A∪B)=P(A)+P(B∖A)=P(A)+P(B)−P(A∩B).

Property (2) looks trivial, yet it is the key to the birthday problem. "Some two share a day" splits into many cases (two match, three match, two separate pairs match, ...), while its complement "all different" is a single case and far easier to count.

Proposition 1.2The birthday problem

In the classical model (n≤365 people, birthdays independent and uniform over 365 days),

P(some two share a day)=1−365⋅364⋯(365−n+1)365n=1−∏k=1n−1(1−k365).
Proof

Count the outcomes in Ac: the first person's birthday has 365 choices, the second must avoid it and has 364, ..., the n-th has 365−n+1. So |Ac|=365⋅364⋯(365−n+1). The classical model gives P(Ac)=|Ac|/365n, and property (2) gives P(A)=1−P(Ac). The second equality just writes each factor as 365−k365=1−k365.

At n=23 this is 0.5073; at n=30, 0.7063. The formula is exact but does not show why the answer is in the twenties. Turning the product into an exponential reveals the structure.

Lemma 1.31 − x ≤ e^{−x}

For every real x, 1−x≤e−x, with equality only at x=0.

Proof

Let g(x)=e−x−(1−x). Then g(0)=0 and g′(x)=1−e−x, which is positive for x>0 and negative for x<0. So g has its minimum 0 at x=0. This is the sign of the error when the Taylor expansion of e−x is cut after two terms: the curve always lies above its tangent line.

Corollary 1.4Twenty-three people are enough
P(some two share a day) ≥ 1−exp⁡(−n(n−1)2⋅365).

In particular the probability exceeds 12 at n=23.

Proof

Apply the lemma to each factor: 1−k365≤e−k/365. All factors are positive, so multiplying gives

∏k=1n−1(1−k365)≤exp⁡(−1+2+⋯+(n−1)365)=exp⁡(−n(n−1)730).

Taking complements gives the inequality. At n=23, 23⋅22730=506730≈0.693151>ln⁡2≈0.693147, so the right-hand side exceeds 1−12=12.

The exponent is exactly the number of pairs (n2) divided by 365: that is what the conjecture was saying. For probability one half we need (n2)≈365ln⁡2, i.e. n≈2⋅365ln⁡2≈22.5. The group only needs to be on the order of the square root of the number of days.

Common mistake

"Some two people share a birthday" and "someone shares mine" are different events. The second involves only n−1 pairs (me with each other person), with probability 1−(364365)n−1: about 5.9% at n=23, and it takes 253 people besides me to pass one half. The intuitive 8% is really an answer to the second question. In the experiment, compare the dotted curve with the black one: near n=23 it is almost ten times lower.

Remark

The classical model assumes birthdays are uniform over 365 days; real ones are not (there are seasonal effects). One can prove that, as long as birthdays stay independent and the year has 365 days, the uniform distribution gives the smallest chance of a match among all distributions, for every n. So within this model the numbers above are lower bounds, and the conclusion only gets stronger. (Twins break independence and February 29 adds a day; neither is in the model.)

Applications

ApplicationHash collisions and the birthday attack

A hash function with m-bit output has d=2m possible values. Replacing "days" by d, the same argument shows that trying about

n≈2dln⁡2≈1.18⋅2m/2

random inputs gives an even chance of two inputs with the same hash. For a 64-bit hash that is about five billion tries, not 264. So an m-bit hash resists collisions with only m/2 bits of strength: 128-bit security needs a 256-bit output.

Try it in the plotter →

In the plotter, draw 1−exp⁡(−x(x−1)/730), then replace 730 by 2d for other numbers of "days": the shape stays almost the same and stretches horizontally by roughly d/365.

Remark

This section only needed counting outcomes. In many problems, though, we first learn something and then ask for a probability: given a positive test, how likely is the disease? New information changes the sample space. That is the question of the next section, conditional probability and Bayes' theorem.

Birthday-problem experiment idea from: github.com/huzhuofan1020-svg/GDGX

Exercises

0 of 4 done

1
Roll two fair dice. What is the probability that the sum is 7? (A fraction is fine.)

Decimals or fractions; anything within 0.001 of the answer counts as correct.

2
Given P(A)=0.5, P(B)=0.4 and P(A∪B)=0.7, find P(A∩B).

Enter the exact value; a fraction such as 1/3 is fine.

3
What is the probability that among 3 people at least two share a birthday? (Uniform over 365 days; four decimals.)

Decimals or fractions; anything within 0.00006 of the answer counts as correct.

4
In a class of 23 that includes you, the probability that someone shares your birthday is about
Answer to exercise 4

Discussion

Found a mistake, have a question or a suggestion? You can also write to 620026600@qq.com

No comments yet. Share your understanding, ask a question, or point out an error on this page.

Log in to join the discussion