A room where nobody is alone

The classic birthday problem asks for one coincidence: some two people with the same birthday, which twenty-three people probably provide. The near-birthday version loosens what counts as a coincidence and needs fewer people still. The strong version goes the other way. It asks for a room in which everyone shares a birthday with at least one other person — nobody is the only person present born on their day.

The room this needs is enormous, and the way the answer behaves as the room grows is stranger than its size. Adding people helps in the end, but for a long time it makes things worse, and the number of people who are alone is the quantity that explains both. Coverage of every day of the year comes long before every person has company, and the gap between those two moments is where this problem lives.

It takes 3,064 people before it is more likely than not that nobody is alone. Below about 1,500 the chance is indistinguishable from zero: in any room smaller than four years’ worth of people, somebody almost certainly has a birthday that nobody else shares. Then the chance rises steeply, crosses a half at 3,064, and approaches certainty only in rooms of five or six thousand.

Counting exactly by following two numbers #

There is no simple product for this probability, as there is for distinct birthdays. The obstacle is that whether a person is alone depends on everyone else in the room, not just on the people before them: a loner can be rescued by any later arrival born on the same day.

The way round is to follow the room as it fills, keeping track of just two numbers: $a$, the number of days on which exactly one person present was born, and $b$, the number of days on which two or more were. When a new person arrives, three things can happen. With probability $(365 - a - b)/365$ they land on an unused day, and $a$ goes up by one. With probability $a/365$ they land on a day with one person, rescuing that loner: $a$ goes down and $b$ goes up. With probability $b/365$ they land on a crowded day and nothing changes.

Nobody is alone exactly when $a = 0$. So the chance that nobody is alone in a room of $m$ is the chance that this two-number walk is at $a = 0$ after $m$ steps. The walk has about 67,000 possible states, and following all of them through 3,064 steps is a few hundred million arithmetic operations — nothing for a computer, and exact to the precision of the arithmetic. This is a Markov chain: the future depends only on the current $a$ and $b$, not on how the room came to be that way.

The count that drives it: loners #

The simpler quantity to understand is the expected number of loners.

A given person is alone when all $m - 1$ others miss their birthday, which happens with probability $(364/365)^{m-1}$. So the expected number of loners is $m (364/365)^{m-1}$. For small rooms it is nearly $m$: almost everyone is alone. It keeps rising, because each newcomer is more likely to become a new loner than to rescue an old one, until the room holds about as many people as the year has days. At 364 people it peaks, with about 134 loners expected — more than a third of the room. After that the days are crowded enough that a newcomer is more likely to spoil someone’s solitude than to start their own, and the count falls.

The peak’s location has a one-line explanation. Each newcomer adds a loner with probability about $e^{-m/N}$ — the chance their day is empty — and removes one with probability about $(m/N)e^{-m/N}$ — the chance their day holds exactly one person. The two balance when $m = N$. The rescue rate is the product of how crowded the room is and how rare occupied days are, and it overtakes the creation rate exactly when the room is as large as the year.

It falls slowly. The factor $(364/365)^m$ halves every 253 people, so the expected number of loners drops from 134 at 364 to about 1 near 2,900. The last few loners take thousands of arrivals to eliminate, because each one is rescued only by somebody born on one particular day.

The Poisson estimate, and why it works #

When the expected number of loners is small, the actual number is close to a Poisson count with that mean, and the chance of none is about $e^{-\text{mean}}$:

$$P(\text{nobody alone}) \approx \exp\!\left(-m\left(\tfrac{364}{365}\right)^{m-1}\right).$$

The dashed curve on the first figure is this estimate, and it lies almost exactly on the exact curve. Setting it to a half puts the threshold at 3,061; the exact computation gives 3,064. The estimate works because in a large room the loners are rare and nearly independent — whether one person is alone has little effect on whether another, born on a different day, is.

A twelve-day year makes all three approaches checkable at once.

On twelve days the exact walk, the estimate and four thousand simulated rooms at each size can be put on one picture. The simulations sit on the exact curve, which confirms the walk was transcribed correctly. The estimate runs a little ahead — it treats the loners as independent when they are slightly negatively correlated, since a crowded room that rescued one loner has used up a person who might otherwise have been a loner elsewhere. On twelve days the difference is visible; on 365 it amounts to three people.

Other years, the same shape #

Nothing about the answer depends on the year having 365 days, and shorter years show how the threshold scales.

For a year of thirty days the threshold is 164 people, about five and a half times the length of the year; for twelve days it was 52, a little over four times; for 365 days it is 3,064, eight and a half times. The ratio grows because the room has to exceed the year by a factor that grows with the logarithm of the year. The expected number of loners is roughly $m e^{-m/N}$, and it falls to one only when $m/N$ is about $\ln m$, which is itself about $\ln N + \ln\ln N$. For 365 days that is about 7.7, and the exact threshold’s extra factor comes from requiring the chance to reach a half rather than the mean to reach one.

The picture is the same at every size: essentially zero for a long time, then a steep rise over a range of a few times the year’s length. What changes with the year is only where the rise starts. The steepness in relative terms increases slowly with the year, which is the kind of sharpening that probabilists call a threshold phenomenon, and it is shared by the coupon collector’s problem and by the connectivity of random graphs.

Three thresholds on one scale #

The strong birthday threshold is easiest to appreciate beside two others.

Some two people share a birthday at 23. Every day of the year is somebody’s birthday — the coupon collector’s problem, how long until every one turns up — at 2,287, which is close to $365 \times (\ln 365 + 0.37)$. And nobody is alone at 3,064. The order is not obvious in advance. Covering every day sounds like the more demanding condition, since it requires all 365 days to be used; but a room can cover every day and still have many loners, one on each of the days that happened to be hit once. Requiring nobody to be alone is requiring every used day to be used at least twice, and that takes about 780 more people.

The three thresholds scale differently with the length of the year $N$. A single collision needs about $\sqrt{N}$ people, which is the wait the rho method for factoring exploits when it looks for one repeated remainder. Covering every day needs about $N \ln N$. Leaving nobody alone needs about $N(\ln N + \ln \ln N)$ — the expected number of loners, $m e^{-m/N}$ roughly, falls to one only when $m/N$ exceeds $\ln N$ by an extra $\ln\ln N$, because the factor $m$ in front grows with the room. The last two differ by a slowly growing amount, and the ratio of them tends to one; the first is in a different world.

What the answer is used for #

The strong birthday problem is not only a party puzzle. Anirban DasGupta, who gave the 3,064 figure in a 2005 survey, noted its relevance to questions of uniqueness in large collections of records — how many entries of a database of identifying features are unmatched by any other, or how often a marker in a population sample is carried by only one person. In each case the question is not whether any two records coincide but whether any record is unique, and uniqueness vanishes far more slowly than coincidence appears.

It is the same arithmetic that governs a random graph becoming connected: the last obstacle to connection is an isolated vertex, and isolated vertices disappear only when the expected number of them falls below one. In both problems the threshold is where a rare kind of loneliness stops being expected, and in both it arrives well after the structure looks, on average, complete. A random network with enough links to have one giant connected piece can still have a few isolated points for a long time, and a room with enough people to use every day can still have loners for a long time, for the same reason: the average is dominated by the bulk, and the obstacle is the exception.

The day that spoils it: 29 February #

The real calendar makes the strong problem much harder, and one day is responsible. A person born on 29 February has a birthday that occurs about once in 1,461 days, so in a room of 3,064 people the expected number of leap-day birthdays is about 2.1. If births are spread evenly over the four-year cycle, the number in the room is close to a Poisson count with that mean, and the chance that exactly one person was born on 29 February is about 26%.

That person is alone, whatever else is true of the room. So on the real calendar, a room of 3,064 has at least a one-in-four chance of a loner from this cause alone, before any of the other 365 days is considered, and the uniform model’s even chance of nobody being alone is out by a large margin. The leap-day loner is only eliminated when the expected number of leap-day births is large enough that exactly one becomes unlikely — rooms of ten thousand or more.

The effect is a clean illustration of a general point: the strong problem is governed by the rarest category, where the classic problem is governed by the most common. A shared birthday arrives soonest on the busiest days; nobody being alone arrives last on the quietest. Any real application — uniqueness in a database, a marker carried by one person in a sample — inherits that sensitivity to the rare end of the distribution, which is why the uniform answer is a floor rather than an estimate. It is the mirror image of the classic problem, where any unevenness brings the match sooner; here unevenness postpones the goal, and the postponement is set by the category that hardly ever comes up, exactly as it is for a coupon collector with one rare coupon. Both problems about completeness are hostage to their rarest case, while the problem about a single coincidence is helped by its commonest.

What the figures cannot show #

The exact curve is exact for a uniform year of 365 independent birthdays. Real birthdays are not uniform, and uneven calendars change this problem in both directions: common birthdays are more easily shared, but rare birthdays — 29 February, public holidays with few scheduled births — produce loners who are very hard to rescue. A single day with a quarter of the average birth rate needs four times as many people to be sure of a second occupant, and it can dominate the threshold.

The simulations in the twelve-day figure are fixed-seed runs of four thousand rooms at sixteen sizes. They confirm the walk at those sizes; the walk itself is exact by construction, and its only approximation is the floating-point arithmetic, whose errors after a few thousand steps are far below the resolution of the picture.

And the thresholds are about the median — the room size at which the chance passes a half. The spread around them is wide for the strong problem: the chance of nobody being alone goes from 10% to 90% between about 2,560 and 3,830 people, a range of more than a thousand, because the last loner’s rescue is a waiting time for one specific day to be hit.

The question it leaves: the last loner #

The expected number of loners falls below one near 2,900, and the room is loner-free with even chance at 3,064. After that, the question becomes how long the last loner lasts. When one person remains alone, they are rescued only by an arrival born on their day, which takes 365 arrivals on average; but by then new loners are rarely created, so the room typically has either none or one.

The detailed behaviour near the threshold — how many loners there are, how long each lasts, how the last one’s rescue time is distributed — is a problem in extreme values: the time until every one of a large number of rare events has happened is governed by the slowest of them, and its distribution after rescaling is the Gumbel distribution, the same law that governs the coupon collector’s wait and the largest of many independent samples. The birthday version shows it at a size where every number can still be computed exactly.

The same limit law says that, suitably shifted and scaled, the number of people needed before nobody is alone becomes more predictable in relative terms as the year grows, while its spread in absolute terms grows like the year itself. For 365 days the spread is about a thousand people either side of the median; for a year of a million days it would be about a million — a small fraction of the roughly sixteen million people the threshold would then require.

Nobody alone #

A single shared birthday needs 23 people and happens almost at once. A room in which every person shares needs 3,064, and the reason is the arithmetic of loners: they multiply while the room is small, peak at 134 when the room is the size of the year, and then decline at a rate set by the chance that one specific day is missed by everybody else. The Poisson estimate built on that count is within three people of the exact answer, and the exact answer comes from following two numbers — days with one person and days with more — as the room fills.

Between the two sits the coupon collector’s 2,287, where every day of the year is taken. The strong problem needs more, and the extra is exactly the difference between a day being used and a day being shared: covering the calendar is about the days, leaving nobody alone is about the people, and the people are harder to satisfy.

That is the thread through all three versions of the question. The classic problem counts pairs and is settled by the square root of the year. The coupon collector counts empty days and needs the year times its logarithm. The strong problem counts lonely people and needs a little more than that again. Each is a different statistic of the same random scatter of birthdays, and each is controlled by the expected number of the one bad thing it asks to avoid — a thing that becomes rare at a different moment for each.