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 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}.$
|
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 |