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 their name. Therefore, the interesting cases start 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}
Let me explain the above expression. First, the total number of possible name-drawings is equal to the number of ways to permute \(N\) items, which is \((N!)\). You can think of the people lined up 1 by 1, and we arrange the names to each person. Therefore, the total number of possible outcomes is equal to the total number of ways to permute \(N\) items, namely \((N!)\). This will be the denominator.
For the numerator, a person drawing their name means that the choice of that name's position is fixed. Therefore, the first task is to choose \(k\) out of \(N\) people to have their names fixed. For that, we have \(\binom{N}{k}\) ways to pick out \(k\) people out of \(N\). Then, for the remaining \((N - k)\) people, we can arrange the names they draw however we want. It can happen that some of the people in this group draw their names, but we don't care about that scenario because we are calculating the probability that at least \(k\) people drew their names, which is covered in \(\binom{N}{k}\). Therefore, for the remaining \((N - k)\) people, their names can freely permute, with \((N - k)!\) permutations in total.
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 one person drew their 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 their 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 their 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.