Twenty-three people are already a crowd

Assume a year has 365 days, every birthday is equally likely, and one person's birthday tells you nothing about another's. Ignore leap day. How many people must enter a room before a shared birthday becomes more likely than not?

The answer feels too small because 23 is being compared with 365. But people are not the collision opportunities. Pairs are. Chapter 7's combination rule counts them:

$$\binom{23}{2} = 253.$$

The room has 253 chances for two birthdays to meet. That observation explains the scale, but adding 253 pair probabilities does not yet give the exact chance of at least one collision. A triple birthday makes three pairs match at once. Naive addition counts such an outcome three times.

Count the event that has only one shape

“At least two birthdays match” has many shapes: one pair, several pairs, a triple, or worse. Its opposite has one clean shape: every birthday is distinct.

The first person may have any birthday. The second must avoid that one date, so 364 of 365 dates remain. The third must avoid two dates, so 363 remain. Continue through the twenty-third person:

$$P(\text{all distinct}) = \frac{365 \times 364 \times 363 \times \cdots \times 343}{365^{23}} \approx 0.4927.$$

Exactly one of two things happens: all birthdays are distinct, or some pair matches. Their probabilities add to one. Therefore

$$P(\text{some match}) = 1 - 0.4927 \approx 0.5073.$$

This is complementary counting: count the side whose description stays simple, then subtract from the whole. The move works whenever an event says “at least one,” “not all,” or “some failure,” and its opposite becomes a single clean invariant.

The number 50.7% belongs to the simplified model, not to every real room. Birthdays are seasonal, populations are not identical, twins violate the independence assumption, and leap day exists. A probability is always conditional on its model, even when the condition is left in the margin.

Add freely, subtract the overlap

Suppose a request is a cache hit when its key appears in a hot index or its response appears in a recent-response table. Forty percent of requests hit the index. Thirty percent hit the table. Ten percent hit both.

Adding 40% and 30% counts the shared 10% twice. Subtract it once:

$$P(A \cup B) = P(A) + P(B) - P(A \cap B) = 0.60.$$

This is the inclusion–exclusion principle. Include the easy pieces, exclude their duplicated intersections, then add back any region that the subtraction removed too often. For many sets the alternating corrections grow long, but the governing bookkeeping never changes: every final outcome must carry coefficient one.

Sometimes exact correction costs more than the decision needs. If the intersections are unknown, stop after addition:

$$P(A \cup B) \le P(A) + P(B).$$

This union bound may count an outcome several times, so it can be too large; it can never be too small. For the 23-person room, adding the 253 pair-match probabilities gives

$$P(\text{some match}) \le \frac{253}{365} \approx 0.693.$$

The true answer is about 0.507. The rough answer is not exact, but it is cheap, safe, and already reveals the square-root scale: the number of pairs grows roughly as the square of the number of people.

Replace one tangled total with many tiny questions

Now ask a different question: not “what is the probability of any collision?” but “how many matching pairs should the room contain on average?”

Attach a switch to every pair of people. The switch is one when that pair shares a birthday and zero otherwise. Such a switch is an indicator variable. If $X_{ij}$ is the switch for people $i$ and $j$, then the total number of matching pairs is the sum of all the switches.

For any fixed pair, the chance of a match is $1/365$. Therefore its expected contribution is $1/365$. There are 253 pairs, so the expected number of matching pairs is

$$\mathrm{E}(X) = \frac{253}{365} \approx 0.693.$$

That is the same arithmetic as the union bound but a different claim. The union bound says the probability of one or more matches is at most 0.693. The expectation says the long-run average number of matching pairs per room is 0.693. A room containing a triple contributes three matching pairs, not one.

Addition does not ask for independence

Why may the expected contributions be added? For two quantities, group complete outcomes by their probabilities. In each outcome, the total contribution is $X+Y$. Distributing the weighted sum gives the weighted average of $X$ plus the weighted average of $Y$:

$$\mathrm{E}(X + Y) = \mathrm{E}(X) + \mathrm{E}(Y).$$

No step multiplied probabilities. Independence is needed for many product rules; it is not needed for this sum rule.

Imagine ten servers controlled by one global coin flip. Heads makes all ten fail; tails makes none fail. The failure indicators are perfectly dependent. Each server still has expected failure contribution one half, so the expected number of failed servers is five:

$$10 \times \frac{1}{2} = 5.$$

This is linearity of expectation. It is one of the rare permissions in probability that becomes stronger when a problem looks more entangled: if the total is a sum, calculate each expected contribution separately and add.

What an average does not promise

An expected value need not be a possible outcome. The ten-server system never has five failed servers; it has zero or ten. Five is the long-run average.

Expectation also does not say outcomes cluster near the average. Two systems can both average five failures while one stays near five and the other swings between zero and ten. To describe spread, tails, or high-confidence capacity, more information is required.

Nor does the birthday calculation transfer unchanged to hashes chosen by an adversary or to a biased generator. The pair probability $1/365$ came from the model. Linearity will add whatever pair probabilities the real model supplies, but it cannot repair false inputs.

Lessons

• Count the complement when the event of interest has many overlapping shapes and its opposite has one clean rule.
• Inclusion–exclusion counts easy pieces first and then repairs duplicated intersections until every outcome is counted once.
• The union bound leaves the overlap uncorrected to obtain a cheap upper bound.
• An indicator variable turns an event into a contribution of zero or one.
• Expected contributions add even when the events are dependent.
• Probability of any collision and expected number of colliding pairs are different questions with different answers.
• Every probability result inherits the assumptions of its sample space and assignment process.

Practice

When the answer contains a smaller answer

Counting so far has moved across a fixed collection: choices, pairs, events, and contributions. But many computations unfold in stages. The number of ways to reach step ten depends on the counts for earlier steps; the running time on an input depends on the running time of smaller inputs.

What if the shortest description of an answer contains a smaller copy of the same answer?

References

1. Lehman, Leighton & Meyer. “Mathematics for Computer Science, §18.5: Linearity of Expectation.” MIT OpenCourseWare, 2015. — source of the epigraph, indicator-variable method, and proof that independence is unnecessary
2. Abel, Chapman & Demaine. “Lecture 18: Introduction to Probability.” MIT OpenCourseWare, 2024. — finite sample spaces, events, probability, and complements
3. Abel, Chapman & Demaine. “Lecture 19: Conditional Probability.” MIT OpenCourseWare, 2024. — sum rule, union bound, and the probability form of inclusion–exclusion
4. Abel, Chapman & Demaine. “Lecture 20: Independence.” MIT OpenCourseWare, 2024. — birthday principle, its assumptions, and square-root collision scaling