04When "At Least One" Explodes

A room needs only 23 people before two of them very probably share a birthday. That is the most famous shock in the subject, and one subtraction is all it takes to crack it. Here is the subtraction. Last chapter ended with a small tool we almost threw away as bookkeeping: the complement rule, P(Aᶜ) = 1 − P(A). It fell straight out of the three axioms in a single line, and it looked like nothing. This chapter is where that one line does something close to magic. The setup is a trap you have fallen into before. The moment a question starts with the words “at least one,” a beginner tries to add up cases — at least one this, or at least one that — and immediately drowns. The cases overlap, the overlaps have their own overlaps, and the whole thing becomes a sum with 2ⁿ−1 tangled terms. But “at least one” has an opposite that is almost always a single, clean, multiply-it-out thing: “none.” So leave the tangle alone. Compute the easy opposite instead, then subtract it from 1. That is the whole move: P(at least one) = 1 − P(none). Aimed at a room of people it returns 23, which feels impossible and is not. By the end you will see the exact reason 23 fools everyone: your gut counts people when the maths counts pairs, and pairs grow quadratically. No magic — just one subtraction, aimed well.

01The line that does all the work

Let's stand exactly where we left off. Every event phrased “at least one” has a complement that is always the same tidy phrase: “none.” That is the hinge of the whole chapter, and it comes from one line of Chapter 3. There we watched P(Aᶜ) = 1 − P(A) fall out of the axioms. An event and its complement are disjoint, and together they fill Ω, so their two probabilities add to 1. Rearrange that and you have the rule. We filed it away as obvious. Now look at the kind of problem where it stops being obvious and turns powerful: at least one head, at least one six, at least one shared birthday. Split the sample space into those two territories below and read the identity straight off. Whatever weight is not in “none” must be in “at least one,” so the two always sum to 1.

Figure 1 split Ω into two territories, but only in the abstract. Make the messy side something you can count on your fingers. Flip a coin three times and there are eight outcomes. Exactly one of them, TTT, has no heads. The other seven all count as at least one head, and those seven scatter across exactly-one, exactly-two, and exactly-three. That scatter is what the complement lets you skip. Subtract the single none from 1 and you are done.

The identity is just the complement rule wearing a costume: P(at least one) = 1 − P(none). Nothing new arrived — it is the same one line from last chapter. What matters is not the algebra. It is which side of the equals sign is easy to compute, and the two sides are nowhere near equal in effort. To feel that difference, try computing the hard side head-on for a moment and watch it explode.

Eight servers that might each time out force the direct road into 255 separate terms. The complement needs one. Here is where that gap comes from. Say you have n separate things that could each “happen” — n servers that could each time out, n dice that could each show a six — and you want the chance that at least one does. The direct way forces you into inclusion–exclusion. Add the chance each one happens. Subtract every pair you double-counted. Add back every triple, and so on. Crank n below and watch the number of terms in that alternating sum blow up as 2ⁿ−1, hitting that count at n=8. Next to it sits the complement, which stays a single term the whole time.

The skill here is not memorizing a formula. It is the reflex to flip the question the instant you see “at least one,” and reach for “none.” The figure makes the reason plain. The direct road grows exponentially in bookkeeping. The complement road stays a one-liner, however large n gets. So let's earn that reflex on the simplest possible case before we aim it at anything hard.

Roll a fair die k times. What is the chance of at least one six? Head-on that is “a six on roll 1, or roll 2, or…” — the overlapping tangle again. Flipped, it is clean. “none” means every single roll misses, and each single roll misses with probability 5/6. Drag k and watch (5/6)ᵏ, the chance of a clean miss every time, shrink while 1 − (5/6)ᵏ climbs. Guess first: how many rolls before you are past 50%?

The real test is whether your own hand reaches for the flip unprompted. You have watched it happen three times now, always done for you. Here are fresh at least one problems with no worked answer attached. For each one, build the “none” side yourself, then read off 1 − P(none). Guess wrong and the widget shows you exactly which factor you missed.

Four rolls of the die already make you a favourite to have seen a six: 1 − (5/6)⁴ ≈ 0.52. That surprises almost everyone, because most people guess six rolls or ten. Notice what made the calculation easy. “None” was a product of identical, independent misses, one factor per roll. That product is the real engine of the chapter. So let's understand exactly why “none” always multiplies into one clean term.

02Why "none" is one clean product

Here is the mechanism, from the ground up. “None” is a chain of “ands”: no six on roll 1, and none on roll 2, and none on roll 3… When the trials do not influence each other — when they are independent — the probability of that chain of ands is simply the product of the pieces. Each new trial that still fails tacks one more factor onto the running product. There is nothing to add, nothing to subtract, and no overlaps to police. Step through the build below and watch “none” grow one clean factor at a time.

One factor per trial — that is exactly why the complement side never tangles. But the die example had independent rolls with a fixed 5/6 miss chance every time. The birthday problem is subtler, and it is subtle in a way you have already met. In the birthday problem the “misses” get harder as you go. That is the tell for a mechanism we built two chapters ago.

Line up n people and ask for the chance their birthdays are all distinct — the “none share” case. Person 1 can have any of 365 days, so person 1 gets a free pass at 365/365. Person 2 must dodge the one day already taken, leaving 364/365. Person 3 must dodge two taken days, leaving 363/365. So the pool of safe days depletes by one with every person who walks in. That is exactly sampling without replacement from Chapter 2, the depleting deck of cards walking back on stage. Step a person in at a time and watch the product assemble.

So “all distinct” is the product (365/365)·(364/365)·(363/365)·…, one shrinking factor per person. It is the same depleting-pool count we already trust, run with 365 calendar slots instead of 52 cards. And the event we actually want is its complement: P(at least two share) = 1 − P(all distinct). That is the complete recipe. Now let's turn the crank and meet the shock everyone warns you about.

03The birthday problem

Before you touch the figure, commit to a number out loud if you can. Being wrong is what rewires the intuition. A room fills with people. How many do you need before it is more likely than not that some two of them share a birthday? Most people answer with a big fraction of 365 — 180, maybe, half the calendar. Hold your guess. Now drag n from 1 to 60 and watch the two curves. P(all distinct) slides down, and P(at least two share) climbs up. Find where they cross the 50% line.

Twenty-three. Not 180 — 23. At 23 people the chance that some two of them share a birthday is already ≈ 0.507, a hair over half. By 57 people that same chance is above 99%, near-certain in a crowd that would not fill a bus. This is genuinely one of the great counter-intuitive results in the subject, and your disbelief right now is the healthy reaction. So let's make the result concrete before we explain it. Drop 23 actual people onto a calendar and see the collision happen with your own eyes.

Watching a single room is persuasive but anecdotal, because one collision could be a fluke. The honest way to trust a probability is to run it many times and let the empirical fraction settle. That is exactly what a computer is for. Below we fill a room with 23 random birthdays, check for a shared one, and repeat that whole experiment 100,000 times. Predict where the running fraction lands, then run it.

The simulated fraction homes in on 0.507 — the same value the formula gave. That agreement is the whole point of checking analytic maths against a Monte-Carlo. Two roads, one number, and now you believe it. But believing is not understanding. Why does 23 do it? The answer is the best idea in the chapter, and once you see it you can never un-see it.

04Pairs, not people

Here is the trap, named plainly. When you imagine “someone sharing my birthday,” you picture yourself checking against everyone else — 22 comparisons for you in a room of 23. That count is linear: add a person, add one comparison. If linear were the real count, your intuition would be right and you would need a crowd. But the event is not “someone shares mine.” It is “any two people at all share.” So what actually matters is the number of pairs. Pairs are a choose-two count, C(n,2) = n(n−1)/2, and that grows like n²/2 — quadratically. Slide n and watch every pair drawn as a chord. Count how fast the chords pile up.

Each newcomer brings more new pairs than the last one did, and a count whose steps keep growing is exactly what quadratic means. Watch why. A single person walks into the room and shakes hands with everyone already there, so the new pairs they add equals the size of the crowd they joined. The tenth person to arrive adds nine pairs. The twenty-third adds twenty-two. That is the chords piling up faster than the people did.

At 23 people there are C(23,2) = 253 pairs. That is 253 separate little chances for a collision, hiding in a room your gut insists is tiny. That is the whole illusion. You counted people (23) and the maths counted pairs (253). Let's put the two counts side by side so the gap is unmissable: the linear “me vs everyone” fan against the full “everyone vs everyone” web.

The web dwarfs the fan the moment n gets past a handful, because n²/2 outruns n and never looks back. Now we can close the loop with a lovely piece of arithmetic. Each of the 253 pairs shares a birthday with probability 1/365, so the expected number of colliding pairs in a room of 23 is 253/365 ≈ 0.69. Watch that expected-collision count climb with n. See it pass the magic value of about ln 2 ≈ 0.69 right as the share probability crosses 50%.

That is not a coincidence. It is the deep reason 23 is the answer. When rare events each have a tiny chance and there are many of them, their count follows a Poisson process, which we will build properly later. Poisson gives P(at least one) ≈ 1 − e^(−E), where E is the expected number of collisions. Set that probability to 1/2 and you need E = ln 2 ≈ 0.69 expected collisions. And n(n−1)/2 · (1/365) reaches 0.69 right at n = 23. The pairs were the engine all along. Now for one unglamorous but essential skill before we generalize: actually computing these products without your machine catching fire.

05Doing the arithmetic without melting

The clean way to write “all distinct” is a ratio of factorials: 365! / (365−n)! / 365ⁿ. That expression is correct, and it is a trap to compute literally. 365! is a number with 779 digits, vastly larger than any normal floating-point value can hold. Ask a computer for that factorial as a float and it does not return a wrong answer. It overflows and dies. Watch the naive factorial route detonate below, right next to the fix.

Figure 15 showed the naive route crashing, but not the wall it hits. That wall has a number: a float64 can hold values up to about 1.8 × 10³⁰⁸, and no higher. Build 365! by multiplying 1 × 2 × 3 × … and watch the running value climb toward that ceiling. Predict the exact factor where it punches through and turns to infinity. The reordered route never even nears the wall, because every partial result stays the size of the answer itself.

The repair is a numerical-literacy habit worth carrying everywhere: never build the giant intermediate. Accumulate the answer one factor at a time instead. Start a running probability at 1.0 and multiply it by (365−k)/365 for each person k. Every partial result is itself a valid probability sitting politely in [0,1], so nothing ever grows large enough to overflow. Same maths, told in an order the machine can survive. Step the loop and watch the running product stay tame.

One running number, always between 0 and 1, landing on 0.4927 at n=23 — and no 779-digit monster ever built. (While we are being honest: the old classroom legend that Gauss summed 1 to 100 in his head as a toddler is almost certainly a tall tale. The real lesson that survives is the one in this figure — restructure the computation so that it never blows up.) That is every tool the chapter needs. So let's do the two things that turn a party trick into understanding. First we try to break the result. Then we find the general shape it is a special case of.

06Break it, then generalize

Every result we have built quietly assumed birthdays are spread uniformly, with all 365 days equally likely. Real birthdays are not: there are seasonal humps, more September births, fewer on Christmas. So does clustering make a shared birthday less likely, since people bunch onto fewer days? Guess first, then toggle from uniform to clustered and watch the crossover move.

The crossover moves the wrong way from most people's guess. Clustering makes collisions more likely, so the 50% crossing drops below 23. It makes sense once you see it: piling people onto fewer popular days is exactly what causes matches. So the plain-uniform answer of 23 is the conservative one, and the real world is even more collision-prone. Good — a result that survives having its assumptions kicked is a result you understand. Now zoom out. Strip away “birthdays” entirely and look at the template underneath.

Everything we did was one shape: a repeated trial, and the question “at least one success?” The universal answer for n independent trials, each with the same chance p, is P(at least one) = 1 − (1 − p)ⁿ. The die-six problem fits that formula exactly (p = 1/6). The birthday problem fits only approximately, because the 253 pairs are not quite independent. The formula puts the birthday crossing at 50.0%, a whisker from the exact 50.7%. Drive both knobs and watch this one formula.

The template 1 − (1−p)ⁿ fit the dice exactly and the birthdays only roughly. That word roughly hides the whole catch. The formula assumes every trial is independent, each carrying the same fixed p. When both of those hold, the template is exact. When the trials lean on each other it only approximates, and sometimes it lies outright. Below are three cases. Decide for each whether the shortcut is exact, close, or flat wrong before you reveal it.

One template covers every “at least one” problem in the book. And the birthday version hides a scaling law worth seeing, because it reaches far outside probability. Replace 365 with a general number of slots d and ask where the 50% crossing lands. The answer is beautifully clean: about 1.18·√d. For d = 365 that is 1.18 × 19.1 ≈ 23 — there is our number, and now it is a formula rather than a party fact. Slide d and watch the threshold track √d.

That √d law is not a curiosity. It is load-bearing infrastructure. In cryptography, a hash function maps data to one of d possible outputs, and a collision — two different inputs with the same hash — breaks the hash. The birthday result says an attacker does not need to try d inputs to force a collision, only about √d of them. That is why a hash advertised as “128-bit” has to output 2¹²⁸ values to stay safe against roughly 2⁶⁴ guesses: the security is the square root of the space, not the space itself. This exact party trick is why your passwords are safe or are not, and it has a name — a birthday attack. Same maths, a room of 23 people and a global security standard. Let's place it on the map.

07You are here

Step back to the family tree and see the honest size of what we did. We did not add a new axiom or a new distribution this chapter. We took the measure from Chapter 3 and learned one move on it: computing an event through its complement. We took one counting fact from Chapter 2, the depleting pool. Then we combined the move and the counting fact. Everything shocking that followed came from those two things we already owned. Find our rung, lit gold.

So this was a technique chapter, not a new-object chapter. It gave you the reflex to flip “at least one” into “1 − none,” and the humility to remember that your gut counts people when the maths counts pairs. That instinct — reach for the complement, or for a cleverly-chosen easier quantity — is one of the two master-moves of the whole subject. It comes back at the very summit, when we bound the tails of a distribution. But there is a question we have been carefully not asking, and it changes everything downstream.

Every probability so far has been fixed. An outcome just is, and P(A) is a single number carved in stone. But that is not how you actually reason, because you learn things. You find out the first card was red, and suddenly the chance the second one is a heart moves. So what is a probability once you have been handed a clue? And how do you update it? That is conditioning, and it is the door into the entire back half of this course. Take a first look at a probability changing the instant you learn something.

Watch that number jump the moment information arrives. That jump is the whole idea waiting in the next chapter. We will shrink the universe down to what we know, re-measure inside it, and discover that the plain multiplication we leaned on all chapter is just the calm special case where the clue tells you nothing. Turn the page.