How many get their own hat

Nobody gets their own hat answered one question about a random arrangement of hats — the chance that no one gets their own — and found it settling on $1/e \approx 0.3679$ however large the crowd. A sum stopped early still says something showed that the alternating sum behind that answer brackets it at every stop.

The natural next question asks for more than one number. How many people get their own hat? The count can be 0, 1, 2 and so on up to the whole crowd, and each value has a chance. The whole distribution settles down, not just its first entry, and what it settles on is one of the most important distributions in probability.

Exactly k in place #

The count of arrangements in which exactly $k$ people get their own hat comes straight from the earlier count. Choose which $k$ people are lucky, in $\binom{n}{k}$ ways, and arrange the remaining hats so that none of the others is lucky, which is a derangement of $n - k$ objects:

$$\#\{\text{exactly } k \text{ in place}\} = \binom{n}{k}\, D_{n-k}.$$

For eight hats that gives 14,833 arrangements with nobody in place, 14,832 with exactly one, 7,420 with exactly two, 2,464 with three, 630 with four, and so on, and the figure checks each count by listing all 40,320 arrangements. Exactly seven in place is impossible, since if seven people have their own hats the eighth must too.

The first two counts differ by exactly 1, and that is true at every size: $n D_{n-1}$ and $D_n$ differ by $\pm 1$, from the recurrence $D_n = n D_{n-1} + (-1)^n$ of the earlier essay. Having nobody in place and having exactly one person in place are almost exactly equally likely, whatever the size of the crowd — an unexpected fact that a single count would never reveal.

Each exact chance is a stopped sum too #

The formula for exactly $k$ in place has the derangement count inside it, and that count is an alternating sum, so each probability is itself a sum that can be stopped early:

$$P(\text{exactly } k) = \frac{1}{k!}\left(1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{(n-k)!}\right).$$

Every stop of the bracketed sum brackets the probability, as the previous essay proved for every inclusion–exclusion sum. For exactly two people in place, stopping after three terms gives the upper bound $\tfrac12 (1 - 1 + \tfrac12) = \tfrac14$, and stopping after four gives the lower bound $\tfrac12(1 - 1 + \tfrac12 - \tfrac16) = \tfrac16$; the true value for eight hats, $7{,}420/40{,}320 \approx 0.184$, lies between them. The brackets tighten factorially, which is the same fact as the rapid convergence below seen from inside one probability.

The shape it approaches #

Divide each count by $8! = 40{,}320$ and set the shares beside the numbers $1/(e\,k!)$: $1/e$, $1/e$, $1/(2e)$, $1/(6e)$, $1/(24e)$. They are the Poisson distribution with mean 1, the distribution of the number of rare events when events are many, independent and each unlikely, averaging one in total. The two sets of bars are indistinguishable at this scale.

The limit is easy to read off the formula. The chance of exactly $k$ in place is $\binom{n}{k} D_{n-k}/n!$, which is

$$\frac{1}{k!} \cdot \frac{D_{n-k}}{(n-k)!},$$

and the second factor is the chance that $n - k$ objects are deranged, which tends to $1/e$. So the chance of exactly $k$ tends to $1/(e\,k!)$ for each fixed $k$, and the Poisson distribution is exactly what those limits form.

The intuition is the one the first essay described and distrusted. Each of $n$ people has a chance $1/n$ of getting their own hat, and $n$ nearly independent chances of $1/n$ give a count that is approximately Poisson with mean $n \cdot 1/n = 1$. The events are not independent — one person holding their own hat changes everyone else’s odds — but the dependence is weak, and the next figure measures exactly how weak.

Averages that come out exactly 1 #

The number of people who get their own hat has mean exactly 1 for every crowd size, because each of the $n$ people has chance $1/n$. The average of $X(X-1)$, which counts ordered pairs of lucky people, is exactly 1 too: there are $n(n-1)$ ordered pairs of people, and each pair is lucky together with chance $\frac{1}{n(n-1)}$, the chance that both hats land right. The same goes for ordered triples and so on — the $r$-th of these factorial moments is the number of ordered $r$-tuples of people, $n!/(n-r)!$, times the chance that all of them are in place, $(n-r)!/n!$, which is 1.

That is a counting argument of the kind inclusion–exclusion is built from, and it does not care about dependence at all. Every factorial moment up to the size of the crowd is exactly 1; beyond it, where there are not enough people to pick, the moment is 0. The table computes each one from the exact counts by summing over all 40,320 arrangements, and gets 1, 1, 1, 1, 1, 1, 1, 1, then 0.

The Poisson distribution with mean 1 is the distribution whose factorial moments are all exactly 1. The number of matches agrees with it in every moment it has, and a distribution determined by its moments — as the Poisson is — is approached by anything whose moments approach its moments. That is the method of moments, and it turns an exact count at every size into a limit theorem. The same technique shows that the number of triangles in a sparse random network is approximately Poisson around the point where triangles first appear, the kind of transition sharp or merely a threshold is about, and it is the higher-order version of the first- and second-moment arguments of finding a threshold with two moments.

Dependent, and still variance 1 #

The mean being exactly 1 needs no independence at all: the average of a sum is the sum of the averages, whatever the events have to do with each other. The variance is where dependence usually shows, and here it is worth computing exactly because the answer is so clean.

For two different people $i$ and $j$, the chance that both get their own hat is $\frac{1}{n(n-1)}$, slightly more than the $\frac{1}{n^2}$ it would be if the two events were independent: knowing that one person has their hat leaves $n - 1$ hats for $n - 1$ people, a slightly better chance for the rest. Each pair of events is therefore slightly positively related, by $\frac{1}{n(n-1)} - \frac{1}{n^2}$. There are $n(n-1)$ ordered pairs, and adding their small positive relations to the $n$ individual variances gives

$$n \cdot \frac1n\left(1 - \frac1n\right) + n(n-1)\left(\frac{1}{n(n-1)} - \frac{1}{n^2}\right) = \left(1 - \frac1n\right) + \frac1n = 1.$$

The dependence adds exactly what the individual variances lack. Independent events with chance $1/n$ each would give a variance of $1 - 1/n$; the weak positive relation between pairs adds back $1/n$, and the variance is exactly 1 at every size — the same as the Poisson’s.

A general method for this situation was found by Louis Chen in 1975, building on Charles Stein’s: it bounds the distance between a count of weakly dependent rare events and the Poisson distribution with the same mean by quantities that measure how strongly the events depend on each other. For the hats those quantities are tiny, and the Chen–Stein method explains in general what the exact counts show here.

How fast the limit arrives #

The total variation distance between two distributions is the largest amount by which they can disagree about the probability of any single event. For the number of matches against the Poisson with mean 1 it is about a tenth at four hats, six ten-thousandths at eight, and about one part in a hundred million at fourteen. On an axis where each gridline is a hundred times smaller, the points bend downwards: each extra hat shrinks the distance by a larger factor than the one before.

Convergence that fast is unusual. Sums of many independent chances approach their limits at a rate proportional to one over the square root of the number of terms, as the central limit essays measure; the number of matches, a count of weakly dependent events, beats that by a factorial. The reason is visible in the moments: they are not approximately right but exactly right up to the $n$-th, so any discrepancy can only come from moments of order higher than $n$, and those carry very little weight in the probabilities of small counts.

Cycles of every length #

A person who gets their own hat is a cycle of length 1 in the arrangement: follow where each hat goes, and every arrangement breaks into closed loops. Two people who have each other’s hats form a cycle of length 2, a swap; three people passing hats round form a cycle of length 3.

The fixed points are only the first of a family. The average number of cycles of length $k$ is exactly $1/k$, for every $k$ up to the size of the crowd: one fixed point, half a swap, a third of a three-cycle, on average. The figure counts all the cycles in all 40,320 arrangements and finds that the cycles of length $k$ number exactly $40{,}320/k$. The count of swaps is approximately Poisson with mean one half — 0.607, 0.302 and 0.078 against 0.607, 0.303 and 0.076 — and as the crowd grows the counts of cycles of each length become independent Poisson variables with means $1, \tfrac12, \tfrac13, \ldots$, a theorem going back to Goncharov in the 1940s.

Long cycles are where a famous puzzle lives. A hundred prisoners must each find their own number among a hundred boxes, opening at most fifty. If each starts at the box bearing their own number and follows the numbers found inside from box to box, a prisoner succeeds exactly when their number sits on a cycle of length at most fifty, so all succeed together exactly when the arrangement has no cycle longer than fifty. An arrangement of $n$ objects has at most one cycle longer than $n/2$, and the number with a cycle of length $k$ is $n!/k$ — the same $1/k$ in another guise — so the chance of success is

$$1 - \left(\frac{1}{51} + \frac{1}{52} + \cdots + \frac{1}{100}\right) \approx 0.3118,$$

where opening boxes at random would give $2^{-100}$. The cycle structure turns an absurdly unlikely coincidence into a better-than-three-in-ten chance.

Adding the averages gives the average total number of cycles, $1 + \tfrac12 + \tfrac13 + \cdots + \tfrac1n$, which grows like the logarithm of $n$. A random arrangement of a million objects breaks, on average, into about 14 cycles. The cycle structure also decides the arrangement’s parity — whether it can be undone by an even number of swaps — which is the invariant of the puzzle that is exactly half solvable.

A thousand objects behave as eight do #

Listing every arrangement stops at nine or ten objects, but the limit theorem says what larger crowds should do, and shuffling tests it. Five thousand random arrangements of a thousand objects, generated from a fixed seed, left an average of 1.005 objects in place, and 35.5 per cent of them left none. The Poisson predictions are 1 and 36.8 per cent.

The gap of just over one percentage point is within sampling noise, not a failure of the limit: with 5,000 shuffles the share with no matches has a standard error of about 0.7 percentage points, so the gap is a little under two standard errors, and the exact chance for a thousand objects differs from $1/e$ by an amount far too small to see. A shuffle is only as good as its randomness, too, and how long until it forgets measures how many real shuffles a deck needs before its arrangement is random enough for counts like these to apply. At eight objects the exact distribution is already within six ten-thousandths of the Poisson; at a thousand, the only thing separating the shuffles from the limit is the finite number of shuffles.

Drawing names for a gift exchange #

The limit has a practical face. A group drawing names from a hat for a gift exchange, and starting again whenever someone draws their own name, is running the hat problem until it succeeds. Each draw succeeds with chance $D_n/n!$, so the number of draws needed follows a geometric distribution whose average is $n!/D_n$. For eight people that is $40{,}320/14{,}833 \approx 2.71826$, within three hundred-thousandths of $e$ itself.

So a group of any size should expect to draw about $e$ times, and almost exactly as often as not, a failed draw fails because precisely one person drew their own name — the near-equality of the first two counts, turning up as an everyday nuisance. A group that redraws only the unlucky person’s name instead of starting over is no longer drawing uniformly at random, which is why careful organisers start again from scratch.

Rencontres, three centuries on #

The problem is older than probability’s modern notation. Pierre Rémond de Montmort posed and solved it in 1708 as the problème des rencontres: turn over the cards of a shuffled deck while counting aloud, and ask for the chance that no card matches the number called. He found the chance of no match approaching $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots$, which is $1/e$, decades before Euler named the number of the curve that is its own slope. For a single suit of thirteen cards the exact chance of no match, $D_{13}/13!$, already agrees with $1/e$ to ten decimal places.

What changed later was the understanding of why the answer is a Poisson distribution and why it appears in so many places. The same law governs the number of shared birthdays in a room when the room is small, the number of empty boxes when balls are thrown into many boxes, the number of isolated points in a sparse random network. In each case the events are numerous, individually rare and nearly independent, and the factorial moments come out close to the powers of the mean. Twenty-three people approaches its answer by a product rather than a count of pairs, but for groups well below 23 the number of shared-birthday pairs is approximately Poisson too.

Exact counts to fourteen, and a rate observed but not bounded #

The exact distributions stop at a few dozen thousand arrangements. Listing all arrangements is feasible up to nine or ten objects, and the moments and distances are computed from exact counts up to fourteen; the thousand-object figure is a sample, and it carries sampling error of the size its caption discusses.

The independence of cycle counts is stated, not shown. The cycles figure shows the averages exactly and one distribution approximately; that the counts of different cycle lengths become independent in the limit is quoted from the theory.

And the rate of convergence is observed, not bounded. The distances fall faster than any fixed ratio on the fourteen sizes drawn; bounds that hold for every size exist, but the figure displays measurements rather than a proof.

Still open: a random order that splits every pair #

Random arrangements of a set with no constraints are well understood. Add constraints — some items must come before others, as in a partial order like the cube cut into chains — and take an arrangement at random among those that respect them. The 1/3–2/3 conjecture, open since the late 1960s, says that unless the constraints already force a single order, some pair of items lies in either order with chance between one third and two thirds. It is not known whether every partial order has such a balanced pair; the best proven bounds place the chance between about 0.276 and 0.724, and the conjecture is known for several special families of orders.

One count, a whole distribution #

The hat problem asked for one probability and got $1/e$. Asking for the whole distribution of the number of matches produces the Poisson with mean 1, and the reason is a set of averages — the factorial moments — that are exactly 1 at every size, because they count ordered choices of people and weigh each by the chance that all of them are lucky. The limit arrives at a factorial rate, extends to cycles of every length, and is visible in a thousand-object shuffle.

When a count of dependent events seems to follow a simple limit, compute its factorial moments exactly. If they match the limit’s moments exactly up to some order, the approximation is not just good but good for a structural reason, and it will be good at sizes no listing can reach.