Fourteen people within a day

Twenty-three people are enough for an even chance that two share a birthday. The reason is that there are 253 pairs among them, and each pair has a one-in-365 chance, so about $253/365 \approx 0.69$ matches are expected, and the chance of none is close to $e^{-0.69}$, a half. The number of pairs grows like the square of the room, which is why the room can be so small.

A near miss is a more forgiving coincidence. Two people whose birthdays fall on consecutive days are almost as striking at a party, and asking for birthdays within a day of each other makes each pair three times as likely to count — the same day, the day before, or the day after. The room shrinks accordingly, though by less than a factor of three, and the amount by which it shrinks is the first thing worth explaining.

Fourteen people are more likely than not to include two with birthdays within a day of each other. Nine are enough for two within three days, and seven for two within six — within a week, in the sense that one birthday falls in the week centred on the other. The curves are exact, and the year is treated as a circle, so that 31 December and 1 January are neighbours; a room does not care which day the calendar starts on.

The trick that makes it exact #

For exact matches the probability of no match is a product: the second person avoids the first’s birthday, the third avoids two, and so on. For near matches the forbidden set for each newcomer is a band of $2k + 1$ days around each earlier birthday, and the bands can overlap, which spoils the simple product. Inclusion and exclusion can handle the overlaps, but the resulting sum has as many terms as there are ways for bands to collide, and it hides the answer’s simplicity. There is a cleaner route, and it is a picture.

Put the $m$ birthdays on the circle of the year. They cut it into $m$ gaps. No two birthdays are within $k$ days exactly when every gap is longer than $k$. Now remove, after each birthday, the $k$ days that follow it. Every gap shrinks by $k$, the circle shrinks from $N$ days to $N - mk$, and a configuration with every gap longer than $k$ becomes a configuration with every gap at least one — with all birthdays distinct — on the shorter circle.

The correspondence is exact, and it gives the formula. The chance that $m$ people on a circle of $N$ days are pairwise more than $k$ days apart is

$$\prod_{i=1}^{m-1} \frac{N - mk - i}{N},$$

which at $k = 0$ is the familiar product for distinct birthdays. The factors are the same as for distinct birthdays on a year of $N - mk$ days, except that each denominator is still $N$: the shrinking changes which configurations are allowed, not how likely each individual birthday is. For fourteen people and $k = 1$, the shrunken circle has $365 - 14 = 351$ days and the product comes to $0.463$, so the chance of a near match is $0.537$.

Checking the formula against rooms #

A formula derived from a picture deserves a check that does not use the picture.

Twenty thousand simulated rooms of fourteen people, with birthdays drawn uniformly, give frequencies within about a percentage point of the formula at every $k$. The figure refuses to draw if they disagree by more than four standard errors. The simulated rooms know nothing about the shrinking argument: each draws fourteen birthdays, sorts them, and measures every gap round the circle directly, so the agreement is between the picture’s formula and a count that never used the picture. At $k = 0$, fourteen people have a 78% chance of all-distinct birthdays; at $k = 1$ that falls to 46%, and by $k = 6$ to under 3%. A room of fourteen almost always contains two birthdays within a week of each other.

For the classic room of twenty-three, the chance of avoiding even a one-day near miss is only 11%. The exact match that makes the birthday problem famous is the least forgiving version of the question; allowing one day either side turns an even chance into a near certainty.

One square root for every window #

The thresholds follow a single rule.

The estimate comes from the same pair-counting that explains twenty-three. A room of $m$ people has about $m^2/2$ pairs. Each pair is within $k$ days with probability $(2k + 1)/N$. If near matches are roughly independent and rare, their number is roughly Poisson with mean $m^2(2k+1)/(2N)$, and the chance of none is about $e^{-m^2(2k+1)/(2N)}$. Setting that to a half gives

$$m \approx \sqrt{\frac{2N \ln 2}{2k + 1}} \approx 1.18\sqrt{\frac{N}{2k+1}},$$

the curve in the figure. It follows the exact thresholds to within a person or two all the way from $k = 0$, where it gives 22.5, to $k = 12$, where the exact threshold is 5. Persi Diaconis and Frederick Mosteller used exactly this estimate in 1989 as a tool for judging when coincidences are surprising, rounding the constant to 1.2.

The lesson of the square root is that widening the window buys less than it seems. Tripling the chance for each pair, from an exact match to a match within a day, shrinks the room only by $\sqrt 3$, from 23 to 14. Going to a week either side, fifteen times the chance, shrinks it by $\sqrt{15}$, to about six or seven.

The same square root governs coincidences that have nothing to do with birthdays. Two people in a room sharing the last four digits of a telephone number need a room of about $1.18\sqrt{10{,}000} \approx 118$; two sharing a postcode among a million need about 1,200. Any coincidence among $N$ equally likely categories needs about $\sqrt N$ people, and every loosening of what counts as a match divides that by the square root of the loosening. It is the reason a collision search finds factors after about the square root of the smallest prime, and the reason coincidences in large groups are so much commoner than intuition expects.

What counts as near #

The formula answers a precise question and a party guest asks an imprecise one. “Near” might mean within a day, within a week, in the same week of the calendar, or in the same month. Each is a different window, and the calendar versions differ from the circular ones: two people born on 30 and 31 March share a month and are within a day, while two born on 31 March and 1 April are within a day and do not share a month.

The same month is a coarser version of the plain birthday problem, with twelve categories instead of 365, and it needs only five people for an even chance. The same calendar week has 52 categories and needs nine. Neither is the same as “within a week”, which uses a sliding window centred on each birthday and needs seven. The difference between fixed categories and sliding windows is that a sliding window never splits a near pair across a boundary, so it catches more coincidences for the same width.

This matters for the use Diaconis and Mosteller had in mind. A person who notices a coincidence rarely specified in advance what would count, and the more kinds of near miss that would have been noticed, the more likely it is that some kind occurs. Any unevenness in the calendar pushes the thresholds down further still, as it does for exact matches. The formula measures one kind; the surprise a person feels usually belongs to the union of many. A guest who would have been struck by a shared birthday, a birthday a day apart, a shared birth month, the same home town or the same first school has specified a very wide window without noticing, and a very wide window needs very few people. Diaconis and Mosteller called this the law of truly large numbers: with a large enough sample, and a loose enough notion of a match, any outrageous coincidence is likely to happen.

A certainty, and a scatter #

Probability gives thresholds; the pigeonhole principle gives certainties, and the circle makes the near-birthday certainty easy. With $m$ birthdays on a circle of 365 days, the $m$ gaps add up to 365, so the smallest gap is at most $365/m$. With 183 people the smallest gap is at most 1.99 days, and since gaps are whole numbers, some two of 183 people are certainly within a day of each other. Certainty needs 183 people; an even chance needs 14.

The distance between those two numbers is the whole of what randomness does. Random points on a circle do not spread out evenly. Their smallest gap is typically about $N/m^2$ — for fourteen people, a couple of days — far smaller than the even spacing of $N/m$, because with $m$ gaps there are many chances for one to be small. An arrangement designed to avoid close pairs can keep every gap near $N/m$; a random arrangement cannot.

The contrast is sharpest against the points laid down by turning a circle by the golden angle, which leave at most three different gap lengths at every stage and keep the smallest gap within a constant factor of the average. Those points are as far from random as points on a circle can be, and a room of people whose birthdays were placed that way would never have a near miss until it held more than a hundred people. Real rooms are random, and their near misses start at fourteen.

When the formula is wrong #

The circle model assumes every day equally likely and every birthday independent. Real birthdays are neither: births cluster in some months and avoid public holidays, and a room of people is rarely a random sample — families, schools and sports teams group people born close together. Seasonal clustering of births is modest — the busiest months have perhaps ten per cent more births than the quietest — and its effect on the thresholds is to move them by a fraction of a person. Social clustering is much stronger: a class of schoolchildren born within one school year has birthdays spread over 365 days but sorted into a single cohort, and a team of athletes is famously overweight in the months just after a selection cut-off. Every departure from uniformity makes near matches more likely, not less, for the same reason uneven calendars make exact matches more likely: concentrating probability increases the chance that two draws land close together.

The shrinking argument also depends on the circle. On a calendar year with a beginning and an end, a birthday on 31 December has no neighbour on 1 January, and the exact formula for a line of $N$ days is slightly different. The same shrinking trick works on a line — remove $k$ days after every birthday but the last, and the question becomes distinct birthdays on a line of $N - (m-1)k$ days — and gives the chance of no near match as $\prod_{i=0}^{m-1} (N - (m-1)k - i)/N$. The difference from the circle affects only the pairs straddling the year’s end, a fraction of about $2k/N$ of all pairs, and the thresholds come out the same: 14 within a day, 9 within three days, 7 within six, on the line as on the circle.

What the figures cannot show #

The simulations are fixed-seed runs of twenty thousand rooms, and they confirm the formula at seven values of $k$ for two room sizes. The formula itself rests on the shrinking argument, which is a bijection between configurations and is exact; the simulations show it was transcribed correctly, not that it is true.

The room drawn on the circle is a single sample, chosen by a seed and not by looking for a striking example. Its smallest gap happens to be 3 days, so this room of fourteen does not contain a near miss within a day, and that is roughly as likely as not. A single room shows what the gaps look like; the probability is a statement about all rooms, which a picture of one cannot display.

And the square-root estimate is a heuristic that happens to be excellent here. The Poisson approximation it rests on is well justified for small windows, where near matches are rare and nearly independent. For windows of a month either side, where most pairs of people are near, the estimate and the formula would part company, and the exact product is the only thing to trust.

Nor do the curves say anything about which two people will be the near pair, or how many near pairs a room will hold. The expected number of pairs within a day in a room of fourteen is $91 \times 3/365 \approx 0.75$, and rooms with two or three near pairs are common; the threshold is about the chance of at least one, which is a coarser statistic than the count. A room that shows no near pair is not evidence of anything, and a room that shows three is not either — the same arithmetic produces both, as the single room drawn above, with its smallest gap of three days, is a reminder.

The question it leaves: every person matched #

A near match, like an exact one, asks for a single coincidence somewhere in the room. The opposite extreme asks for coincidences everywhere: a room in which every person shares a birthday with someone else. That needs a far larger room — larger than the number of people it takes to cover every day of the year — and its threshold, 3,064, comes from counting a different quantity entirely: not pairs, but people left alone. It is the subject of the essay on a room where nobody is alone.

Between the two extremes lies the coupon collector’s question — how long until every day turns up as somebody’s birthday — which needs about 2,287 people for an even chance. The three questions are three different kinds of count. A single coincidence counts pairs and needs about $\sqrt N$ people; covering every day counts empty days and needs about $N\log N$; leaving nobody alone counts lonely people and needs more still. Near misses belong with the first kind, which is why their thresholds are so small and move only by square roots. The other two kinds are about the room as a whole rather than about any one pair in it, and they need the room to be larger than the year before they even begin.

Close enough #

Fourteen people are enough for two birthdays within a day of each other, seven for two within a week either side. The exact answers come from a picture: put the birthdays on the circle of the year, take away $k$ days after each one, and the near-birthday question becomes the ordinary birthday question on a shorter circle. The pattern behind all the answers is one square root, $\sqrt{N/(2k+1)}$, because each widening of the window multiplies the chance of every pair and the number of pairs grows as the square of the room.

The exactness comes cheaply because the circle has so much symmetry. Every day is like every other, every gap is exchangeable with every other, and removing days after each birthday does not favour any birthday over another. On a real calendar with uneven births and a year that ends, the shrinking trick survives only approximately, and the numbers move by less than a person.

The birthday problem is usually told as a surprise about twenty-three. With near misses allowed it becomes a surprise about how few people any coincidence needs — and about how little the exact number matters, since each version of “near” moves the threshold only by a square root, and every version of the question is answered by the same count of pairs.