## Secret Santa Revisited

Last week’s post presented two similar problems, the first being a simpler “standard” probability puzzle, and the second being rather more challenging.  Since the first problem was basically just a lead-in to this discussion, I won’t spend time on it here; there are plenty of good descriptions of solutions elsewhere (see here, for example).

The harder second problem asks essentially the same question as discussed in the Deranged Secret Santa post from last year: suppose that n participants in a Secret Santa gift exchange each put a slip of paper with their name on it into a single hat.  To determine gift-giving assignments, each participant in turn draws a slip from the hat, replacing it with another if he draws his own name.  What is the probability that this procedure “fails,” with the last person to draw finding his own name on the last slip in the hat?

I did some simulation and doodling on this problem last year, with limited success.  After revisiting the problem this year, there are a few more concrete and interesting results to report.

First, as usual, the problem has already been solved; the solution by Brian Parsonnet appears as sequence A136300 in the Online Encyclopedia of Integer Sequences.  (The sequence is parameterized by the number n of participants, where each integer value of the sequence is the numerator of the corresponding probability with denominator $(n-1)!^2$.)  However, the given recurrence relation is rather complex, and appears to require $O(2^n)$ time and space to compute.

It turns out that we can solve the problem more simply and efficiently (in quadratic time) by transforming the problem slightly.  Note that the statement of the problem does not explicitly specify any particular order in which participants draw slips from the hat.  That is, it does not really matter who is the last person to draw; all that we want to know is the probability that the last person– whoever that may be– ends up drawing their own name.

At each turn, then, we can randomize the selection of the next person to draw, without affecting the desired probability.  (In the context of last week’s airplane boarding problem, the passengers do not stand in a line; they jostle in a group near the jetway entrance, and each next person to board is selected randomly.)  This helps a lot: given $n$ total participants, let $m$ be the number still waiting to draw, and let $k \leq m$ be the number waiting to draw whose names have already been drawn.  Then the probability that the last person to draw is left with his own name is $p(n,0)$, where $p(m,k)$ is given by the following recurrence (with apologies for WordPress’s limited LaTeX multi-line formatting):

$p(m,k) = \frac{k}{m}\left[\frac{k}{m} p(m-1,k-1) + (1 - \frac{k}{m}) p(m-1,k)\right]$

$+ (1 - \frac{k}{m})\left[\frac{k}{m-1} p(m-1,k) + (1 - \frac{k}{m-1}) p(m-1,k+1)\right]$

$p(1,k) = 1 - k$

As the following plot shows, the probability of failure varies approximately as $1/n$; the probability for $n=100$ in the original problem is approximately 0.0095018.

Probabiilty that the last person draws his own name vs. group size.

Finally, this slight transformation of the problem yields an interesting additional bonus: recall the “warning” given in last year’s post, suggesting that you probably do not want to use this procedure at all for your Secret Santa gift exchange.  The problem is that all possible permutations (specifically, all possible derangements) mapping gifters to recipients are not equally likely.  Even if you handle the small failure possibility of the last person drawing his own name by starting the whole procedure over, some participants are still more likely to draw certain names than others.  (As mentioned last year, the most extreme deviation is near the end of the line, with the last person to draw being nearly twice as likely to draw the next-to-last person as to draw the first person in line.  See the Mathematica source code below to calculate these probabilities.)

We can relax that warning a bit, based on the following observation: as in the puzzle solution above, if we modify the procedure slightly by first randomizing the order in which participants draw names… then the resulting random assignment does at least have the nice property that each person is equally likely to draw any other person’s name!

I verified this numerically for $n \leq 8$ using the code below, but I think this follows generally from a simple symmetry argument.  However, this is a weaker statement than the stronger claim that all derangements are equally likely, which still does not hold ($n=4$ is a minimal counterexample).

board[seats_, assigned_, prob_] :=
Module[
{passenger, s, p},
If[Length[seats] === 1,
If[seats === {Length[assigned] + 1}, Return[]];
MapIndexed[
(overall[[#2[[1]], #1]] += prob) &,
Append[assigned, First[seats]]
],
passenger = Length[assigned] + 1;
s = DeleteCases[seats, passenger];
p = 1/Length[s];
Scan[
board[DeleteCases[seats, #], Append[assigned, #], prob*p] &,
s
]
]
]

n = 10;
overall = Table[0, {n}, {n}];
board[Range[n], {}, 1];

This entry was posted in Uncategorized. Bookmark the permalink.

### 3 Responses to Secret Santa Revisited

1. Pingback: Secret Santa puzzle | Possibly Wrong