Tuesday, December 30, 2014

Secret Santa Problems (Part II)

This post is in English now, since this is exactly the version of Secret Santa we played at our lab's Christmas party. I could not find the results of this post anywhere in the internet, but they probably appear somewhere. Possibly they are wrong.

This post is the second part to my previous post "Wichtel-Probleme".

Let's play Secret Santa again! Usually, at the beginning of the Christmas season all $n$ players would fix a derangement, which is a permutation of all players' names such that no player ends up with his or her own name. Naturally, this derangement is anonymous, i.e., a given player only knows which name he got assigned, and nothing else. The problem of finding a proper assignments is quite complicated, as the number of derangements is given by the sub-factorial

$$!n = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}$$

which for large $n$ quickly approaches a fraction of $1/e$ of all $n!$ permutations. Hence, only about 36% of all arrangements are proper, i.e., derangements. Typically, one would not want to play something like that in an office with 30 or more employees, since the process of drawing names can be quite time consuming (but see this blog post by Martin Eden about an algorithm ensuring a proper permutation).

Instead, let us play a different version of Secret Santa: Every player brings a wrapped gift and deposits it on a nicely decorated table. Then, the players take turns and draw exactly one gift. Let us assume that none of the players will choose his or her own gift -- that wouldn't be fun, would it? But what if a player has no choice? This brings us to the question of this post:

What is the probability that the last player has to take home his or her own gift?

Clearly, if there are just two players, this situation cannot occur: Either both players get their own gifts, or none does. Since the first option is ruled out, for $n=2$ this probability is zero. And for three players? Let's look at the following table listing all six possible permutations of gifts. Invalid permutations (those in which any of the first two players takes his or her own gift) are crossed out.:

1 2 3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Of all six permutations, only three follow the given rules, and of these only one (indicated in red) makes the last player draw his or her own gift. Hence, the probability is 1/3.

Let's generalize this:

How many permutations end up with the last player taking his or her own gift, given that none of the first $n-1$ players take their own gifts? And how many permutations are there such that the first $n-1$ players do not take their own gifts?

The ratio between the answers of these two questions is the desired probability.

The first question is easy to answer: Just fix the last gift to the last player and count the number of derangements for the first $n-1$ players; the result is $!(n-1)$. The second question is a bit more tricky, and I am not sure if the result is correct. Intuition tells me that the result can be obtained by complete induction or a different kind of recursion, but maybe also the following reasoning is correct: Essentially, there are just two options for the first $n-1$ players not to take their own gifts. Either all $n$ gifts are properly deranged, or the first $n-1$ gifts are deranged and the last gift is fixed. These two options are exclusive: If all $n$ names are deranged, the last gift has to be taken by any of the first $n-1$ players. Hence, we can add the possibilities of these two options; $!n$ for complete derangements and $!(n-1)$ for derangements with the last gift fixed. The probability that the last player has to take home his or her own gift is thus

$$ \frac{!(n-1)}{!(n-1)+!n} $$

The picture below shows that this probability decreases approximately by $1/n$ with the number of players. The more, the merrier!



By the way: The number of derangements with $k<n$ fixed points (i.e., exactly $k$ players take home their own gifts) is given by the Recontres numbers. However, given our rule, more than one fixed point cannot occur.