Secret Santas I
Probability puzzles require you to weigh all the possibilities and pick the most likely outcome.
A group of about twenty friends decide to exchange gifts as secret Santas. Each person writes their name on a piece of paper and puts it in a hat and then each person randomly draws a name from the hat to determine who has them as their secret Santa.
What is the probability that at least one person draws their own name?
HintThe probability converges on a single value as the number of people approaches infinity. At ten people the probability is accurate to better than 1 millionth for any number more than ten people.
1 - 1/e
or approximately 0.63212
where e is the mathematical constant (e ~ 2.71828).
This comes from the number of derangements (permutations in which no element appears in its original position). There are n! ways to draw n names out of the hat. There are [n!/e + .5] derangements of n elements (where [x] is floor x--the integer portion of x). This gives:
[n!/e + .5] / n!
as the probability of nobody drawing their name.
Ignoring the .5 added for rounding (which becomes increasingly insignificant as n increases) this gives
(n!/e) / n!
= n!/e * (1/n!)
Subtract this from 1 to get the probability that somebody draws their own name.
Jan 05, 2009
|OK, javaguru - I got the right answer for high n, but I got more than the stated deviation for the cases n=10 and n=20 (base case).|
Here's how I approached it: for 20 to NOT draw their own name, the probability is (19/20)^20, or approx. 0.3585. The complementary probability of "at least one" would of course be 1-.3585 = .6415. More generally, p = 1 - [(n-1)/n]^n, which for large n, converges on the value you indicated. But by this method I do not get the "within a millionth" for moderate n, such as n=10 (or even somewhat higher). More precisely, I get for p(n): p(10) = .6513; p(20) = .6415; p(100) = .6340; p(10,000) = .6321. Do you agree? Or - what am I missing in my approach?
Thanks for another fun math teaser.
Jan 06, 2009
|You can't use the "19/20" of not picking their name exponentially to get the true probability. It is an approximation that is quite poor at low n, but improves as n increases. The reason is because the piece of paper that is removed from the hat carries information--it must NOT be the name of the person who drew it. This information has to be accounted for when calculating the odds for the next person. Because you know that all the people drawing names before have not drawn their own name, the probability that the next person will draw their name is reduced because the probability that their name has already been drawn is increased.|
This is easily demonstated at low values of n. With two people, the probability of each one drawing their own name is 50%, so the probability of not drawing their name is also 50%. (1/2)^2 is 1/4 or .25, but the actual probability is 1/2 because if the first person doesn't draw their own name, the second person can't either.
At three people (2/3)^3 is 8/27 or .296 but the actual probability is 1/3. (There are 3! = 6 permutations of ABC and only two--CAB and BCA--have none of the elements in their original position.) Instead of (2/3)^3 for not picking your own name the conditional probability is actually:
(2/3) for the first person (A) not picking their own name;
this leaves either AB or AC; this means that the second person to draw a name (B) has a
(1/2)*(1/2) + (1/2)*1 = 3/4
probability of not picking their name, which is greater than the 2/3;
for the last person if the first two have not picked their name then one of three cases has occurred:
A picked C and B picked A, leaving B
A picked B and B picked A, leaving C
A picked B and B picked C, leaving A
that leaves a 2/3 chance that the last person C won't pick a C.
(2/3)*(3/4)*(2/3) = 1/3
probability that none of them pick their own name.
As n increases, the impact of each person not picking their own name decreases, improving the approximation, but the error will always be much higher than the error introduced by eliminating the integer rounding in 1 - 1/e.
Jan 08, 2009
|It was hard for me becuase I'm not good with math.|
Aug 20, 2010
|The exact answer I got (for n people) is 1/1! - 1/2! + 1/3! - 1/4! ... 1/n! which converges to 1 - 1/e for large n.|
Back to Top