11
$\begingroup$

In a Secret Santa game, each of $n$ players puts their name into a hat and then each player picks a name from the hat, who they buy a Christmas present for. Obviously, if someone picks their own name then they put it back and draw again (if they're the only person remaining in the hat then everyone heaves an exasperated sigh, and you start again).

My question: how many loops of present-giving do you expect to see? (e.g. A -> B -> C -> A)

More mathematically: what is the expected number of cycles in a random $n$-permutation which contains no fixed points?

The twelve-fold way doesn't appear to answer this question. Some brief Monte Carlo suggests that the limiting answer as $n\to\infty$ is $c\log n$ for some constant $c\approx 0.95$ (see attached graph, where circles are Monte Carlo approximation, straight line is $\log n$) but I'd like to see an analytical argument for this.

alt text http://www.freeimagehosting.net/uploads/330281fbea.png

$\endgroup$
2
  • $\begingroup$ Naturally, in Secret-Santa there nobody is giving gifts to themselves... How are you generate permutations without fixed points? One way is to rejection-sample a random permutation and discard if it has fixed pts... $\endgroup$ Dec 21, 2010 at 11:01
  • $\begingroup$ Thanks for your comment John. Rejection sampling was exactly what I was doing. Thankfully 1/e of randomly generated permuations are derangements, so it doesn't take too long. $\endgroup$ Dec 22, 2010 at 9:36

6 Answers 6

14
$\begingroup$

One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permutations, subtracting the multiset of permutations with a fixed point at $i$ (for all $i$), adding the multiset of permuations with a fixed point at $i$ and $j$ (for all $i$ and $j$), etc. Let $D_n$ be the set of permutations with no fixed points (derangements). This gives

$\{D_n\} = \{S_n\} -n\{S_{n-1}\} +\frac{1}{2!}n(n-1) \{S_{n-2}\} -\frac{1}{3!}n(n-1)(n-2)\{S_{n-3}\} \ldots$

where $\{S_k\}$ is the set of permutations of length $k$. Now, we can find the number of $k$-cycles on the right-hand side. The expected number of $k$-cycles in $\{S_{n-i}\}$ is $1/k$ if $k\leq n-i$ and $0$ if $k > n-i$. If we make this replacement, and divide by the number of derangements, we find that the expected number of $k$-cycles in a derangement is

$\frac{1}{k} \cdot \frac{1 -1 +1/2! -1/3! + \ldots \pm 1/(n-k)!}{1 - 1 + 1/2! - 1/3! +\ldots \pm 1/n!}$.

One can check this formula by noting that it gives the expected number of $n-1$ cycles as 0 and the expected number of $n$-cycles as approximately $e/n$ (this is correct, since the probability that a permutation is a derangement is approximately $1/e$).

For large $n$ and $k\leq n-\log{n}$, this is almost exactly $\frac{1}{k}$. For $k > n-\log{n}$, the expected contribution of the number of cycles from long cycles is quite small, so the expected number of cycles is roughly $\sum_{k=2}^n \frac{1}{k}$.

$\endgroup$
0
7
$\begingroup$

This isn't an answer to your question, but without any restrictions, the expected number of $r$-cycles in a permutation of at least $r$ elements is $\frac{1}{r}$, so the expected number of cycles in a permutation in $S_n$ is $1 + \frac{1}{2} + ... + \frac{1}{n} = H_n \sim \log n$. So this provides a heuristic upper bound on the number you're actually looking for.

Edit: Okay, so here's one way to get an answer. It's not elegant, but it's fairly automatic. Our starting point is the exponential formula

$$\sum_{m \ge 0} Z(S_m) t^m = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right)$$

where $Z_{S_m}$ is the cycle index polynomial of $S_n$. We want to ignore fixed points, so we set $z_1 = 0$. We want to count the remaining types of cycles together, so we set $z_2 = z_3 = ... = z$. Then

$$\sum_{m \ge 0} \frac{1}{m!} \sum_{\sigma} z^{c(\sigma)} t^m = \exp \left( \frac{zt^2}{2} + \frac{zt^3}{3} + ... \right) = e^{-zt} \frac{1}{(1 - t)^z}$$

where the inner sum is over permutations in $S_m$ with no fixed points and $c(\sigma)$ denotes the number of cycles. To compute the expected number of cycles we now need to differentiate with respect to $z$ and set it equal to $1$. Using logarithmic differentiation gives

$$\sum_{m \ge 0} \frac{1}{m!} (\sum_{\sigma} c(\sigma)) t^m = e^{-t} \frac{1}{1 - t} \left( \log \frac{1}{1-t} - t \right).$$

Now the number we are actually interested in is $\frac{1}{!m} \sum_{\sigma} c(\sigma)$ but this essentially differs only by a multiple of $e$ so it suffices to analyze the asymptotics of the above sequence. Note that

$$\frac{1}{1-t} \left( \log \frac{1}{1-t} - t \right) = \sum_{n \ge 0} (H_n - 1) t^n$$

so it suffices to analyze the effect of the factor $e^{-t}$. This gives the sequence

$$c_n = \sum_{k=0}^{n} (-1)^k \frac{H_{n-k} - 1}{k!}$$

and by taking, say, the $\frac{n}{2}$ largest terms it's not hard to believe that $c_n \sim \frac{H_n}{e}$. So my money is on the constant you're looking for being equal to $1$.

$\endgroup$
3
  • $\begingroup$ Thanks Qiaochu. I suspect that with some careful accounting and a few judicious approximations, you can probably turn that argument into one which accounts for the conditioning on the number of 1-cycles, and derive the constant multiplicative factor. I'll have a crack at that if I get some spare time later today. $\endgroup$ Dec 21, 2010 at 10:46
  • $\begingroup$ @Chris: I've updated with a generating function argument, but one can also reason heuristically: I believe the numbers X_r of r-cycles are asymptotically independent (and possibly there is a theorem in the literature to this effect) and so conditioning on the value of X_1 shouldn't affect the asymptotic behavior of the other X_i. The generating function computation supports this. $\endgroup$ Dec 21, 2010 at 11:06
  • $\begingroup$ @Qiaochu: I haven't verified it really carefully, but it looks like our answers agree, which is a good check on both of them. $\endgroup$
    – Peter Shor
    Dec 22, 2010 at 13:10
6
$\begingroup$

In an unrestricted permutation, the number of cycles is distributes as $\sum_{i=1}^n X_i$, where $X_i$ is Bernoulli with mean $1/i$, all independent. It follows that the number of cycles is concentrated near $\log n$. The probability that a uniform permutation has no fixed points is $\sim 1/e$, so conditioning on this does not change the number of cycles.

$\endgroup$
5
$\begingroup$

I want to elaborate on and correct a comment that I made.

The two questions are not the same. The Secret-Santa-game method used to choose a derangement is not uniform on derangements. For $n=4$, you get the following:

$P[\text{Restart}] = 5/36$

$P[(12)(34)] = 1/9$

$P[(13)(24)] =1/12$

$P[(14)(23)]=1/12$

$P[(1234)]=1/18$

$P[(1243)]=1/9$

$P[(1324)]=1/12$

$P[(1342)]=1/12$

$P[(1423)]=1/12$

$P[(1432)]=1/6$

If you simulate this, the chance of two transpositions is $36/31(1/9+1/12+1/12)= 10/31$ rather than $1/3$, and the average number of cycles should be about $41/31$ instead of $4/3$. I suspect that this makes no difference to the asymptotics, and that no one will care about the nonuniform method's exact answer.

$\endgroup$
5
  • $\begingroup$ Good point. I would have guessed the Secret Santa method chose derangements uniformly. $\endgroup$
    – Peter Shor
    Dec 22, 2010 at 0:03
  • $\begingroup$ 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. $\endgroup$
    – fedja
    Dec 22, 2010 at 3:48
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 22, 2010 at 10:38
  • $\begingroup$ 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. $\endgroup$
    – fedja
    Dec 22, 2010 at 20:06
  • $\begingroup$ @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. $\endgroup$
    – Peter Shor
    Dec 23, 2010 at 0:00
3
$\begingroup$

Let's do a back of envelope count. Assume that the number in question is $F(n)$. We all agree that $F(n)$ grows only as $\log n$. I'll assume that, whatever it is, it is nice and regular, meaning that $F(n)-F(n-1)=o(1)$ (actually, one would expect $O(1/n)$). Now, it is pretty well known that the probability to have exactly $k$ fixed points is about $\frac{1}{ek!}$ for large $n$. It is also well-known that the average number of cycles is exactly $H_n$. This gives the identity $$ H_n\approx e^{-1}\sum_{k\ge 0}\frac 1{k!}(F(n-k)+k)\approx F(n)+1 $$ so my guess would be $F(n)\approx H_n-1\approx \log n+\gamma-1$, just as Peter said, with an expected error of order $O(1/n)$

$\endgroup$
2
$\begingroup$

Asymptotically $N \to \infty$, the number of k-cycles $a_k$ independent random variables for a uniformly chosen permutation in $S_N$. $a_k$ is poisson distributed with mean $1/k$. This is consistent with there being $N$ elements to permute. There should be 1/2 of a two-cycles, 1/3 of a 3-cycles all the way to 1/N N-cycles. You can't have N+k-cycles for any k > 0. So the total number of people giving gives is

$ \mathbb{E}[cycles] = \mathbb{E}[\sum k a_k ] = \sum 1 = N $

You are counting the total number of cycles $a_1 + a_2 + \dots + a_k$ whose expected value is $1 + 1/2 + 1/3 + \dots + 1/N \approx \log N$. Since the number of cycles of different lengths are independent, conditioning on there being no fixed points - i.e. no one-cycles should just be the expected number of cycles of other lengths which is still $1/2 + 1/3 + \dots + 1/N \approx \log N$.

This is my best guess, based on an old paper from the 60's Ordered Cycle Lengths in a Random Permutation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.