Editing SecretSanta
You are currently browsing as guest..
To change this, fill in the following fields:
Username
Password
Click here to reset your password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Tue Apr 23 12:51:43 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
COLUMN_START^ 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? ]]] <<| COLUMN_SPLIT^ [[[ 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 EQN:d_{n-1}+d_n. Then the probability that the last person has their own name is EQN:\frac{d_{n-1}}{d_{n-1}+d_n}. When /n/ is very large, this approaches EQN:\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. ]]] COLUMN_END 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 EQN:\frac{1}{3}*\frac{1}{3}*\frac{1}{2} and EQN:\frac{1}{3}*\frac{1}{2}*\frac{1}{2}. Now we can see that the probability of failing is EQN:\frac{1}{18}*\frac{1}{12} which is EQN:\frac{5}{36}. !! Conceptual summary [[[>50 COLUMN_START^ * BADC * BCAD * BCDA * BDAC COLUMN_SPLIT^ * CABD * CADB * CDAB * CDBA COLUMN_SPLIT^ * DABC * DCAB * DCBA COLUMN_END ]]] 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.