Symmetric powers and the Chinese restaurant process

Here is a simple but cute computation that makes a good exercise in elementary representation theory with a probabilistic flavor — as usual, it’s probably well-known, but I wasn’t aware of it until doing the exercise myself.

We consider random permutations in the symmetric group $S_n$ , and write $\omega_n(\sigma)$ for the number of cycles in the disjoint cycle representation of $\sigma\in S_n$ . It is a well-known fact (which may be due to Feller) that, viewed as a random variable on $S_n$ (with uniform probability measure), there is a decomposition in law
$\omega_n=B_1+\cdots+B_n,$
where $B_i$ is a Bernoulli random variable taking value $0$ with probability $1-1/i$ and $1$ with probability $1/i$ , and moreover the $(B_i)$ ‘s are independent.

This decomposition is (in the sources I know) usually proved using the “Chinese Restaurant Process” to describe random permutations ( $n$ guests numbered from $1$ to $n$ enter a restaurant with circular tables; they successively sit either at the next available space of one of the tables already occupied, or pick a new one, with the same probability; after all $n$ guests are seated, reading the cycles on the occupied tables gives a uniformly distributed element of $S_n$ .) If one is only interested in $\sigma_n$ , then the decomposition above is equivalent to the formula
$\mathbf{E}(z^{\omega_n})=\prod_{j=1}^n\Bigl(1-\frac{1}{j}+\frac{z}{j}\Bigr)$
for the probability generating function of $\omega_n$ . (This formula comes up in mod-poisson convergence of $\sigma_n$ and in analogies with the Erdös-Kac Theorem, see this blog post).

Here is an algebraic proof of this generating function identity. First, $z\mapsto \mathbf{E}(z^{\omega_n})$ is a polynomial, so it is enough to prove the formula when $z=m$ is a non-negative integer. We can do this as follows: let $V$ be a vector space of dimension $m$ over $\mathbf{C}$ . Then define $W=V^{\otimes n}$ and view it as a representation space of $S_n$ where the symmetric group permutes the factors in the tensor product. Using the “obvious” basis of $W$ , it is elementary that the character of this representation is the function $g\mapsto m^{\sigma_n(g)}$ on $S_n$ (the matrix representing the action of $g$ is a permutation matrix). Hence, by character theory, $\mathbf{E}(m^{\sigma_n})$ is the dimension of the $S_n$ -invariant subspace of $W$ . Since the representation is semisimple, this is the dimension of the coinvariant space, which is the $n$ -th symmetric power of $V.$ This in turn is well-known (number of monomials of degree $n$ in $m$ variables), and we get
$\mathbf{E}(m^{\omega_n})=\binom{m+n-1}{n}=\prod_{j=1}^n\Bigl(1-\frac{1}{j}+\frac{m}{j}\Bigr),$
as claimed!

Symmetric powers and the Chinese restaurant process

Published by

Kowalski