{"id":5021,"date":"2016-11-16T12:21:06","date_gmt":"2016-11-16T10:21:06","guid":{"rendered":"https:\/\/wpethzprd.ethz.ch\/kowalski\/?p=5021"},"modified":"2024-02-20T13:40:32","modified_gmt":"2024-02-20T11:40:32","slug":"symmetric-powers-and-the-chinese-restaurant-process","status":"publish","type":"post","link":"https:\/\/blogs.ethz.ch\/kowalski\/2016\/11\/16\/symmetric-powers-and-the-chinese-restaurant-process\/","title":{"rendered":"Symmetric powers and the Chinese restaurant process"},"content":{"rendered":"

Here is a simple but cute computation<\/a> 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.<\/p>\n

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

This decomposition is (in the sources I know) usually proved using the “Chinese Restaurant Process” to describe random permutations ($latex n$ guests numbered from $latex 1$ to $latex 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 $latex n$ guests are seated, reading the cycles on the occupied tables gives a uniformly distributed element of $latex S_n$.) If one is only interested in $latex \\sigma_n$, then the decomposition above is equivalent to the formula
\n$latex \\mathbf{E}(z^{\\omega_n})=\\prod_{j=1}^n\\Bigl(1-\\frac{1}{j}+\\frac{z}{j}\\Bigr)$
\nfor the probability generating function of $latex \\omega_n$. (This formula comes up in mod-poisson convergence of $latex \\sigma_n$ and in analogies with the Erd\u00f6s-Kac Theorem, see this blog post<\/a>).<\/p>\n

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

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 $latex S_n$, and write $latex \\omega_n(\\sigma)$ for the number of … Continue reading Symmetric powers and the Chinese restaurant process<\/span><\/a><\/p>\n","protected":false},"author":625,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1086,2],"tags":[],"class_list":["post-5021","post","type-post","status-publish","format-standard","hentry","category-exercise","category-blogroll"],"_links":{"self":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/5021","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/users\/625"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/comments?post=5021"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/5021\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/media?parent=5021"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/categories?post=5021"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/tags?post=5021"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}