A Christian Liberal Arts University, Est. 1846

The Secret Santa Problem Continues

  • Project Type: Directed
  • Directed Project Contributors: Project Contributors: Daniel Crane, Tanner Dye

Purpose / Abstract

We explore the Secret Santa gift exchange problem. A group of N people draws names at random, giving a gift to the person drawn. First, we examine the probabilities of gift exchanges under various scenarios when everyone draws names at once. We then consider the probabilities of certain gift exchanges when people take turns drawing names and develop a strategy to maximize the likelihood of receiving a gift from the most generous participant.

Introduction / Background

Secret Santa gift exchanges are a popular Christmas tradition. In a Secret Santa gift ex- change, a group of n people draws names at random, with the requirement that a person can not draw him or herself. Then each person gives a gift to the person drawn.

There are several ways to design a Secret Santa gift exchange. Previous work done on these gift exchanges [2, 5, 6, 9, 10] usually operates under the assumption that everyone is equally likely to give a gift to any other person in the gift exchange, which is true when everyone draws a name at once. In Section 2, we summarize some of these results and also apply results proven in other contexts to Secret Santa. We consider cases where everyone is single, where all participants are in families of size k, and where participants are in families of different sizes. The probability of needing to redraw names depends on family size when we do not allow family members to give gifts to each other. Rook polynomials allow for calculation of this probability. Other techniques such as the inclusion-exclusion principle and bounds on permanents of matrices can be used for studying he limiting behavior of these probabilities when the number of participants in the gift exchange increases.

Next, in Section 3, we examine probabilities of allowed gift exchanges when names are drawn one at a time as opposed to all at once as in Section 2, and we then determine which kinds of exchanges are more likely than others. Specifically, we show that the order of drawing names affects to whom each participant is most likely to give a gift. In this type of gift exchange, the probability of any one derangement can be written as a product of terms involving an indicator function, and this allows us to compare the probabilities for two different giver-recipient pairs. We find that each person is most likely to give to the person drawing directly before him, with the first person to draw being most likely to give a gift to the last person to draw. Furthermore, we find that the last person to draw is more likely to give a gift to the second to last person than any other giver-recipient pair.

Methods

Resources / Links

[1] Barton, D.E., \The Matching Distributions: Poisson Limiting Forms and Derived Methods of Approximation". Journal of the Royal Statistical Society. Series B, 20(1): 73-92, 1958.

[2] Boyd, A.V., and J.N. Ridley, \The Return of Secret Santa". The Mathematical Gazette, 85(503):307-311, 2001.

[3] Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. 4th ed. Boston: Addison Wesley Longman, 1998.

[4] Margolius, Barbara H. "The Dinner-Diner Matching Problem". Mathematics Magazine, 76(2): 107-118, 2003.

[5] McGuire, Kelly M., George Mackiw, and Christopher H. Morrell. "The Secret Santa Problem". The Mathematical Gazette, 83(498):467-472, 1999.

[6] Penrice, Stephen G., \Derangements, Permanents, and Christmas Presents". The American Mathematical Monthly, 98(7): 617-620, 1991.

[7] Schrijver, A. "A Short Proof of Minc's Conjecture." Journal of Combinatorial Theory Series A, 25(1978) 80-83.

[8] Van Lint, J.H. "Notes on Egoritchev's Proof of the Van der Waerden Conjecture." Linear Algebra and Its Applications, 39(1981) 1-8.

[9] Ward, Tony, \Dierence Equations, Determinants and the Secret Santa Problem". The Mathematical Gazette, 89(514):2-6, 2005.

[10] White, Matthew J., \The Secret Santa Problem". Rose-Hulman Institute of Technology Undergraduate Math Journal, 7(1) (Paper 5), 2006.