Feeds:
Posts

Short cycles in random permutations

Previously we showed that the distribution of fixed points of a random permutation of $n$ elements behaves asymptotically (in the limit as $n \to \infty$) like a Poisson random variable with parameter $\lambda = 1$. As it turns out, this generalizes to the following.

Theorem: As $n \to \infty$, the number of cycles of length $1, 2, ... k$ of a random permutation of $n$ elements are asymptotically independent Poisson with parameters $1, \frac{1}{2}, ... \frac{1}{k}$.

This is a fairly strong statement which essentially settles the asymptotic description of short cycles in random permutations.

Proof

We will prove pointwise convergence of moment generating functions. First, the Poisson random variable $X_{\lambda}$ with parameter $\lambda$ is the random variable which takes on non-negative integer values with probabilities

$\displaystyle \mathbb{P}(X_{\lambda} = k) = e^{-\lambda} \frac{\lambda^k}{k!}$.

$X_{\lambda}$ therefore has moment generating function

$\displaystyle \mathbb{E}(e^{t X_{\lambda}}) = e^{-\lambda} \sum_{k \ge 0} \frac{e^{tk} \lambda^k}{k!} = e^{\lambda (e^t - 1)}$

which is the exponential generating function of the Touchard polynomials

$\displaystyle T_n(\lambda) = \sum_{k=0}^n S(n, k) \lambda^k$

where $S(n, k)$ are the Stirling numbers of the second kind. These specialize to the Bell numbers when $\lambda = 1$ as expected.

Because we are discussing $k$ random variables, we should compute a joint moment generating function. The joint moment generating function of $k$ independent Poisson random variables with parameters $\lambda_1, ... \lambda_k$ is

$\displaystyle \mathbb{E}(\exp \left( t_1 X_{\lambda_1} + ... + t_k X_{\lambda_k} \right) = \exp \left( \lambda_1 (e^{t_1} - 1) + ... + \lambda_k (e^{t_k} - 1) \right)$.

Back to permutations. By the exponential formula, letting $c_k(\sigma)$ denote the number of cycles of length $k$ in a permutation $\sigma$, we have

$\displaystyle \sum_{n \ge 0} \frac{t^n}{n!} \sum_{\sigma \in S_n} z_1^{c_1(\sigma)} ... z_k^{c_k(\sigma)} = \exp \left( z_1 t + ... + z_k \frac{t^k}{k} + \frac{t^{k+1}}{k+1} + ... \right)$

which simplifies to

$\displaystyle \frac{1}{1 - t} \exp \left( (z_1 - 1) t + ... + (z_k - 1) \frac{t^k}{k} \right)$.

It is a general and straightforward observation that if $f(t)$ is a power series with radius of convergence greater than $1$, then $\frac{f(t)}{1 - t}$ has a power series expansion whose coefficients asymptotically approach $f(1)$. Substituting $z_i = e^{t_i}$, we conclude that the coefficients of

$\displaystyle \sum_{n \ge 0} \frac{t^n}{n!} \sum_{\sigma \in S_n} e^{t_1 c_1(\sigma)} ... e^{t_k c_k(\sigma)}$

asymptotically approach

$\displaystyle \exp \left( (e^{t_1} - 1) + ... + (e^{t_k} - 1) \frac{1}{k} \right)$.

But the former is precisely the joint moment generating function of $c_1, ... c_k$, and the latter is precisely the joint moment generating function of independent Poisson random variables with parameters $1, ... \frac{1}{k}$. The conclusion follows.

Mean and variance

An exact result which can be deduced using the above methods is that the expected number of $k$-cycles of a random permutation of $n$ elements is $\frac{1}{k}$ if $k \le n$ and $0$ otherwise. It follows that the total expected number of cycles is the harmonic number

$\displaystyle H_n = 1 + \frac{1}{2} + ... + \frac{1}{n} \sim \log n$.

Since Poisson random variables have the same mean and variance, and by the asymptotic independence statement above, we expect the variance of the total number of cycles to also be asymptotic to $\log n$. This is in fact true, and can be shown using the exponential formula as above.

In The Anatomy of Integers and Permutations, Granville suggested that the decomposition of a random permutation into cycles should be thought of as analogous to the decomposition of a random integer into prime factors. In light of this analogy, the above computation should be thought of as roughly analogous to the Hardy-Ramanujan theorem.

One Response

1. […] « Short cycles in random permutations […]