Secret Santa (expected no of cycles in a random permutation) - MathOverflow

Secret Santa (expected no of cycles in a random permutation)

2010-12-21T10:27:10Z

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.

Answer by Qiaochu Yuan for Secret Santa (expected no of cycles in a random permutation)

2010-12-21T10:34:00Z

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$.

Answer by John Mangual for Secret Santa (expected no of cycles in a random permutation)

2010-12-21T11:27:06Z

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.

Answer by Omer for Secret Santa (expected no of cycles in a random permutation)

2010-12-21T16:59:18Z

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.

Answer by Peter Shor for Secret Santa (expected no of cycles in a random permutation)

2010-12-21T17:17:40Z

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}$.

Answer by fedja for Secret Santa (expected no of cycles in a random permutation)

2010-12-21T21:20:25Z

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)$

Answer by Douglas Zare for Secret Santa (expected no of cycles in a random permutation)

2010-12-21T22:47:52Z

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.