Random Permutations (Part 7)
Posted by John Baez
Last time I computed the expected number of cycles of length $k$ in a random permutation of an $n$-element set. The answer is wonderfully simple: $1/k$ for all $k = 1, \dots, n$.
As Mark Meckes pointed out, this fact is just a shadow of a more wonderful fact. Let $C_k$ be the number of cycles of length $k$ in a random permutation of an $n$-element set, thought of as a random variable. Then as $n \to \infty$, the distribution of $C_k$ approaches a Poisson distribution with mean $1/k$.
But this is just a shadow of an even more wonderful fact!
First, if we fix some number $b \ge 1$, and look at all the random variables $C_1, \dots, C_b$, they converge to independent Poisson distributions as $n \to \infty$.
In fact we can even let $b \to \infty$ as $n \to \infty$, so long as $n$ outstrips $b$, in the following sense: $b/n \to 0$. The random variables $C_1, \dots , C_b$ will still converge to independent Poisson distributions.
These facts are made precise and proved here:
- Richard Arratia and Simon Tavaré, The cycle structure of random permutations, The Annals of Probability 20 (1992), 1567–1591.
In the proof they drop another little bombshell. Suppose $j \ne k$. Then the random variables $C_j$ and $C_k$ become uncorrelated as soon as $n$ gets big enough for a permutation of an $n$-element set to have both a $j$-cycle and a $k$-cycle. That is, their expected values obey
$E(C_j C_k) = E(C_j) E(C_k)$
whenever $n \ge j + k$. Of course when $n \lt j + k$ it’s impossible to have both a cycle of length $j$ and one of length $k$, so in that case we have
$E(C_j C_k) = 0$
It’s exciting to me how the expected value $E(C_j C_k)$ pops suddenly from $0$ to $E(C_j) E(C_k) = 1/jk$ as soon as our set gets big enough to allow both a $j$-cycle and a $k$-cycle. It says that in some sense the presence of a large cycle in a random permutation does not discourage the existence of other large cycles… unless it absolutely forbids it!
This is a higher-level version of a phenomenon we’ve already seen: $E(C_k)$ jumps from $0$ to $1/k$ as soon as $n \ge k$.
More generally, Arratia and Tavaré show that
$E(C_{j_1} \, \cdots \, C_{j_m}) = E(C_{j_1}) \, \cdots \,E(C_{j_m})$
whenever $n \ge j_1 + \cdots + j_m$. But on the other hand, clearly
$E(C_{j_1} \, \cdots \, C_{j_m}) = 0$
whenever $n \lt j_1 + \cdots + j_m$, at least if the numbers $j_i$ are distinct. After all, it’s impossible for a permutation of a finite set to have cycles of different lengths that sum to more than the size of that set.
I’m trying to understand the nature of random permutations. These results help a lot. But instead of describing how they’re proved, I want to conclude with a picture that has also helped me a lot:
One can argue that Flajolet and Sedgewick should have used circumferences rather than areas to indicate cycle lengths: after all, the circumference is a kind of ‘cycle length’. That would have made the large cycles seem even larger compared to the puny ones.
Of course, experts on the visual display of quantitative information have a lot of opinions on these issues. But never mind! Let’s extract some morals from this chart.
We can see that a random permutation of a large set has rather few cycles on average. To be precise, the expected number of cycles in a random permutation of an $n$-element set is $\sim \ln n$.
We can also see that the lengths of the cycles range dramatically from tiny to large. To be precise, suppose $1 \le m \le m' \le n$. Then since the expected number of cycles of length $k$ is $1/k$, the expected number of cycles of length between $m$ and $m'$ is close to
$\ln m' \; - \; \ln m$
Thus we can expect as many cycles of length between $1$ and $10$ as between $10$ and $100$, or between $100$ and $1000$, etc.
So, I’m now imagining a random permutation of a large set as a way of chopping up a mountain into rocks with a wild range of sizes: some sand grains, some pebbles, some fist-sized rocks and some enormous boulders. Moreover, as long as two different sizes don’t add up to more than the size of our mountain, the number of rocks of those two sizes are uncorrelated.
I want to keep improving this intuition. For example, if $j \ne k$ and $n \ge j + k$, are the random variables $C_j$ and $C_k$ independent, or just uncorrelated?
Re: Random Permutations (Part 7)
Maybe some of you can help me understand (and thereby prove) Equations 5 and 6 in Arratia and Tavare’s paper. They cite another paper for this equation, from a journal on population biology! But I think it should be easy and fun to figure out ourselves.
These equations concern the random variable $C_k$ that I was discussing: the number of cycles of length $k$ in a random permutation of an $n$-element set. It’s a formula for expected values of products of such random variables.
We take a list of numbers $m_1 , \dots, m_\ell$ and compute the expected value of the random variable
$C_1^{\underline{m}_1} \cdots C_\ell^{\underline{m}_\ell}$
where the underline indicates ‘falling powers’:
$x^\underline{m} = x(x-1)(x-2) \cdots (x-m+1)$
Equation 5 says that
$E(C_1^{\underline{m}_1} \cdots C_\ell^{\underline{m}_\ell} = \prod_{k = 1}^\ell \left( \frac{1}{k} \right)^{m_k}$
or in other words
$E\left( \prod_{k = 1}^\ell C_k^{\underline{m}_k} \right) = \prod_{k = 1}^\ell \left( \frac{1}{k} \right)^{m_k}$
if $m_1 + 2 m_2 + \cdots + \ell m_\ell \le n$. It also says that if this inequality is violated, the expected value is $0$. So, the main thing I need to understand is this equation.
But then, in Equation 6, they reformulate this equation very suggestively as follows, given that the inequality holds:
$E\left( \prod_{k = 1}^\ell C_k^{\underline{m}_k} \right) = E\left(\prod_{k = 1}^\ell Z_k^{\underline{m}_k}\right)$
where the $Z_k$ are independent Poisson distributions with means $1/k$. To see why this reformulation works, I just need to see why
$E\left(Z_k^{\underline{n}}\right) = \left( \frac{1}{k} \right)^{n}$
This must be a famous thing about Poisson distributions. I think I’ve even used it before in my own work. I bet one proof uses Dobiński’s formula for the number of partitions of an $n$-element set. If we go this route, I’ll probably need to use the relation between partitions and permutations to figure out what’s really going on here.