Paper detail

"Secret Santa" and the Combined Length of Spanned Cycles in a Random Permutation

In many schools throughout the United States, it is customary to hold a yearly "Secret Santa" event. With the approach of Christmas, all the students place their names in a hat; each student, in turn, draws a name out of the hat, thus becoming Secret Santa to the student whose name is drawn. On the day before Christmas break, each student places a gift in front of the locker of the student to whom she or he is Secret Santa. Unfortunately, children being children, some students might forget to bring gifts on this day. Students who do not find gifts next to their lockers, feeling cheated, angrily take their gifts back from their recipients, who in turn reclaim their gifts from their recipients, and so forth. We analyze the distribution of the number $L$ of students whose Christmas is ruined, as a function of the number of students who do not bring gifts. We give a simple, explicit formula for the probability of every possible value for $L$ (backed by three proofs of distinct flavors), as well as closed-form formulae for its expectation and variance. Notably, we show that if $m$ kids forget to bring gifts, then the expected fraction of kids whose Christmas is not ruined is less than $\frac{1}{m+1}$ (regardless of the total number of students), with low probability for a large deviation from this fraction. The underlying theoretical results are applicable to the study of manipulation in matching markets within game theory.