The Secret Santa hat fails about 63% of the time
Put ten names in a hat, pass it around, and there's a 63% chance that at least one person pulls their own. That isn't a one-in-ten problem. It's closer to two in three.
A bigger group doesn't help. With 3 people the hat fails 66.7% of the time, with 4 it's 62.5%, with 5 it's 63.3%, and from about 8 people on it sits at 63.21% and stays there. An office of sixty: still 63.21%.
Where 63% comes from
Number the people 1 to n. However the slips come out of the hat, that's a shuffle, and there are n! of them (3,628,800 for ten people). A draw is usable only if nobody ends up holding their own number. Mathematicians call a shuffle like that a derangement. Here are the counts for small groups:
| People | All shuffles | Usable | Hat works |
|---|---|---|---|
| 3 | 6 | 2 | 33.33% |
| 4 | 24 | 9 | 37.50% |
| 5 | 120 | 44 | 36.67% |
| 8 | 40,320 | 14,833 | 36.79% |
| 10 | 3,628,800 | 1,334,961 | 36.79% |
The last column wobbles for a few rows and then locks onto 36.79%, which is 1/e, where e = 2.71828 is the number that turns up whenever something grows continuously. The usable count is n! times (1 − 1 + 1/2 − 1/6 + 1/24 − ...), the start of the series for 1/e. The terms shrink so fast that by 8 people the hat's odds are within a thousandth of a percentage point of it.
So if your family throws everything back in the hat whenever someone gets themselves, expect about 2.7 attempts. Irritating, but fair.
The two fixes that quietly cheat
Nobody wants to redo the whole hat, so people patch it. Both patches always give a usable draw. Neither gives an even one. I know because I had the code list every possible outcome for small groups and count how often each one came up. Take four people, Ana, Bob, Chloe and Dev. There are 9 usable draws, so a fair method lands on each of them 11.11% of the time.
Swap with the next person. Shuffle once. Anyone holding their own name trades slips with whoever is next to them. One draw (Ana gives to Dev, Bob to Ana, Chloe to Bob, Dev to Chloe) comes up 33.33% of the time, three times its share. Two others come up 4.17%. With five people the likeliest draw is 13 times as likely as the least likely.
Put it back and draw again. People draw in turn, and anyone who pulls their own name returns it and picks again. Every individual pick is random, which is why it feels fair. It isn't, because the early drawers have more choices than the late ones. If the last person is left with only their own name, everyone starts over (that's 13.89% of the time with four people). Even so, the likeliest draw is 19.35% and the least likely 6.45%, a ratio of 3. For five people the ratio is 4.
At a family party none of this matters much. In code it does, because a result that looks random is exactly how this sort of bias gets shipped without anyone noticing.
What a fair draw does
Shuffle the whole group properly. Look at the result. If anyone has themselves, or a couple has each other, throw the shuffle out and do it again. Every usable draw started out equally likely, and the check removes only unusable ones, so the usable ones stay level with each other. That's the whole method. It costs about 2.7 shuffles on average, which a computer won't notice.
Pairs who swap gifts
In a fair draw with ten people, 39.3% of the usable draws (525,105 of 1,334,961) contain at least one pair buying for each other. If you'd rather avoid that, you can ask for one big loop, where Ana gives to Chloe, Chloe to Ed, and so on until the chain comes back to Ana. You have to ask, though. At ten people only 27.18% of usable draws are single loops, so a plain shuffle rarely lands on one by chance.
The longer version has the couples math and a calculator for your own group size: the mathematics of Secret Santa. The generator that uses all of it is at cipher.ink/secret-santa. It draws in your browser, and the server only ever stores sealed links.
The full version
Couples, one big loop, Hall's theorem, and a calculator that counts the draws for your own group.
Read it on cipher.ink Run a Secret Santa