Timeline for Secret Santa (expected no of cycles in a random permutation)
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 23, 2010 at 0:00 | comment | added | Peter Shor | @fedja: To simulate a permutation of $n$ without cycles of length less than 10, you might pick a random permutation of size $n+4$, and hope that when you threw out cycles of length $\leq 10$, you would end up throwing away exactly 4 elements. By optimizing on 4, this might not be too inefficient. Better yet, you could pick correlated random permutations of size $n$, $n+1$, $n+2$, $n+3$, $\ldots$, $n+10$, and hope that one of these works. | |
| Dec 22, 2010 at 20:06 | comment | added | fedja | Actually, on average, the rejection will occur around half-way through the simulation, so the "efficiency" of such method is $2/(e+1)$ rather than $1/e$, which is not too bad. In the game, it would mean restarting every time anyone gets his name (no repeated draws allowed). On the other hand, I would love to learn how to simulate a permutation without cycles of length less than 10, say, efficiently. | |
| Dec 22, 2010 at 10:38 | comment | added | Douglas Zare | The numbering I used was the order people drew from the hat. There are other interpretations. Perhaps all names are distributed at once, and then the people who drew their own names draw again, and this is repeated until a derangement is created or one person is stuck, which means the process restarts. This also would not produce a uniform distribution on derangements. What struck me was that it doesn't seem like it should be that simple to get a uniformly chosen derangement other than choosing a random permutation and rejecting it about $1-1/e$ of the time, and this might taint simulations. | |
| Dec 22, 2010 at 3:48 | comment | added | fedja | The game description is ambiguous. There is no reason to assume that the rule is that there is some fixed order in which the players make their choices (and, certainly, if they draw straws to determine who's choosing next, we get a more symmetric distribution, though I'm not sure it'll be uniform either. That's why everybody answered the well-posed question in the end of the post. | |
| Dec 22, 2010 at 0:03 | comment | added | Peter Shor | Good point. I would have guessed the Secret Santa method chose derangements uniformly. | |
| Dec 21, 2010 at 22:47 | history | answered | Douglas Zare | CC BY-SA 2.5 |