Secret Santa Odds?

Question

If you are doing a Secret Santa gift game with 25 people, what are the odds of picking your own name?

Let's assume everyone writes their own name on a slip of paper, tosses it into a hat, and then everyone pulls a name from the hat. What are the total odds that one of the 25 people would pull their own name from the hat?

TO CLARIFY: I am asking the odds that when all 25 people open their slips of paper, what is the likelihood that ANY ONE of them has pulled their own name. Not the odds for any one individual (1/25), but for the group as a whole.

Thanks!

I mean AT LEAST one person pulling their own name.

I mean AT LEAST one person pulling their own name.

Answer 1

This is one of the harder counting problems I've seen. I did a computer simulation of up to 14 people so I could verify my answer. It took a while to think through how to solve it analytically.

I'll work at it from the opposite direction: find the probability of nobody picking their own name. Then we just subtract that from one to get the probability somebody (at least one) picked their own name.

I'll derive a generic formula for n people. First, the total number of ways for n people to pick is n! Next, subtract the number of ways one person can choose his own name. That's n times (n-1)! (the number of ways for the rest of the people to pick). n * (n-1)! = n! So far, the number of ways nobody picks their own is n! - n! This is 0, which is clearly not right, but we are not done. For now, we'll leave it as n! - n! and not simplify any further. You'll see why later.

Note that the number we subtracted out counts twice all those permutations where two people picked their own names. So, add back in: nC2 * (n-2)! That's the number of ways to choose the two people who got their own names, times the number of permutations of the remaining n-2 people. We can simplify this a bit:

nC2 * (n-2)! = n! / [ (n-2)! 2! ] * (n-2)! = n! / 2!

But again, we've now added back too many. So we need to subtract out all those permutations where three picked their own names: nC3 * (n-3)! Again, we simplify this to n! / 3!

You can see this process will keep on going up to n. So the total ways nobody picks their own name is:

n! - n! + n!/2! - n!/3! + n!/4! - n!/5! .... (-1)^n * n!/n!

The probability is that expression divided by n! so all the numerators cancel out:

1 - 1 + 1/2! - 1/3! + 1/4! ... (-1)^n/n!

An astute reader might notice that this similar to the form of the Taylor series for e^x, which is:

e^x = 1 + x/1! + x²/2! + x³/3! + x⁴/4! + x⁵/5! + ...

Let x be -1 and we have:

e^(-1) = 1 - 1 + 1/2! - 1/3! + 1/4! - 1/5! + ...

This series converges rather quickly, and by n = 12, has correctly approximated 1/e to 9 decimal places: 0.367879441. So, subtract this from one to get your probability: 0.632120559.

If this all seems a little complicated, it is. To visualize, try what I did and enumerate all the possibilities for a small number. n=4 seems a good one because it is large enough to begin to see what's going one, but small enough to easily write all permutations. Write ABCD, ABDC, ACBD, ACDB, ... all 24 combinations. Then, any combination with an A in the first position, B in the second, etc. has at least one correct. Now, use the logic described above and apply it to this set of permutations.

Answer 2

Good question!
Btw, when you say any one, do you mean AT LEAST one or EXACTLY one.

Northstar, how would one go about solving such a problem?

If you have to consider the probability of exactly one person pulling his/her own name, it would be something like this, I guess.
Probability of 1 person pulling own name = 1/25
Probability of 2 person NOT pulling own name = 23/25
Probability of 3 person NOT pulling own name (would depend on whether 2 has/has not picked 3). So this gets more and more complicated.

Would really appreciate if someone could explain how to solve this!!

Answer 3

Once the group gets above about the size of 10, the odds hardly change at all. The odds of at least one person drawing their own name is very close to

1 - 1/e ≈ .632

Answer 4

25 factorial, aka 25!

which ends up being 1.551121 × 10^25


i could be wrong, but it seems logical