Secret Santa
AllPages
RecentChanges
Links to this page
Edit this page
Search
Entry portal
Advice For New Users
Here's one analysis ...

The process guarantees that the first 9 won't have their own names. How many arrangements are there?

If the last person does have their own name then the first 9 have a derangement. If the last person does not have their own name then all 10 form a derangement. Total number is $d_{n-1}+d_n.$

Then the probability that the last person has their own name is $\frac{d_{n-1}}{d_{n-1}+d_n}.$

When n is very large, this approaches $\frac{1}{n+1}.$ The exact numbers are:

  • For 5 people: 9/(9+44) = 0.1698...
  • For 7 people: 265/(265+1854) = 0.125059...
  • For 10 people: 133496/(133496+1334961) = 0.090909029...

This turns out to be wrong! The different derangements are not, in fact equally likely.

There are many Secret Santa problems. The one we're interested in here is this:

Suppose 10 people decide to participate in a "Secret Santa". Their names are put into a hat, and one by one each takes a name out. If it's their own, they put it to one side, choose another, then return their own to the hat. They then retain the name they've chosen, which is clearly not their own.

So all but the last are guaranteed to end up with a name other than their own.

What is the probability that the last person ends up with their own name?

So I've been doing some calculations, and here are the results:

Number of
participants
Probability
of failure
Evaluated
1
1
1.000000
2
0
0.000000
3
1/4
0.250000
4
5/36
0.138889
5
19/144
0.131944
6
203/1800
0.112778
7
4343/43200
0.100532
8
63853/705600
0.090495
9
58129/705600
0.082382
10
160127/2116800
0.075646
11
8885501/127008000
0.069960
12
1500518539/23051952000
0.065093

These results match exactly those of the simulations I've been running, so I know they're right. They are strange numbers, though, so where do they come from?

Being so strange you might imagine that the calculations aren't simple or straight-forward, and they're not. The calculation for N=1, 2 or 3 aren't very enlightening. Here's the full calculation for N=4.

We're choosing from A, B, C and D. A can't go first, so we have three choices, and they're equally likely. Here's a table for the next choice:

Chosen Next
choices
B A, C, D
C A, D
D Don't
care

In the last case we don't care because we're trying to compute the probability of the process failing. With D selected it can't fail.

But now we have 5 ways to continue: BA, BC, BD, CA, CD, and their probabilities are not equal:

Chosen Prob Next
BA 1/3 * 1/3 D
BC 1/3 * 1/3 A, D
BD 1/3 * 1/3 A
CA 1/3 * 1/2 B, D
CD 1/3 * 1/2 A, B

We only care if we get D last, so the only options we get are BCAD and CABD. The probabilities of these are $\frac{1}{3}*\frac{1}{3}*\frac{1}{2}$ and $\frac{1}{3}*\frac{1}{2}*\frac{1}{2}.$

Now we can see that the probability of failing is $\frac{1}{18}*\frac{1}{12}$ which is $\frac{5}{36}.$

Conceptual summary

  • BADC
  • BCAD
  • BCDA
  • BDAC
  • CABD
  • CADB
  • CDAB
  • CDBA
  • DABC
  • DCAB
  • DCBA
We can enumerate all the possible results, shown at right. The point is, though, that these are not all equally likely. There are 3 possibilities for the first choice, but if you choose B then there are three choices next, whereas if you choose C there are only two choices next. In each case, the choices are equally likely.

And that's what makes the calculations so very difficult.

I've written a program to compute the results precisely, but there's very little insight to be gained from them. Each takes longer than the previous, and it's not fast. The case N=12 took 53 minutes, the next is computed to take 12.5*53 minutes, or about 11 hours.

Or so.

Next step ...

The next stage will be to try to find a recurrence formula for the problem, but I've not had time to work on that yet. If anyone has a clean recurrence formula then I'd love to hear from you, otherwise this puzzle will continue to occupy my occasional free moments.

Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout