Secret Santa

Secret Santa is a process that allows $n$ people to give each other presents, so that each person gives a single present and receives a single present. At the beginning each of the $n$ people write their name on a slip of paper and put the slip into a hat. Each person takes a random slip from the hat. If the slip has their name they draw another random slip from the hat and then put the slip with their name back into the hat. At the end everyone buys a Christmas present for the person whose name is on the slip they are holding. This process will fail if the last person draws their own name.

In this variation each of the $n$ people gives and receives two presents. At the beginning each of the $n$ people writes their name on two slips of paper and puts the slips into a hat (there will be $2n$ slips of paper in the hat). As before each person takes from the hat a random slip that does not contain their own name. Then the same person repeats this process thus ending up with two slips, neither of which contains that person’s own name. Then the next person draws two slips in the same way, and so on. The process will fail if the last person gets at least one slip with their own name.

Define $q(n)$ to be the probability of this happening. You are given $q(3) = 0.3611111111$ and $q(5) = 0.2476095994$ both rounded to 10 decimal places.

Find $q(100)$ rounded to 10 decimal places.

This is a quite complex problem, needing a significant amount of mathematical sophistication and some knowledge around combinatorics and probability.

The process described can work for n=1 and n=2, but fails for n=3 (as described, the failure probability is just over one third). Essentially, the person to pick last will always pick their own slips, as everyone else has already picked. However, as you increase n, the probability of the last person getting at least one of their own slips becomes less, since there are more slips in the hat to start with and hence a greater number of choices. Hence q(5) is less than q(3).

To compute q(100) from first principles would be quite complicated, requiring a summation of products of probabilities over all possible drawing sequences.

This formula has the general form:

q(n) = 2/n + sum(2(i-2)/[(n(n-1)]*[q(i-1) + q(i-2)*(1-q(i-1))]) for i=3 to n

The summation term represents the situations where the next person to draw selects a slip that has been put in the hat by one of those who has already drawn (i-2 choices out of the n(n-1) ways of selecting two slips from the hat) multiplied by the probability that after i-1 people have drawn the procedure hasn’t yet failed.

You would start from your base cases, so for n=1, q(1) = 0, and for n=2, q(2)=0, then use your formula to calculate: q(3), q(4), …, all the way up to q(100).

Unfortunately, it is impractical to attempt to calculate q(100) exactly or even to 10 decimal places by hand, because the formula involves a long sequence of calculations. This is definitely a task that needs a computer program to be written to do the calculation.

An approximation approach might be more practical for a hand calculation. For example, you might attempt to fit a function to the given q values and extrapolate to n=100. However, you’d need more data points and a conjectured form for the function. For example, for the data given, a simple linear extrapolation between q(3) and q(5) falls fairly short and is unlikely to give accurate results.

So unfortunately, practically calculating q(100) rounded to 10 decimal places is outside the scope what we can do by hand.

More Answers: