The other day, my sister found out she was the Secret Santa to her own Secret Santa. In other words, two classmates exchanged gifts in Secret Santa and my mom asked me “what are the chances of that?” Of course, I had to find out so I got to work on the problem. In this first part, I’ll just outline the main ideas. In the next part, I will fill in all of the mathematical details.
Here is a quick recap of how this works. My sister’s class has \(26\) students. Each student draws a name from a hat to see who they are a Secret Santa for. If you draw your own name then you put it back and then draw another one. Before looking at the answer, it may be worth it to see if you can guesstimate the answer. Is it something like \(1\%\), or \(10\%\), or something else? Is it more or less likely if we increase the number of students?
If you want to skip the math and just find out the answer, it turns out that the probability that at least two students exchange gifts among themselves is approximately \(39.34\%\). Now, this, in and of itself, may be a bit surprising. I would have intuitively expected this answer to be smaller. What’s potentially more surprising is what happens if we change the number of students. In the plot below, I’ve plotted the probability based on the number of students in the class. If the number of students is at most \(5\), there is some irregularity, which makes sense. For example, if there are \(3\) students, there is no chance of an exchange between two students – this is because no student can draw themselves.
Something interesting happens as soon as we get to \(6\) students – the probability seems to stabilise! I find it somewhat surprising then that the answer to our question essentially doesn’t depend on the number of students (as long as it’s not too small). To explain all of this, we need to talk about permutations.
Let’s work in generality here. Suppose we have \( n \) students, where \(n\geq 2\). Suppose that the draws from these students are \(x_1, x_2,\ldots, x_n\). Then, \(x_1, x_2,\ldots, x_n\) is just a rearrangement of the numbers \(1,2,\ldots, n\). In other words, a draw in our problem is equivalent to a permutation of the numbers \(1,2,\ldots,n\).
Now let’s recall how we compute probabilities: $$\text{probability} = \frac{\text{# succesful events}}{\text{# total events}}.$$ What is a valid event in our case? Recall that a student can’t draw themselves. This means that \(a_1\neq 1, a_2\neq 2,\ldots, a_n\neq n\). Such a permutation has a name: it is called a derangement. There is actually a formula for these things which involves factorials (\(1!=1, 2!=1\cdot 2, 3!=1\cdot 2\cdot 3, \ldots\)):
Theorem (Number of Derangements) Let \(D_n\) be the number of derangements for \(n\) students. Then $$D_n = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!} = n! \left(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\cdots + (-1)^n\frac{1}{n!} \right).$$ I won’t prove this theorem here but people that know about the inclusion-exclusion principle can try to prove it. Anyways, if \(n=26\), we get $$D_{26}=148362637348470189868449792$$
No, there’s no typo here. That is \(148\) million billion billion. That’s the total number of ways my sister’s class could have divided up their Secret Santa. This number is so big that if each school in the world (somewhere around \(5\) million) did a Secret Santa event every second of every day, each with a different arrangement, since the Big Bang (about \(13\) billion years ago), then by present day we will have gotten through about \(1.382\%\) of all possibilities. Let that sink in… If WordPress allowed me to add a “mind=blown” emoji here, I would do that.
Moving on, we now want to look at the number of “succesful events”. What constitutes a succesful event? We want our permutation to satisfy the requirement that \(x_1\neq 1, \ldots, x_n\neq n\) first of all. Moreover, we want at least two students to exchange gifts. It will actually be easier to first compute the number of permutations where no two students exchange gifts. For such permutations, we want to avoid the situation where, for example \(x_1=3\) and \(x_3=1\). (For those in the know, we want the number of permutations with no cycles of length at most \(2\).) Here is another theorem which I won’t prove in this post:
Theorem. The number of derangements with \(n\) students with no two students exchanging gifts is $$S_n=n!\cdot \sum_{b+2c\leq n} \frac{(-1)^{b+c}}{b!c!2^c}.$$ Scary! Let me explain the formula. Here, \(b\) and \(c\) are nonnegative integers such that \(b+2c\leq n\). So, for example, if \(n=6\) the possibilities are \((b,c)=(0,3), (2,2), (4,1), (6,0)\). So in this case our sum becomes $$S_6 = 6! \cdot \left( \frac{(-1)^{0+3}}{0!3!2^3}+\frac{(-1)^{2+2}}{2!2!2^2}+\frac{(-1)^{4+1}}{4!1!2^1}+\frac{(-1)^{6+0}}{6!0!2^0} \right)=160.$$ So now we can compute the number of unsuccesful (recall we’re counting these first) outcomes in our case of \(26\) students. We get: $$S_{26} = 89986488307675207011663872.$$ These are the unsuccesful outcomes so to get the number of succesful ones, we subtract this from the total number of outcomes, i.e. from \(D_{26}\) from above. We get \(58376149040794982856785920\). Another huge number but this means we can now solve our problem. The probability we were looking for is $$\frac{58376149040794982856785920}{148362637348470189868449792} \approx 39.34\%.$$
This is all nice but we still haven’t quite explained one phenomenon: why does the probability stabilize after \(n\geq 6\)? Let’s take the number of derangements again: $$D_n = n! \cdot \left(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\cdots + \frac{(-1)^n}{n!}\right).$$ It turns out (details to be filled in a future post) that the sum \(\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1)^n}{n!}\) approaches (as \(n\) gets larger) a certain value, namely \(\frac{1}{e}\), where \(e\) is Euler’s constant. So the number of derangements is approximately \(n!/e\). In fact, the approximation is very good even for small values of \(n\).
A similar fact holds for the number of succesful events, which happens to be approximately \(n!\left(\frac{1}{e}-\frac{1}{e\sqrt{e}} \right)\). So the probability of a succesful event is approximately $$\frac{n!\left(\frac{1}{e}-\frac{1}{\sqrt{e}} \right)}{n!/e}= 1 – \frac{1}{\sqrt{e}}.$$
If you’d like to send me any kind of message regarding this post, feel free to complete the form below!