Secret SantaYou are currentlybrowsing as guest. Click here to log in 

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


So I've been doing some calculations, and here are the results:
participants  of failure  
  
  
  
  
  
  
  
  
  
  
  
 
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 straightforward, 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}.$

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.
Last change to this page Full Page history Links to this page 
Edit this page (with sufficient authority) Change password 
Recent changes All pages Search 