The Math of Secret Santa
By Richard Low
15 Dec 2011
Category:
Technical Articles
This Christmas, my housemates and I took it in turns to pick names out of a hat for our annual Secret Santa. We agreed that if someone picked their own name we would put all the names back and try again. It took us 5 attempts before we found a 'collision-free' assignment. This made me think, is this to be expected? And how many times would it take us with more people?
This problem can be rephrased as counting the number of permutations that have no fixed points. Such permutations are called derangements and can be calculated with a reasonably simple recurrence, as follows.
Imagine there are n people, and use the notation !n to denote the number of derangements of n objects. The first person chooses a name, and has n-1 names to choose from without finding their own; the person they choose either takes the first name or doesn't. In the first case, the remaining n-2 people have to choose from their n-2 names, so can do this in !(n-2) ways. In the second case, there are !(n-1) possibilities, since each remaining person's name is still in the hat and they must not choose it for a valid assignment. This gives !n = (n-1)(!(n-1) + !(n-2)), with the base cases !0 = 1 (by convention) and !1 = 0.
Solving this, which is simple to prove by induction, we find the following:
You may recognize the sum as the first n+1 terms in the Taylor expansion of e^x evaluated at -1. This sum converges extremely quickly, so the probability of a successful Secret Santa assignment rapidly approaches 1/e ≈ 37% as the number of people grows. The number of trials until we find a successful assignment is thus Geometric(1/e), which has expectation e ≈ 2.72. Indeed, for n=5, the exact sum already gives expectation 2.7.
So what about our 5 attempts? Markov's inequality says that the probability that a random variable X deviates from its mean by more than a factor k is at most 1/k, so the probability that we need more than 5 attempts is at most e/5 = 0.543. A better, and easier, bound can be obtained for the geometric, since the probability that we need more than 5 attempts is the probability that we fail 5 times in succession, which is (1-1/e)5 ≈ 0.10, and this decreases exponentially rather than linearly in the number of attempts. (Question for reader: how many rounds do we need to succeed with probability > 0.99 ?) Most importantly, this is independent of the number of people n involved so in Acunu's Secret Santa, we should expect a similar number of rounds, even as Acunu continues to double in size every year!
If you eat this sort of thing for breakfast, you should join us!
blog comments powered by Disqus