Last week I attended a presentation where the speaker asked everyone in the audience to take off their shoes, and to put them together at the front of the room. The speaker then asked each person to select and pick up a pair of shoes that was not his/her own.

Strange presentation, huh? There was more to it than that; I will leave it to the reader to imagine where things could possibly have gone from there. But just that initial selection process presented an interesting problem. How easy– or difficult– is it for a group of people to redistribute their shoes so that no one has his or her own pair?

This problem has received plenty of attention, so much so that it is commonly known by several different names, from the “hat-check problem” to “*le probleme des recontres*.” There are some very cool mathematics involved… but the subject of this post is a variant that I think is more realistic, and consequently less well-behaved.

I will re-phrase the problem in the context of the common “Secret Santa” holiday gift exchange. Suppose that a group of people (e.g., your family or co-workers) want to exchange gifts, with each person buying a gift for one other person in the group. The usual approach is to write each person’s name on a slip of paper, put all of the slips into a hat, and have each person in turn take a slip from the hat. If a person draws a slip with his own name on it, he returns the slip to the hat and selects another. Each person then buys a gift for the person named on the drawn slip.

The resulting assignment mapping each person in the group to his or her gift recipient is a derangement, or permutation of persons in the group with no fixed points. The process of drawing names from the hat is effectively a means of generating a random derangement.

There are two interesting observations about this process. First, it can break: it is possible for the last person to draw to find that the only remaining slip in the hat has his own name on it. What happens then? Earlier in the process, drawing your own name is remedied by simply returning the slip and drawing another. But for the last person there is no other slip to draw.

It is a nice probability puzzle to determine how frequently this situation occurs. I do not yet know the answer as a function of the group size , other than for some specific small . Let me know if you find a solution. [*Edit*: Over a year later, there is a description of the solution to this problem here.]

The second observation is that the process is not as random as you might think. Even if we discount the “end of the line” failure described above, the resulting distribution of derangements that are generated is nowhere near uniform. That is, suppose that if the last person gets stuck with his own name, we simply return all of the slips to the hat and start over, effectively conditioning the resulting permutation on the failure not occurring. We can consider the resulting probability distribution of derangements that are generated… and we would like that distribution to be uniform, so that each assignment is equally likely.

Some initial experiments suggest that the most extreme deviations occur where you might expect, namely for the last person to draw a slip. For example, the last person in line is *least* likely to end up buying a gift for the *first* person in line, and is *most* likely to end up buying for the person *next to last* in line.

What I did not expect was the extent of the difference; the ratio of those two probabilities is nearly two to one (for , the largest group that I looked at, the ratio is approximately 1.94869)!

We can draw a couple of conclusions. First, we can fix these problems very simply with a more extreme rejection algorithm: everyone draws a slip, and after everyone has drawn, if *anyone* has his or her own name, then return all of the slips to the hat and start over. This guarantees uniformity, and the usual hat-check problem solution now applies, so that we can expect to have to re-draw only about times.

Of course, the second conclusion is that if you are Charlie Brown in love with the little red-haired girl, and you want to be her Secret Santa, then the drawing order that maximizes your chances is with you and her at the end of the line, with you drawing last. Good luck.

If you have a Secret Mastermind, you can also even the probabilities by having the drawing person assign the gift giver for the currently drawn name to the next name drawn… then the last name is given a gift by the first. And no re-draws needed. Obviously if this is done publicly with the hat, absolutely nothing is secret 🙂

-bill

This is an idea I hadn’t thought of. The resulting permutation is a (n-)cycle, with each of the (n-1)! possible cycles being equally likely, and thus P(i draws j) is 1/(n-1) for all i,j. This approach would also have the nice property that, on gift-opening day, someone could open their gift, announcing who it was from, then that person could open their gift, announcing who it was from, and so on… this process would continue through the entire group, ending with the last person opening their gift from the first person to open.

On the other hand, this approach yields only a small fraction (5-10% for typical group sizes) of all of the possible derangements, so a lot of gift assignments would be prohibited, such as some pair(s) of persons exchanging gifts. That is, a derangement is any permutation with no 1-cycles (fixed points); this approach yields only permutations with a single n-cycle.

Also, as you point out, if we don’t draw names publicly, but instead have a Secret Mastermind, then s/he may as well conduct whatever procedure s/he wants… such as running a computer program to pseudo-randomly generate an arbitrary derangement :).

Pingback: Secret Santa Revisited | Possibly Wrong

Pingback: Secret Santa puzzle | Possibly Wrong