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.