{"id":1588,"date":"2016-12-03T22:05:10","date_gmt":"2016-12-04T04:05:10","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1588"},"modified":"2016-12-09T12:09:10","modified_gmt":"2016-12-09T18:09:10","slug":"unmasking-the-secret-santas","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/unmasking-the-secret-santas\/","title":{"rendered":"Unmasking the Secret Santas"},"content":{"rendered":"

This Riddler<\/a> puzzle is about the popular Secret Santa gift exchange game. Can we guess who our Secret Santa is?<\/p>\n

\nThe 41 FiveThirtyEight staff members have decided to send gifts to each other as part of a Secret Santa program. Each person is randomly assigned one of the other 40 people on the masthead to give a gift to, and they can\u2019t give to themselves. After the Secret Santa is over, everybody naturally wants to find out who gave them their gift. So, each of them decides to ask up to 20 people who they were a Secret Santa for. If they can\u2019t find the person who gave them the gift within 20 tries, they give up. (Twenty co-workers is a lot of co-workers to talk to, after all.) Each person asks and answers individually \u2014 they don\u2019t tell who anyone else\u2019s Secret Santa is. Also, nobody asks any question other than \u201cWho were you Secret Santa for?\u201d<\/p>\n

If each person asks questions optimally, giving themselves the best chance to unmask their Secret Santa, what is the probability that everyone finds out who their Secret Santa was? And what is this optimal strategy? (Asking randomly won\u2019t work, because only half the people will find their Secret Santa that way on average, and there\u2019s about a 1-in-2 trillion chance that everyone will know.)\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

In order to generalize the problem, let’s assume there are $2n+1$ staff members in total, and each one is allowed to ask $n$ co-workers who they were Secret Santa for. The problem asks about $n=20$, but we’ll examine the general case here.<\/p>\n

A key aspect of this problem is that there is no communication among co-workers. Each staff member independent seeks to discover their Secret Santa and can’t use information gleaned by other co-workers. This assumption actually simplifies the problem greatly; from the point of view of the individual asking questions, there are two classes of co-workers: (1) those we know nothing about and (2) those for whom we already know either their Secret Santa or who they are Secret Santa for. A strategy consists of a sequence of decisions where we must either query somebody from group (1) or somebody from group (2). The lack of collusion among co-workers means that each staff member must use the same strategy. Consequently, there aren’t actually that many different possible strategies! Let’s look at each one in turn.<\/p>\n

Purely random strategy<\/h3>\n

The simplest strategy is to choose $n$ co-workers at random. Each co-worker has a $\\tfrac{1}{2n}$ chance of being your Secret Santa, so the probability that you will find your Secret Santa is $\\tfrac{1}{2}$, regardless of the number of people. Since everybody must use the same strategy, the probability of everybody finding their Secret Santa is:
\n\\[
\nP_\\text{rand} = \\frac{1}{2^{2n+1}}
\n\\]This gets small very quickly as $n$ increases. When $n=20$, we have $P_\\text{rand} = 4.55\\times10^{-13}$ (about 1 in 2 trillion, as mentioned in the problem statement). A very small probability indeed. The random strategy maximizes an individual’s chance of finding their Secret Santa, but it’s a horrible choice if the goal is to maximize the chance that everybody<\/em> finds their Secret Santa.<\/p>\n

Deterministic strategy<\/h3>\n

If not picking randomly, there is only one alternative: to ask the co-worker you gifted! Once they reveal who they gifted, then you ask that person, and so on. You can imagine a graph where each node is a staff member, and you draw an arrow connecting each Secret Santa to their target. Once this is done, each node has exactly one incoming arrow (from their Secret Santa) and one outgoing arrow (to their target). An example of such a graph is shown below.<\/p>\n

\"secret_santa\"<\/p>\n

Notice that the nodes form closed loops. There could be a single loop or multiple smaller loops, as shown above. Before we tackle the general case, let’s see what happens if the group is small.<\/p>\n

Small group<\/b> ($n=1$ or $n=2$): In the case $n=1$, there are three staff members, and they must necessarily be in a single cycle of length 3. In this case, we immediately<\/i> know our Secret Santa; it’s the person we didn’t give a gift to! We don’t even need to ask any questions to know this. In the case $n=2$, there are five staff members. If they form a cycle of length 5, we can follow the Santa until there is a single co-worker left out. Since there can be no cycles of length 4, the co-worker that was left out must be our Secret Santa! Once again, we can deduce our Secret Santa with perfect accuracy even if we don’t directly ask them the question.<\/p>\n

Larger group<\/b> ($n\\ge 2$): If the group is larger, the deductive arguments used previously no longer work because there are too many co-workers left over after we’ve asked all our questions. Each staff member will find their Secret Santa only if all the loops in the are sufficiently small. Since $n$ questions are asked, each loop must have at most $n+1$ members. It turns out counting big loops is easier than counting small ones. So the probability we’re after is:
\n\\begin{align}
\nP_\\text{determ}
\n&= \\frac{\\text{Assignments where each loop has at most }n+1\\text{ nodes}}{\\text{Total number of assignments}}\\\\
\n&= 1-\\frac{\\text{Assignments containing a loop with at least }n+2\\text{ nodes}}{\\text{Total number of assignments}}\\\\
\n&= 1-\\frac{\\sum_{k=n+2}^{2n+1}\\left(\\text{Assignments containing a loop with }k\\text{ nodes}\\right)}{\\text{Total number of assignments}}
\n\\end{align}The total number of assignments is the number of permutations of $\\{1,\\dots,2n+1\\}$ such that there are no fixed points, since nobody is allowed to be their own Secret Santa (wouldn’t be much of a secret). This is precisely the number of derangements<\/a> $D_{2n+1}$, a concept we discussed in the Lonesome King puzzle<\/a>.<\/p>\n

For the numerator, we must count how many ways we can have a loop of length $k$. Since $k \\ge n+2$, there are at most $n-1$ nodes left over. Therefore there can be no more than one loop of length $k$. There is ${2n+1\\choose k}$ ways of picking our loop, $(k-1)!$ ways of ordering the elements in the loop, and $D_{2n+1-k}$ ways of arranging the remaining nodes that weren’t part of the loop. Note that we don’t risk double counting in this manner because there aren’t enough nodes remaining to produce loops of length $k$ or greater. The final result is:
\n\\[
\nP_\\text{determ} = 1-\\frac{\\sum_{k=n+2}^{2n+1}{2n+1 \\choose k}(k-1)!\\,D_{2n+1-k}}{D_{2n+1}}
\n\\]In the case $n=20$, this evaluates to
\n\\begin{align}
\nP_\\text{determ} &= \\tfrac{97939699570365313025758987280981560791683250767}{307662419905587585654556899376849633804439730767}\\\\
\n&\\approx 0.318335
\n\\end{align}so a probability of about 31.8%. Not bad! Here is a plot of how the probability changes as a function of $n$.<\/p>\n

\"secret_santa_plot\"<\/a><\/p>\n

As discussed above, the probability is equal to 1 when $n=1$ or $n=2$, since we can deduce the Secret Santa in those cases even if we ask the wrong co-workers. Curiously, the case $n=3$ (7 people) has a lower probability than the case $n=4$ (9 people). As $n\\to\\infty$, the probability tends to a finite limit. To find this limit, we can use the derangement formula $D_n = \\left[\\frac{n!}{e}\\right]$, where $[x]$ is the nearest integer to $x$. We then have:
\n\\begin{align}
\nP_\\text{determ} &= 1-\\frac{\\sum_{k=n+2}^{2n+1}{2n+1 \\choose k}(k-1)!\\,D_{2n+1-k}}{D_{2n+1}} \\\\
\n&\\approx 1-\\frac{\\sum_{k=n+2}^{2n+1}{2n+1 \\choose k}(k-1)!(2n+1-k)!}{(2n+1)!}\\\\
\n&= 1-\\sum_{k=n+2}^{2n+1}\\frac{1}{k}\\\\
\n&\\approx 1-\\log(2)\\\\
\n&\\approx 0.306853
\n\\end{align}As $n\\to\\infty$, this approximation becomes exact and the limiting probability is $1-\\log(2)$, or about 30.7%. This can be shown rigorously by using upper and lower bounds for the derangements; i.e. $\\frac{k!}{e}-\\tfrac12 \\le D_k \\le \\frac{k!}{e}+\\tfrac12$.<\/p>\n

In the derivation above, we calculated the probability that everybody<\/em> wins when everybody uses the deterministic strategy. If we’re interested in the probability that an individual wins using this strategy, we can observe that an individual wins as long as they don’t belong to the large chain of length $k$ in the summation above. So the probability that an individual wins is given by:
\n\\begin{align}
\nP_{\\text{determ}}^{\\text{individual}} &= 1-\\frac{\\sum_{k=n+2}^{2n+1}{2n+1 \\choose k}(k-1)!\\,D_{2n+1-k}\\tfrac{k}{2n+1}}{D_{2n+1}}
\n\\end{align}Here is what a plot of this looks like as a function of $n$:<\/p>\n

\"\"<\/a><\/p>\n

When $n > 2$, the probability of an individual winning is always less than 50%. When $n=20$, the probability that an individual wins is about 0.487805, or 48.8%. The limit as $n\\to\\infty$ can be computed as before and we obtain $\\tfrac{1}{2}$ this time. So in conclusion, the deterministic strategy is slightly worse than random guessing from the individual’s perspective, but it yields the best possible chance of everybody<\/em> finding their Secret Santa.<\/p>\n

Hybrid strategy<\/h3>\n

The nice thing about the purely random strategy is that no matter what the assignment looks like, there is always some chance<\/em> that everyone will find their Secret Santa. In fact, the chance is the same for every assignment. Unfortunately, that chance is very low. In contrast, the deterministic strategy’s success depends heavily on the assignment. In some cases it works for everybody and in other cases it only works for some.<\/p>\n

In principle, one could design a hybrid<\/em> strategy, e.g. using a deterministic strategy for some number of moves and then playing the remaining moves randomly. The potential of a hybrid strategy is that it gives every assignment a winning chance even if that chance is small. Unfortunately, such strategies are always worse than the purely deterministic one for this problem.<\/p>\n

<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This Riddler puzzle is about the popular Secret Santa gift exchange game. Can we guess who our Secret Santa is? The 41 FiveThirtyEight staff members have decided to send gifts to each other as part of a Secret Santa program. Each person is randomly assigned one of the other 40 people on the masthead to … Continue reading “Unmasking the Secret Santas”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1615,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[9,6,8,2],"class_list":["post-1588","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-binomial","tag-counting","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1588","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=1588"}],"version-history":[{"count":24,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1588\/revisions"}],"predecessor-version":[{"id":1619,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1588\/revisions\/1619"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/1615"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=1588"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=1588"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=1588"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}