Matpic
mathematics, in pictures
Concept

Birthday problem

The question of how many random draws from a set of possibilities make a repeat likely. Among 365 equally likely birthdays the answer is 23, and in general a repeat is likely after about the square root of the number of possibilities.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

When a shared birthday becomes likely. The chance that some pair in a group shares a birthday, against group size. It passes a half at 23 people, where the probability is 50.7%.

Twenty-three people

A room needs 253 people before someone probably shares a birthday with you. It needs 23 before two of them probably share one with each other. The gap between those numbers is the whole problem.

probability · Birthday problem A year of birthdays with a seasonal swing of ±50%, peaking in September. Bars for the 365 days of a model calendar with a seasonal swing of ±50%, peaking in September, drawn as each day's excess or shortfall against an even year. A shared birthday among 23 people has chance 54.86% against 50.73% for the even year, the first group with an even chance is 22, and the calendar behaves like 324.4 equally likely days.

Any unevenness brings the match sooner

Real birthdays are not spread evenly across the year, and every such departure pushes the famous twenty-three down rather than up. The proof is one move on two days at a time, and what it leaves behind is a single number — the one ecologists use to count species.

probability · Birthday problem The walk x² + 1 modulo 101, drawn as the letter ρ. Starting at 2 and squaring and adding 1 modulo 101, the walk visits 8 values once on a tail and then runs round a cycle of 9 values for ever.

A collision that finds a factor

A walk through the remainders modulo a number must eventually repeat, and it repeats modulo each hidden prime factor long before it repeats modulo the number. Pollard saw that the earlier repeat can be detected without knowing the prime — and that its timing is the birthday problem, so the cost is the square root of the factor.

probability · Birthday problem

Named alongside it

The objects these essays reach for when they reach for this one.

CollisionComplementary countingIndependenceChinese remainder theoremConvexityFactoringGreatest common divisorHash collisionIterationModular arithmeticPairsPigeonhole principle

All concepts