Why 23 People Make a Shared Birthday Likely

Twenty three people sounds far too small for a shared birthday to be more likely than not. That reaction is sensible, but it is counting the wrong thing. The birthdays are not compared with the calendar one person at a time. They are compared with one another, pair by pair. Start with three people. Each blue dot is one person, and each yellow line will represent one question: do the two people at its ends share a birthday? The first person can be compared with the second. The first can also be compared with the third. Finally, the second can be compared with the third. Three people already make three distinct pairs. Now add a fourth person. That newcomer creates three fresh comparisons, one with everyone already present. Add a fifth person and the newcomer creates four more. We added two people, but we added seven pairs. Five people therefore make ten pairs. In general, n people each appear in n minus one comparisons. That counts every pair twice, once from each end, so we divide by two. Now put twenty three people around the circle. The dots still look sparse. That is the picture our intuition notices. But every dot must be compared with every other dot. The formula gives twenty three times twenty two, divided by two. That is two hundred fifty three. Here is every comparison the birthday question is actually making. So the experiment is not twenty three lonely attempts to hit one special day. It is two hundred fifty three opportunities for some pair to collide. We have not proved the fifty percent claim yet, but now the scale of it should no longer feel absurd.

To keep the calculation clean, suppose there are three hundred sixty five equally likely birthdays, ignore leap day, and treat people's birthdays as independent. Real birthdays are not perfectly uniform, but this model is close enough to expose the main effect. Counting every possible kind of match directly is messy. Two people might match, three might match, or two separate pairs might match. So turn the question around. What is the chance that every birthday is different? The first person can have any birthday. For the second person to avoid a match, only one day is forbidden. That leaves three hundred sixty four safe days out of three hundred sixty five. Bring in a third person. Now two occupied birthdays must be avoided, so only three hundred sixty three days are safe. Both conditions must hold, which is why the fractions multiply. Each new person contributes another fraction, with one fewer safe day in the numerator. For n people, multiply from three hundred sixty four over three hundred sixty five down to three hundred sixty six minus n over three hundred sixty five. At twenty three people, that product is about zero point four nine two seven. So the chance that everyone differs is just under one half. Subtract from one, and the chance of at least one shared birthday is about zero point five zero seven three, just over one half. Now view every group size on one graph. The horizontal axis is the number of people, and the vertical axis is the chance that some pair shares a birthday. The dashed line marks one half. With ten people, the chance is only about eleven point seven percent. That feels unsurprising, and it gives us a low starting point on the curve. Move to twenty two people. The chance has climbed to about forty seven point six percent, still below the dashed half line. Add just one more person. That newcomer does not create one new chance to match. They create twenty two new pair comparisons. At twenty three, the probability reaches fifty point seven percent and crosses the line. The rise continues quickly. At thirty people the chance is about seventy one percent. At fifty people it is about ninety seven percent. The curve accelerates because every new arrival is compared with everyone already present. That is why twenty three is enough. It is not large compared with three hundred sixty five days, but it creates two hundred fifty three pairs. The product calculation and the graph now say the same thing: a shared birthday is more likely than not.

Now ask a question that sounds almost identical. How many people are needed before someone probably shares my birthday specifically? The word my changes the comparison structure completely. With seven people in the room, only six comparisons matter for my birthday. Each yellow line joins me to one other person. Birthdays shared entirely among the blue people do not answer this question. For the original birthday problem, every pair matters. The same seven people create twenty one comparisons, because every person is checked against every other person. The left count grows one at a time as people arrive. The right count grows by the whole number already in the room. That is why the original any-pair question reaches one half so much sooner. Let n mean the number of other people, not counting me. One person fails to match my birthday with probability three hundred sixty four over three hundred sixty five. For nobody to match me, all n people must fail. A match becomes more likely than not when the no-match probability falls below one half. So we set the shrinking power below one half. Take logarithms to bring n down from the exponent. Because the logarithm of three hundred sixty four over three hundred sixty five is negative, dividing by it reverses the inequality. The result is n greater than two hundred fifty two point six. Since n must be a whole number, we need two hundred fifty three other people. Including me, that is two hundred fifty four people in the room. Put both questions on one graph. The horizontal axis now counts everyone in the room, including me. The dashed line is again a probability of one half. The blue curve asks whether any pair matches. It crosses one half at twenty three people because those people create two hundred fifty three pairs. The green curve asks whether someone matches one fixed birthday. It rises far more slowly and crosses one half at two hundred fifty four people, meaning two hundred fifty three comparisons with me. So the intuition that twenty three feels too small was not foolish. It was quietly answering the green question while the birthday paradox asks the blue one. Always ask which pairs actually count.

The birthday idea appears anywhere many objects are assigned to a limited set of labels. A hash function turns a file, password, or message into one fixed-size output. Two different inputs that receive the same output create a collision. Here are sixteen possible outputs. Send in one item, then a second, a third, and a fourth. So far every item has landed in a different slot. Now send in the fifth. It lands in the same slot as the second item. Sixteen slots sounded generous for five items, but five items already create ten pairs that might collide. Suppose a hash has N equally likely outputs and we try k inputs. The number of input pairs is k times k minus one over two, exactly the same pair count as before. Each pair has about one chance in N of sharing an output. Combining all those small risks gives this standard approximation for no collision. Subtracting from one gives the chance of at least one collision. Set that collision chance to one half and solve. The result is about one point one eight times the square root of N. The constant matters for an exact estimate, but the memorable fact is the square root. The birthday example checks the scale. Three hundred sixty five possible days have a square root near nineteen, and the more accurate crossing is twenty three. A sixty four bit hash has two to the sixty fourth possible outputs, but collisions become likely after roughly two to the thirty second inputs. That is about four billion, far below the number of available outputs. For a one hundred twenty eight bit hash, the birthday scale is about two to the sixty fourth trials. For a two hundred fifty six bit hash, it is about two to the one hundred twenty eighth. Collision resistance therefore provides roughly half as many security bits as the output length. That matters when hashes identify files, support digital signatures, or detect duplicates. A real design either chooses enough output bits to make accidental collisions fantastically unlikely, or includes a clear plan for handling collisions when they occur. Four ideas now hold the whole lecture together. Count comparisons rather than objects. Compute the easier no-collision probability. Check whether every pair counts or only comparisons with one fixed target. And expect collisions near the square root of the number of possible outcomes. Twenty three people are enough because they do not create twenty three chances to match. They create two hundred fifty three pairs. Once that hidden web is visible, the birthday result stops being a trick and becomes an ordinary collision problem.