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!

Published by

Kowalski

I am a professor of mathematics at ETH Zürich since 2008.