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
In a class of people, what is the probability that at least two share a birthday?
Most people's first answer: a year has days and people fill less than a tenth of it, so perhaps .
The true answer is above . 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.
Play first, read later. Drag the group size : 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?
- some two share a day
- exponential bound
- someone shares the first person's day
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.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.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.Simulate only 10 classes: how far is the frequency from the theory? And after 1000 classes?
The curve climbs much faster than the head count, because what can collide is not a "person" but a pair. people form
To turn this guess into something provable, we first need a precise framework.
Definition
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 , we say the event occurs.
Events are sets, so set operations are the logic of events: is " or occurs", is "both occur", is " does not occur". If , the events are mutually exclusive.
Number the people; each birthday is one of the days . An outcome is an ordered -tuple , so
"Some two share a day" is the event
Let be finite or countable. A function assigning a real number to every event is a probability if
- non-negativity: ;
- normalisation: ;
- countable additivity: if are pairwise mutually exclusive, then
.
The pair 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":
If is finite and all outcomes have the same probability, then for every event
In the classical model, a probability question becomes a counting question: how many outcomes does contain?
Theorems and proofs
There are only three axioms, but every everyday rule follows from them.
For all events :
- ;
- ;
- if then ;
.
(1) Take and
With (1), additivity also holds for finitely many exclusive events (pad the list with empty sets).
(2) and are exclusive with union , so .
(3) , an exclusive union, so
(4)
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.
In the classical model ( people, birthdays independent and uniform over days),
Count the outcomes in : the first person's birthday has choices, the second must avoid it and has , ..., the -th has . So
At this is ; at , . The formula is exact but does not show why the answer is in the twenties. Turning the product into an exponential reveals the structure.
For every real , , with equality only at .
Let . Then and , which is positive for and negative for . So has its minimum at . This is the sign of the error when the Taylor expansion of is cut after two terms: the curve always lies above its tangent line.
In particular the probability exceeds at .
Apply the lemma to each factor:
Taking complements gives the inequality. At ,
The exponent is exactly the number of pairs divided by : that is what the conjecture was saying. For probability one half we need , i.e.
"Some two people share a birthday" and "someone shares mine" are different events. The second involves only pairs (me with each other person), with probability
The classical model assumes birthdays are uniform over days; real ones are not (there are seasonal effects). One can prove that, as long as birthdays stay independent and the year has days, the uniform distribution gives the smallest chance of a match among all distributions, for every . 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
A hash function with -bit output has possible values. Replacing "days" by , the same argument shows that trying about
random inputs gives an even chance of two inputs with the same hash. For a -bit hash that is about five billion tries, not . So an -bit hash resists collisions with only bits of strength: -bit security needs a -bit output.
In the plotter, draw , then replace by for other numbers of "days": the shape stays almost the same and stretches horizontally by roughly .
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
✓ All exercises in this section are done.
Next section: Conditioning & Bayes →
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