I ran a million Secret Santa draws through my generator. Here's what the paper hat gets wrong

I run a small Secret Santa generator. Before this year's rush I wanted two things: proof that its draw is actually fair, and real numbers for the problems people hit when they draw names from a hat. So I took the draw module the server runs (TypeScript, about 400 lines), ran it in Node on a laptop and counted what came out.

Every simulated draw below got a fresh 128-bit seed from crypto.getRandomValues, the same way the server seeds it. Where an exact answer exists I computed it separately, by formula or by listing every possible draw, and checked the simulation against it.

1. The hat fails about 63% of the time

Put everyone's name in a hat, let everyone pull one. The chance that at least one person pulls their own name:

From 6 people up the number stops moving. A draw where nobody gets themselves is a derangement, and the share of shuffles that are derangements converges to 1/e (36.8%) almost immediately, so the failure rate sits at 1 − 1/e and the expected number of full draws sits at e, about 2.72.

As a sanity check I shuffled 8 names 1,000,000 times with a plain Fisher–Yates shuffle. 632,287 shuffles had at least one person holding their own name: 63.23%, against an exact 63.21%.

I keep a version of this table, along with what to do when it happens, on the Secret Santa rules page.

2. "Just redraw that one person" is worse than it sounds

The usual fix at the table: if you pull your own name, put it back and draw again. Two things go wrong.

First, the last person can be left holding only their own slip. Second, even when it works, the pairings are no longer equally likely. People who draw early pick freely, people who draw late get what's left, so some complete pairings can be reached in many ways and others in very few.

I computed both exactly by walking every possible sequence of draws:

In each case the gap between the most and least likely full outcome was exactly n − 1. Nobody at a party will notice a 5× bias, but it's the kind of thing a generator should not have. The only paper method that stays fair is the boring one: if anyone gets themselves, everyone puts their slip back and you start over.

3. What the generator does instead: shuffle, check, start over

That boring method is also the right algorithm. Shuffle uniformly, check every rule, and if anything fails, throw the whole shuffle away. Conditioning a uniform distribution on "the result is valid" gives a uniform distribution over valid results, so no valid draw is favoured.

A stripped-down version:

// allowed(g, r): may g give to r? (g !== r, plus any exclusions) function drawNames(n, allowed, rng) { const a = Array.from({ length: n }, (_, i) => i); for (let tries = 1; ; tries++) { for (let i = 0; i < n; i++) a[i] = i; let ok = true; for (let i = 0; i < n && ok; i++) { const j = i + rng.int(n - i); // forward Fisher–Yates [a[i], a[j]] = [a[j], a[i]]; ok = allowed(i, a[i]); // a[i] is final now, so check it early } if (ok) return { receivers: a, tries }; } } 

Bailing out at the first broken rule is safe because the rejected attempt is discarded whole. The real module also checks up front that a valid draw exists at all (more on that below) and caps the number of attempts, so it can't spin forever.

Results from 1,000,000 draws of 8 people through the real module, no exclusions:

• Average attempts: 2.719 (exact: 2.718)
• Worst case: 32 attempts
• Time: about 7.5 µs per draw on my laptop
• The slower fallback for very tight rules was never needed

Is it actually uniform? With 5 people there are exactly 44 valid draws. In 440,000 runs each one should show up about 10,000 times. The rarest came up 9,826 times and the most common 10,204. A chi-square test gives 27.8 on 43 degrees of freedom, p = 0.96: nothing to see. I ran the same test on 6 people with 2 couples kept apart (116 valid draws, 400,000 runs each time) six times: p = 0.04, 0.54, 0.73, 0.96, 0.24 and 0.74. One run in twenty lands under 0.05 by chance with a fair draw, and the reruns of that setup scattered the way they should.

4. What exclusions cost

Couples who shouldn't draw each other are the most common rule. Every rule removes valid draws, so the shuffle gets rejected more often:

For a computer, 8 attempts is nothing; the 200-person case took about 5 ms per draw, most of it the up-front feasibility check. For a group doing it by hand with slips, "everyone puts their slip back" nine times in a row is where the evening goes. This is the case the generator with exclusions exists for.

5. Households and the "half" limit

Families usually want more than couples apart: everyone under one roof. That has a hard limit, and it's a textbook result. A draw exists only if every group of givers has at least as many allowed recipients as it has members (Hall's condition). A household of k people needs k recipients outside the house, so a household can be at most half the group.

Exact counts for 10 people with one household kept apart:

At exactly half, the draw is forced into two teams: every household member buys for someone outside and every outsider buys for someone inside, 5! × 5! = 14,400 ways. Rejection sampling still copes at 252 attempts. One more person in the household and there's no valid draw, so instead of looping the module returns the blocking group: in my 6-of-10 test, five household members who between them could only give to four people. I go through the family version of this, with several households and kids, on the family Secret Santa page.

6. Mutual pairs, and why there's a "one big circle" switch

A uniformly random valid draw often contains two people who buy for each other. That's legal, but some groups find it flat:

The million-draw run agreed: 39.42% of the 8-person draws had a mutual pair and 33.96% formed one loop.

If you want a single chain (A gives to B, B to C, and the last person back to A), the generator has a one-big-circle mode that uses Sattolo's algorithm instead of Fisher–Yates. It's the backward Fisher–Yates loop with one small change, j = rng.int(i) instead of rng.int(i + 1), and it produces every single loop with equal probability. No mutual pairs and no separate loops by construction; with no exclusions it always passes on the first attempt, and with 4 couples among 8 people it took 3.39 attempts on average. The chain is handy when the reveal happens on a call: each person opens their gift, says who they had, and that person goes next. I wrote up how that works for remote teams on the virtual Secret Santa page.

7. Two smaller things that turned out to matter

• Seeds make draws auditable. Every draw stores its 128-bit seed and runs it through a small PRNG (sfc32). Same seed and same inputs give the same result, so if someone says "the draw was rigged", it can be replayed.
• Tight rules need a fallback, but a labelled one. If rejection sampling hasn't found a valid draw within its budget, the module switches to a randomized search plus random swaps that keep every rule. That's only approximately uniform, so the result records which method produced it. In all the runs above it never triggered.

The short version

• A paper hat draw fails about 63% of the time for any group of 6 or more.
• Redrawing only the unlucky person can strand the last drawer (9 to 14% of the time in groups of 4 to 8) and makes some pairings up to n − 1 times likelier than others. Restart from scratch instead.
• Couples cost you roughly 5 to 9 full draws. Fine for code, painful with slips.
• No household can be more than half the group.
• In groups of 6 or more, about 39% of random draws contain a mutual pair; a single-loop draw avoids that.

I built secretsantagenerator.xyz. An AI agent working for me ran these simulations on the generator's draw code and wrote this post from the results, with no line-by-line human edit, so it's marked as AI-generated. The exact counts don't depend on randomness; the simulated figures should land within a fraction of a percent if you rerun them.