[math-fun] Secret Santa problem
Secret Santa [*] is a common holiday procedure where each person in a set of N > 3 is secretly assigned a random different member to whom they will give a gift. Everyone is to receive one gift, and no one is to know anyone else's assignment. That is, a random derangement of the entire set is selected but each participant is only allowed to know their own assignment. Is there a good manual procedure we can use to make these secret random assignments? Drawing names from a hat is natural, but it can result in self-assignments. We could make repeated drawings until none result, but this can be tedious; the portion of derangements is 1/e. We could avoid self-assignments by ordering everyone and somehow drawing random positive "deltas", but this will often violate the one gift requirement. We could have a computer (or other outside party) generate the derangement and then have each person obtain their assignment in secret, but that's clunky and requires an omniscient non-participant. Can you think of a way to generate secret derangements that's about as natural as drawing names from a hat? [*] alternatively, Chaotic Chanukah, Random Ramadan, Kooky Kwanzaa,...
Thu, 08 Jan 2004 11:18:25 -0800 Marc LeBrun <mlb@fxpt.com> Can you think of a way to generate secret derangements that's about as natural as drawing names from a hat? Drawing names from two hats? Split the names randomly, partitioning the group into reds and greens. The red people draw names from the hat with green names, and the green people draw hats from the hat with red names. I guess you know that your gift came from a particular half of the group, but that doesn't seem so terrible.
=Michael B Greenwald Drawing names from two hats?
Interesting approach! Of course one glitch is that there must be as many reds as greens, so this only works for even N (and, unfortunately, my motivating application has N=5...<;-).
...that doesn't seem so terrible.
Agreed, in practice. But still, from a theoretical, esthetic, point of view, it's unfortunate that it doesn't generate all derangements with equal probability (eg all the cycles are even). It seems strange that random secret derangements would be so much harder to generate than random secret permutations. Perhaps this multi-hat idea can be modified to work uniformly somehow? Or, perhaps there's some kind of cryptographic protocol, using sealed envelopes or the like? (avoiding the omniscient computer smells like eliminating key escrow...)
Divide the problem into two stages. First, secretly assign numbers to people by drawing sealed numbers from a hat. Second, generate a random derangement; this need not be done secretly. Here is one way to generate derangements with equal probability. Place numbers 2 to n in a hat. Draw a number; it becomes p(1). Put 1 into the hat and withdraw 2 if it is not p(1). Draw a number; it becomes p(2). Replace 2 if it is not p(1), and withdraw 3 if it is not p(1) or p(2). Draw a number; it becomes p(3). And so on. Gene __________________________________ Do you Yahoo!? Yahoo! Hotjobs: Enter the "Signing Bonus" Sweepstakes http://hotjobs.sweepstakes.yahoo.com/signingbonus
Marc LeBrun wrote:
That is, a random derangement of the entire set is selected but each participant is only allowed to know their own assignment.
My impression of Secret Santa is that you're supposed to have a random n-cycle, not just a random derangement. With a random derangement, for example, you might end up with a bunch of pairs of people each unknowingly just exchanging gifts with each other, which seems to me undesirable. Making a random n-cycle out of a random permutation is easy, of course: each person gives gifts to the person who comes after them in the permutation. This is like taking a permutation written in 1-line notation, and putting parens around it to make it into an n-cycle written in cycle structure notation. Each n-cycle can appear in n different ways, of course. (So, obviously, 1/n of all permutations of n things are n-cycles.) Of course, the interesting question is generating things secretly, modeled on pulling names out of a hat. I stayed my hand moments before sending out email based on the same idea Gene Salamin proposed:
Divide the problem into two stages. First, secretly assign numbers to people by drawing sealed numbers from a hat. Second, generate a random derangement; this need not be done secretly.
But then you only know the secret number of the person you're giving a gift to, not the name! It's the decoding (secretly) that's tricky. Here's the best idea I've come up with. It's pretty baroque, and I'm sure there's something better. --------- 1) Each person gets a secret code name, just as Gene said. Practically, I'd do this by closing your eyes and pointing to a random word on a random page of a dictionary. 2) Each person: a. writes their real name on a piece of paper, b. folds that paper up so the name can't be seen, c. puts it in an envelope, d. writes their secret code name on the outside of the envelope, and e. puts that envelope into a second, larger envelope, in such a way that it is possible to open both flaps to get to the inside piede of paper. (!) 3) These overstuffed envelopes get put in a hat and are drawn out randomly, and put in a stack in that random order. 4) Make this random permutation into a random n-cycle: open both flaps of each doubled envelope, take out the folded paper inside it, and put it into the previous doubled envelope. (The folded paper from the first envelope goes in the last one.) 5) Put all the envelopes back into the hat, mix them up again, and then take them all out and remove the inner paper-in-envelopes from their outer covers. 6) Each person can now safely take the (inner) envelope with their own secret dictionary word written on it, and read the name on the folded paper inside it to see their giftee. --------- The second, outer set of envelopes is a little bit of overkill. It would suffice to draw the paper-in-one-envelopes out of the hat face down, so that no one got to see the secret code names written on the underside of them. (It's easier to open envelope flaps when they are face down anyway.) It's not immediately obvious that we need to preserve secrecy during step (4); nothing would be given away then and there if the secret code names were visible. But secrecy would then be compromised in step (6), where people reveal their secret code names. Improvements welcomed, since this looks pretty bad to me. (But for Marc's motivating n=5, it will certainly work!) --Michael Kleber kleber@brandeis.edu
For secret santa as a n-cycle random permutation. Generator stage: 1 N folks stands in a circle each has an envelope., they each draw X, a random unique alias from a hat. They make up two cards. One says I give to X, the other says I am X. They put the I am X card in there own envelope and the I give to X card in the envelope of the person on their right. Finding secret stage. 2. The envelopes are put in a hat and each person draws an envelope. They make the I am X alias public and keep the I give to alias. Regards Otto otto@olympus.net On Thursday 08 January 2004 12:54, Michael Kleber wrote:
Marc LeBrun wrote:
That is, a random derangement of the entire set is selected but each participant is only allowed to know their own assignment.
My impression of Secret Santa is that you're supposed to have a random n-cycle, not just a random derangement. With a random derangement, for example, you might end up with a bunch of pairs of people each unknowingly just exchanging gifts with each other, which seems to me undesirable.
Making a random n-cycle out of a random permutation is easy, of course: each person gives gifts to the person who comes after them in the permutation. This is like taking a permutation written in 1-line notation, and putting parens around it to make it into an n-cycle written in cycle structure notation. Each n-cycle can appear in n different ways, of course. (So, obviously, 1/n of all permutations of n things are n-cycles.)
Of course, the interesting question is generating things secretly, modeled on pulling names out of a hat. I stayed my hand moments before sending out email based on the
same idea Gene Salamin proposed:
Divide the problem into two stages. First, secretly assign numbers to people by drawing sealed numbers from a hat. Second, generate a random derangement; this need not be done secretly.
But then you only know the secret number of the person you're giving a gift to, not the name! It's the decoding (secretly) that's tricky.
Here's the best idea I've come up with. It's pretty baroque, and I'm sure there's something better.
--------- 1) Each person gets a secret code name, just as Gene said. Practically, I'd do this by closing your eyes and pointing to a random word on a random page of a dictionary.
2) Each person: a. writes their real name on a piece of paper, b. folds that paper up so the name can't be seen, c. puts it in an envelope, d. writes their secret code name on the outside of the envelope, and e. puts that envelope into a second, larger envelope, in such a way that it is possible to open both flaps to get to the inside piede of paper. (!)
3) These overstuffed envelopes get put in a hat and are drawn out randomly, and put in a stack in that random order.
4) Make this random permutation into a random n-cycle: open both flaps of each doubled envelope, take out the folded paper inside it, and put it into the previous doubled envelope. (The folded paper from the first envelope goes in the last one.)
5) Put all the envelopes back into the hat, mix them up again, and then take them all out and remove the inner paper-in-envelopes from their outer covers.
6) Each person can now safely take the (inner) envelope with their own secret dictionary word written on it, and read the name on the folded paper inside it to see their giftee. ---------
The second, outer set of envelopes is a little bit of overkill. It would suffice to draw the paper-in-one-envelopes out of the hat face down, so that no one got to see the secret code names written on the underside of them. (It's easier to open envelope flaps when they are face down anyway.)
It's not immediately obvious that we need to preserve secrecy during step (4); nothing would be given away then and there if the secret code names were visible. But secrecy would then be compromised in step (6), where people reveal their secret code names.
Improvements welcomed, since this looks pretty bad to me. (But for Marc's motivating n=5, it will certainly work!)
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
=Michael Kleber
My impression of Secret Santa is that you're supposed to have a random n-cycle, not just a random derangement. With a random derangement, for example, you might end up with a bunch of pairs of people each unknowingly just exchanging gifts with each other, which seems to me undesirable.
OK, tastes differ. I don't recall any restriction to n-cycles. I actually enjoy the craziness of not knowing what size cycle you will wind up in. (Surely ALL-pair derangements are relatively rare--a vein of homework exercises throbs here!<;-).
Making a random n-cycle out of a random permutation is easy, of course: each person gives gifts to the person who comes after them in the permutation... Improvements welcomed, since this looks pretty bad to me.
Your method will work fine for n-cycles. In fact, more simply, since we basically hide the random permutation by leaving the envelopes face down during the shift step, we might as well just write our names in the clear on the fronts as well. Then after the shift step we just throw them all in a mailbag (never peeking at the fronts) and then open our own self-addressed envelopes to see who shifted in. Although this is mechanically a smidgen trickier than just drawing names, and might be cleverly improved somehow, I think it's conceptually comparable since the ephemeral global information still is just a single random permutation. Now what about those pesky derangements?
Marc LeBrun wrote:
OK, tastes differ. I don't recall any restriction to n-cycles. I actually enjoy the craziness of not knowing what size cycle you will wind up in.
Since yesterday, I've taken an unscientific poll. My desire for n-cycles is clearly in the minority, so I'll abandon it. Many people agreed with you completely, seeing the small cycle possibility as a feature, not a bug. Some had a third option entirely: ideally, there should be no 2-cycles, but anything else is fine.
Your method will work fine for n-cycles. In fact, more simply, since we basically hide the random permutation by leaving the envelopes face down during the shift step, we might as well just write our names in the clear on the fronts as well.
Oof, right, I knew I had an extra layer of complexity in there -- a vestige of an earlier scheme I'd been thinking of. Thank you.
Although this is mechanically a smidgen trickier than just drawing names, and might be cleverly improved somehow, I think it's conceptually comparable since the ephemeral global information still is just a single random permutation.
Good, glad it passes the test of having the right smell for a solution.
Now what about those pesky derangements?
Okay, this shouldn't be too bad. There is an easy *almost* correct answer. One so-so way to generate a random derangement a_1, a_2,..., a_n is as follows: --------- 1) Start with all a_i = i 2) For i from 1 to n-1, swap the value of a_i with one of a_{i+1},...,a_n, chosen at random --------- This can easily be modified into the desired type of blind generation scheme: --------- 1) Each person writes her own name on a piece of paper, folds it, puts it in an envelope, and writes her own name on the outside of the envelope in such a way that if you fold the flap over backwards, it covers up her own name. Put all these anonymized envelopes into the hat. 2) Pick a random pair of envelopes out of the hat, swap the pieces of paper inside them, then put *one* of them back into the hat. The other one is finished: unfold its flap to reveal whose envelope it is and give it to them; the name inside is the person they give gifts to. Keep this up right through swapping the contents of the last two envelopes. --------- It's easy to see that no one gives themselves gifts: the first time my envelope gets drawn from the hat, my name is removed from it, and then either my envelope or my name is immediately out of circulation. This is so-so because it doesn't generate derangements uniformly at random. Since we picked envelopes in a random order, no particular person is treaded asymmetrically, of course! But some cycle structures are more or less likely than they "ought" to be. I haven't tried to analyze it in detail, but I suspect you get too few 2-cycles, for example. Probably the person who is handed their envelope in the first pass through step 2 can make some guesses as to the length of the cycle they're in. Anyone want to really do this calculation? It might be interesting... I'll have to think more about whether there's an easy variant that will give uniform distribution to the derangements generated --- without giving out more information. (I may have one that will give all derangements but where the people watching will know the number of disjoint cycles, for example.) --Michael Kleber kleber@brandeis.edu
At 11:31 AM 1/9/04, Michael Kleber wrote:
I'll have to think more about whether there's an easy variant that will give uniform distribution to the derangements generated --- without giving out more information.
An observation: A large class of "hat-drawing-like" algorithms-- including most of those proposed in the past day--cannot generate derangements uniformly. If the procedure involves a finite sequence of uniform choices, each from a set of N or fewer objects, the probability of any particular sequence of choices will be 1/K, where K contains no prime factors larger than N. A particular derangement might be generated in many ways, so its probability would be the sum of different 1/K terms, but the total probability still will have no prime factor larger than N in the denominator. Unfortunately, the number of derangements for N = 5 is 44 = 2*2*11, and for N = 6, it's 265 = 5*53; so a prime factor larger than N is needed for the selection to be uniform. There are three obvious ways around this limitation, although it isn't clear how to apply some of them to an algorithm that could be used at a restaurant table. First, allow an unbounded sequence of choices, as in the "select a permutation; if it isn't a derangement, start over" procedure. Second, allow non-uniform choices. Third, allow uniform choices from larger sets. -- Fred W. Helenius <fredh@ix.netcom.com>
Uniform Distributions Of Santa. Please excuse my ignorance about this area of combinatorics; I am curious about what is meant by a "uniform distribution to the derangements". Here is where I am confused. I have suggested here that a derangement is a directed graph of one or more cycles of two or more vertexes. Every person is assigned a vertex of the graph and we walk the cycle generating Santa's and recipients. To get a uniform distribution we then randomly choose a graph of a derangement and then randomly assign each person a vertex. For five people there are only two possible graphs, a graph of a single five cycle, and a graph consisting of a two cycle and a three cycle. Clearly if we choose one of the two graphs with any probability distribution, 1/2 - 1/2 or 1/3 - 2/3, and then assign each person to a vertex, the distribution will be even in the sense that each person has an equal chance for each vertex. The debate over how to adjust the probability of choosing one graph or another seems to me to be somewhat arbitrary. There was a suggestion her at one point that we allow only the connected cycle of all vertexes. If we generate every possible graph on N vertexes, and then choose every graph that consists only of cycles from that group and treat each one as having equal probability we get one answer. If we select only from the set of non-isomorphic graphs we get a different answer. If we count the possible permutations of assignments in each graph, so that a graph of four vertexes is four times as likely to be chosen as a graph of three vertexes, we get yet another answer. If we weight the probability by the number of vertexes in a cycle we get yet another answer. Any of these methods generates an even distribution in the sense that each person is equally likely to be chosen for any edge. The envelope flap method, IMHO the best described so far in terms of practicality, does meet the above test for uniform distribution, although it doesn't hide the conditional probabilities from the players, since one can calculate the probability that each player after a given point will be a neighbor with increasing accuracy as the game is played. That can be fixed by making the names aliases and then drawing them from a hat, but it then removes the nice feature of it being a single draw for each name and removes the feature of minimal preparation. In the real world, the envelope method would work quite well, it is a practical answer to a practical question with a mathematical flavor. I would be interested though in knowing what the probability of any particular distinguishable graph of cycles is, and how the probability of being in a particular x-cycle changes as a function of the position in the sequence at which a name is drawn. Regards Otto otto@olympus.net On Friday 09 January 2004 10:47, Fred W. Helenius wrote:
At 11:31 AM 1/9/04, Michael Kleber wrote:
I'll have to think more about whether there's an easy variant that will give uniform distribution to the derangements generated --- without giving out more information.
An observation: A large class of "hat-drawing-like" algorithms-- including most of those proposed in the past day--cannot generate derangements uniformly.
If the procedure involves a finite sequence of uniform choices, each from a set of N or fewer objects, the probability of any particular sequence of choices will be 1/K, where K contains no prime factors larger than N. A particular derangement might be generated in many ways, so its probability would be the sum of different 1/K terms, but the total probability still will have no prime factor larger than N in the denominator.
Unfortunately, the number of derangements for N = 5 is 44 = 2*2*11, and for N = 6, it's 265 = 5*53; so a prime factor larger than N is needed for the selection to be uniform.
There are three obvious ways around this limitation, although it isn't clear how to apply some of them to an algorithm that could be used at a restaurant table. First, allow an unbounded sequence of choices, as in the "select a permutation; if it isn't a derangement, start over" procedure. Second, allow non-uniform choices. Third, allow uniform choices from larger sets.
Aw, nuts... Funster-mostly-lurker Thomas Colthurst and I spent a little time this afternoon thinking about how good my secret santa algorithm is. (Recall, it's iterating "remove two envelopes from the hat, swap the names inside, then put one of them back in the hat.") After some amount of mental fumbling, we realized the sad truth: turns out that it generates only n-cycles. :-( Once you realize it's true, the proof's not hard, so I'll leave it as an exercise. Sigh... Anyway, in light of Fred Helenius's observation (that choosing among derangements uniformly is essentially hard for prime factorization reasons), it seems that the next obvious thing to hope for is that, even once you know who you're giving gifts to, the person giving gifts to you should be equally likely to be anyone in the group. It's pretty clear that, if you do a decent job randomizing, there should only be two probabilities to think about: that your gift-giver is (a) the person you're giving gifts to, or (b) someone else. And of course if (a) happens 1/(n-1) of the time, you meet this criterion. Anyway, my algorithm does (a) with probability zero, so unless you're of the camp that says n-cycles are a good thing, a better routine is required. From this point of view, by the way, the "two hats" algorithm (for n even) is also flawed: the person you're giving gifts to was definitely in the opposite hat from you, making them (epsilon more than) twice as likely as anyone else to be your santa. --Michael Kleber kleber@brandeis.edu
I think Michael Kleber's algorithm can be fixed albeit with a slight increase in complexity. Envelopes are prepared as before. There is a red hart and a blue hat as well as the initial hat from which we draw. We draw two envelopes as before and swap the contents, this time we randomly place one envelope in the red hat and one in the blue hat. If at the last draw, there is only one envelope. we draw a second envelope from the blue hat to match it, swap the contents and place one envelope in the blue and one envelope in the red hat. The blue hat is then dumped out. All the cards are removed from their envelopes, shuffled and put back in any order. The red and blue hats are combined and the envelopes passed out. I believe this procedure can generate any poosible secret santa configuration. For the case of an even number, we can see that the set of names has been partitioned into two equal size sets. The red hat contains only one set as the lables on the envelopes, and the blue hat contains the same set as the contents of the envelopes. Consequently we can safely shuffle the contents in either hat and the criteria that every person is contained in one envelope and has their name on one envelope is met. For the case of an odd number, we must shuffle only the blue hat because it is possible that shuffling the red hat could cause a person to be their own secret santa. In addition, of course, it guarantees an odd cycle in the geometry of the result. There are probably ways to simplify this algorithm and make it more natural in terms of practicality. Regards Otto otto@olympus.net On Sunday 11 January 2004 17:27, Michael Kleber wrote:
Aw, nuts...
Funster-mostly-lurker Thomas Colthurst and I spent a little time this afternoon thinking about how good my secret santa algorithm is. (Recall, it's iterating "remove two envelopes from the hat, swap the names inside, then put one of them back in the hat.") After some amount of mental fumbling, we realized the sad truth: turns out that it generates only n-cycles. :-( Once you realize it's true, the proof's not hard, so I'll leave it as an exercise.
Sigh...
Anyway, in light of Fred Helenius's observation (that choosing among derangements uniformly is essentially hard for prime factorization reasons), it seems that the next obvious thing to hope for is that, even once you know who you're giving gifts to, the person giving gifts to you should be equally likely to be anyone in the group. It's pretty clear that, if you do a decent job randomizing, there should only be two probabilities to think about: that your gift-giver is (a) the person you're giving gifts to, or (b) someone else. And of course if (a) happens 1/(n-1) of the time, you meet this criterion.
Anyway, my algorithm does (a) with probability zero, so unless you're of the camp that says n-cycles are a good thing, a better routine is required.
From this point of view, by the way, the "two hats" algorithm (for n even) is also flawed: the person you're giving gifts to was definitely in the opposite hat from you, making them (epsilon more than) twice as likely as anyone else to be your santa.
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Actually the fix posted below doesn't work. It will produce only one odd cycle, so that, for instance, in a six person problem it will never generate two three cycles. Oh well, this must be a good problem, it is "fighting back". Regards Otto On Monday 12 January 2004 13:32, Otto Smith wrote:
I think Michael Kleber's algorithm can be fixed albeit with a slight increase in complexity.
Envelopes are prepared as before. There is a red hart and a blue hat as well as the initial hat from which we draw. We draw two envelopes as before and swap the contents, this time we randomly place one envelope in the red hat and one in the blue hat.
If at the last draw, there is only one envelope. we draw a second envelope from the blue hat to match it, swap the contents and place one envelope in the blue and one envelope in the red hat.
The blue hat is then dumped out. All the cards are removed from their envelopes, shuffled and put back in any order. The red and blue hats are combined and the envelopes passed out. I believe this procedure can generate any poosible secret santa configuration.
For the case of an even number, we can see that the set of names has been partitioned into two equal size sets.
The red hat contains only one set as the lables on the envelopes, and the blue hat contains the same set as the contents of the envelopes. Consequently we can safely shuffle the contents in either hat and the criteria that every person is contained in one envelope and has their name on one envelope is met. For the case of an odd number, we must shuffle only the blue hat because it is possible that shuffling the red hat could cause a person to be their own secret santa. In addition, of course, it guarantees an odd cycle in the geometry of the result.
There are probably ways to simplify this algorithm and make it more natural in terms of practicality.
Regards Otto otto@olympus.net
On Sunday 11 January 2004 17:27, Michael Kleber wrote:
Aw, nuts...
Funster-mostly-lurker Thomas Colthurst and I spent a little time this afternoon thinking about how good my secret santa algorithm is. (Recall, it's iterating "remove two envelopes from the hat, swap the names inside, then put one of them back in the hat.") After some amount of mental fumbling, we realized the sad truth: turns out that it generates only n-cycles. :-( Once you realize it's true, the proof's not hard, so I'll leave it as an exercise.
Sigh...
Anyway, in light of Fred Helenius's observation (that choosing among derangements uniformly is essentially hard for prime factorization reasons), it seems that the next obvious thing to hope for is that, even once you know who you're giving gifts to, the person giving gifts to you should be equally likely to be anyone in the group. It's pretty clear that, if you do a decent job randomizing, there should only be two probabilities to think about: that your gift-giver is (a) the person you're giving gifts to, or (b) someone else. And of course if (a) happens 1/(n-1) of the time, you meet this criterion.
Anyway, my algorithm does (a) with probability zero, so unless you're of the camp that says n-cycles are a good thing, a better routine is required.
From this point of view, by the way, the "two hats" algorithm (for n even) is also flawed: the person you're giving gifts to was definitely in the opposite hat from you, making them (epsilon more than) twice as likely as anyone else to be your santa.
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
=Eugene Salamin Divide the problem into two stages. First, secretly assign numbers to people by drawing sealed numbers from a hat. Second, generate a random derangement; this need not be done secretly.
This sounds promising, but on further scrutiny, I just can't see how to make it work. Exactly who are which assigned numbers secret from? How do you (and only you) just learn which is your assigned recipient? If you know your own number you can also inadmissibly see who your own Secret Santa is. On the other hand if you don't know your own number how do you select the right recipient assignment from the derangement? Of course an omniscient computer (or waiter) wouldn't have these problems, but we're trying to avoid that device.
Here is one way to generate derangements with equal probability...
Apart from the above issue, as Dan Hoey points out, this particular scheme might paint itself into a corner. But surely Knuth or somebody has a nice deranging algorithm. Anyway, if the derangement's public knowledge then in principle you could just draw one randomly from a deck of prepared cards or something, it doesn't matter. Surely there's a way to do this?!
participants (6)
-
Eugene Salamin -
Fred W. Helenius -
Marc LeBrun -
Michael B Greenwald -
Michael Kleber -
Otto Smith