December 6, 2020
"From Christopher “CJ” Halverson comes a bibliophilic game of Secret Santa:
Every year, CJ’s family of five (including CJ) does a book exchange for Christmas. First, each person puts their name in a hat. The hat is shaken, and then each person draws a random name from the hat and gifts that person a book. However, if anyone draws their own name, they all put their names back into the hat and start over.
What is the probability that no one will draw their own name?"
Answer: \(\frac{11}{30}\)
Explanation:
We are going to solve the general case for \(N\) people, such that the above case would just be when \(N = 5\). Obviously when \(N = 1\), that person is guaranteed to draw his/her name. Therefore, the interesting cases starts with \(N = 2\). Using the indirect method as aforementioned, we have: \begin{align} & &P(\text{No one draws their own names}) \\ &&= 1 - P(\cup_{k=1}^N \text{Exactly k people draw their names}) \\ \end{align} Where \(\cup_{k=1}^N\) means the union of cases from 1 to N. Now, instead of focusing on the exact figure, we can instead focus on the probability that at least \(k\) people drew their names, as the expression is intuitive and simplifies nicely: \begin{align} & &P(\text{At least k people drew their names out of N names}) \\ & &= \frac{\binom{N}{k}(N-k)!}{N!} = \frac{\frac{N!}{k!(N-k)!}(N-k)!}{N!} = \frac{1}{k!} \\ \end{align}
Now we can combine our two results to derive at the solution. The union of probabilities where exactly \(k\) out of \(N\) people that drew their own names would simply be the probability that at least 1 person drew his/her name, subtracting the probabilies where at least two people drew their own names as we double-counted this case, then adding back the probability where at least three people drew their names, and so on, until \(k\). In other words: \begin{align} & &P(\text{No one draws their own names}) \\ &&= 1 - P(\cup_{k=1}^N \text{Exactly k people draw their names}) \\ &&= 1 - (\frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + \dots + \frac{(-1)^{N+1}}{N!}) \\ &&= \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} + \dots + \frac{(-1)^{N}}{N!} \\ &&= \sum_{k=2}^N \frac{(-1)^k}{k!} \end{align} And so when \(N = 5\), we have: \begin{align} P &= \sum_{k=2}^5 \frac{(-1)^k}{k!} \\ &= \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} \\ &= \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120} \\ &= \frac{11}{30} \end{align}
In the limit, as \(N \to \infty\), the probability can be evaluated in the limit after realizing the sum is just the Taylor Series expansion of \(f(x) = e^x\) evaluated at \(x = -1\), and so we have: \begin{align} P(\text{No one draws their own names for large N}) \to e^{-1} \approx 0.368 \end{align}
It is surprising that as N gets very large, the probability converges to \(e^{-1}\) instead of say going to 0 or 1. This can be explained by the fact that there are two forces at play here when N goes to infinity. First, as the number of people drawing names increase, the potential for at least one person to draw his/her name goes up. On the other hand, for each person, the pool of names gets very large and so the potential for each individual person drawing his/her name goes down. The balancing point is \(e^{-1}\).
I have simulated two cases. First, when \(N = 5\), the book drawing is simuated with updated Monte-Carlo probabilies of up to 1 million that quickly converge to the reference value of \(\frac{11}{30}\):
The second simulation is taking N from 1 to 100. Note that the simuated value reflect well with the theory. When \(N = 1\), the probability is of course 1. When \(N = 3\), we have \(P = \frac{1}{2} - \frac{1}{6} = \frac{1}{3}\), and when \(N = 4\), we have \(P = \frac{1}{2} - \frac{1}{6} + \frac{1}{24} = \frac{3}{8}\). Those are the transient states as seen in the bar graph of the simulated results, but thanks to factorial decay, the subsequent Monte-Carlo trials quickly converge to the theoretical value of \(e^{-1}\).
Please find the Simulation Code here.