## December 7, 2019

### 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:

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?

Posted at December 7, 2019 11:25 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3173

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

Posted by: John Baez on December 8, 2019 7:18 AM | Permalink | Reply to this

### Re: Random Permutations (Part 7)

Hi John,

a combinatorial way for looking on such relations is given by the so-called Weingarten calculus, which gives the Haar state (for example, the uniform counting measure on the permutation groups) in terms of summing over partitions of sets. In my paper Stochastic aspects of easy quantum groups with Teo Banica and Steve Curran we reproved the result for the cycles on the permutation group via such combinatorial means; however, the focus there is actually on quantum group versions of the permutation and also the orthogonal group. The nice thing is that one can treat all those objects in the same way; the difference is just the set of partitions which are involved; for the classical permutation group this is the set of all partitions, for the orthogonal group it is the subset of all pairings (matchings), and for the quantum versions one has to replace partitions by non-crossing partitions.

Posted by: Roland Speicher on December 8, 2019 11:46 AM | Permalink | Reply to this

### Re: Random Permutations (Part 7)

Thanks, Roland! I’m especially interested in the case of the hyperoctahedral groups, since like the symmetric groups these are Coxeter groups. There’s a third infinite sequence of Coxeter groups, the $D_n$ series. I wonder how things work for those.

Posted by: John Baez on December 12, 2019 7:47 AM | Permalink | Reply to this

### Re: Random Permutations (Part 7)

Here are a bunch of facts I want to understand and somehow ‘unify’. My goal is to understand how permutations, partitions and the Poisson distribution are connected. These are some tidbits that seem to hint at a deep connection.

1) Let $P$ be the Poisson distribution of mean $1$. Then the $n$th moment of $P$ is the number of partitions of an $n$-element set. In other words:

$E[P^n] = \sum_{k=0}^n S(n,k)$

where $S(n,k)$ is the number of partitions of $n$ into $k$ parts. This is sometimes called Dobiński’s formula.

More generally let $P(x)$ be the Poisson distribution of mean $x$. Then

$E[P(x)^n] = \sum_{k=0}^n S(n,k) x^k$

I don’t really understand these facts. I know how to relate Gaussian integrals to combinatorics using Feynman diagrams. Something similar should be going on here: there should be some nice way to see why moments of a Poisson distribution are governed by partitions of $n$ into $k$ parts. I know that Poisson distributions can be seen as the Fock space description of coherent states, so I have hopes.

2) Consider the falling power

$x^\underline{n} = x(x-1)(x-2) \cdots (x-n+1)$

which is the number of injections $n \hookrightarrow x$ when $x$ is an integer. It obeys a formula like this:

$x^n = \sum_{k=0}^n S(n,k) x^{\underline k}$

where $S(n,k)$ is the number of partitions of $n$ into $k$ parts.

It’s enough to prove this equation for natural numbers since polynomials are equal if they agree on all natural numbers. If $x$ is a natural number we can prove the equation as follows.

Interpret $x$ as a finite set and $x^n$ as the set of functions $n \to x$. Any such function has an epi-mono factorization which is unique up to isomorphism. That is, it’s given by some surjection $n \to k$, which gives a partition of $k$ into $n$ parts, followed by an injection $k \hookrightarrow n$. If we count the number of options (paying careful attention to avoid overcounting) we get the right side of the above equation.

This argument goes back to Rota.

3) Putting 1) and 2) together we get

$E[P^{\underline{n}}] = 1$

Conversely, this and 2) imply 1). Wikipedia’s proof of 1) reduces it to proving $E[P^{\underline{n}}] = 1$ in this way, and then quits there. This is not entirely satisfying!

4) On the other hand,

$x^\underline{n} = \sum_{k=0}^n s(n,k) x^k$

where $s_{n,k}$ is $(-1)^{n-k}$ times the number of permutations of $n$ with exactly $k$ disjoint cycles. This is a kind of ‘inverse transform’, reversing the change of basis from polynomials $x^{\underline k}$ to polynomials $x^n$ given in 2). But what’s really going on here, combinatorially?

Posted by: John Baez on December 8, 2019 9:00 PM | Permalink | Reply to this

### Re: Random Permutations (Part 7)

The fact that moments of the Poisson distribution are given in terms of partitions of sets comes quite naturally from the ”law of small numbers”, i.e., from the limit theorem that $((1-\frac 1n)\delta_0+\frac 1n \delta_1))^{*n}$ converges for $n\to\infty$ to the Poisson distribution. If you calculate the moments in the limit of this convolutions, then they are given in terms of partitions. Doing the same for the central limit theorem, gives you the moments in the limit in terms of pairings, which is the Wick formula for Gaussian variables.

This is all kind of folklore knowledge going probably back to the beginnings of limit theorems, but since the modern machinery of Fourier transforms has taken over, it is a bit hard to find such combinatorial approaches in standard textbooks. Let me thus shamelessly refer to my own lecture notes on free probability theory, where Theorem 2.16 gives such a statement with proof. (Actually, again the main focus is there on the free analogue, but the proof for the classical statement and the free statement is in parallel, one using all partitions, the other just non-crossing partitions.)

Posted by: Roland Speicher on December 9, 2019 4:57 PM | Permalink | Reply to this

### Re: Random Permutations (Part 7)

This sounds like what I need to read! For some reason I’m just seeing this comment now. I want a combinatorial approach because I’m hoping I can extract some wisdom from it.

Posted by: John Baez on December 12, 2019 7:52 AM | Permalink | Reply to this

Post a New Comment