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

Yannai A. GonczarowskiarXiv 2013 · DOI · arXiv

Abstract

In many social settings, "Secret Santa" gift exchanges are a popular tradition. However, these events are mathematically fragile. This paper models the exchange as a random permutation and analyzes the distribution of $L$, the number of participants whose holiday is "ruined" when $m$ individuals fail to bring a gift. We derive an explicit formula for the probability distribution of $L$, along with its expectation and variance. Our results show that even a small number of forgetful participants can trigger a massive chain reaction, typically ruining the holiday for the vast majority of the group.

Introduction

A Secret Santa event involves $n$ participants, each drawing a name to whom they will give a gift. This process defines a random permutation of the participants, which naturally decomposes into disjoint cycles. A "ruined" holiday occurs through a specific chain reaction: if a participant does not receive a gift, they reclaim the gift they brought. The intended recipient of that gift then reclaims their own, and so on. This process continues until every member of the affected cycle has had their gift reclaimed.

The central question addressed is: if $m$ participants forget to bring gifts, what is the distribution of $L$, the total number of people whose holiday is ruined?

Methodology

The study approaches the problem through combinatorial probability, providing three distinct proofs for the distribution of $L$:

  1. Probabilistic/Recursive Proof: An inductive approach calculating the distribution for $m$ forgetful participants based on the case for $m-1$.
  2. Enumerative Reduction: A counting argument that simplifies the general case to the scenario where all participants are ruined ($L=n$).
  3. Direct Enumeration: A bijective proof using cycle structure representations to map permutations to sets of integer compositions.

These methods rely on properties of rising factorials and identities within Pascal’s Triangle to establish robust closed-form solutions.

Key Insights and Results

The analysis reveals that the "chain reaction" is remarkably efficient at disrupting the exchange. The expected number of ruined participants is given by: $$E[L] = \frac{m(n+1)}{m+1}$$

This implies that the expected fraction of "saved" participants is less than $1/(m+1)$, regardless of the total population size $n$. For example, if only one person forgets a gift in a group of 100, the expected number of ruined holidays is 50. If two people forget, this number jumps to 67.

Evolution of the probability distribution of ruined participants $L$ as the number of forgetful students $m$ increases ($n=100$).

As shown in Figure 1, as $m$ increases, the probability distribution of $L$ shifts dramatically toward $n$ and becomes increasingly concentrated. For large $m$, the variance decreases, and the outcome becomes highly predictable: nearly everyone's holiday is ruined. Specifically, the probability that the entire group is ruined ($L=n$) is exactly $m/n$. In a school of 1,000 students, if 100 students forget gifts, one can expect more than 99% of the students to have their holiday ruined, with a standard deviation of less than 1%.

Conclusion and Applications

While framed as a holiday mishap, these results have significant implications for game theory and matching markets. The "Secret Santa" model describes "spanned cycles" in permutations, which are critical for understanding how small disruptions or manipulations can propagate through a system. The scale invariance of the expected fraction of saved participants suggests that large matching markets are just as vulnerable to small-scale failures as smaller ones. This work provides a foundation for studying the limits of manipulation in algorithmic game theory and matching market design.

Summary updated

Abstract

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.
BibTeX
@misc{gonczarowski2013secret,
  author = {Yannai A. Gonczarowski},
  title = {{"Secret Santa" and the Combined Length of Spanned Cycles in a Random Permutation}},
  year = {2013},
  eprint = {1307.4322},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1307.4322},
}

Loading related content...

Figure