A Chinese restaurant process for multiset permutations

Abstract

Multisets are like sets, except that they can contain multiple copies of their elements. If there are $n_i$ copies of $i$, $1\le i\le t$, in multiset $M_t$, then there are $\left(\genfrac{}{}{0ex}{}{n_1+\cdots +n_t}{n_1,\dots ,n_t}\right)$ possible permutations of $M_t$. Knuth showed how to factor any multiset permutation into cycles. For fixed $n_i$, $i\ge 1$, we show how to adapt the Chinese restaurant process, which generates random permutations on $n$ elements with weighting $\hat{I}{¸}^{\#\mathrm{cycles}}$, $\hat{I}¸>0$, sequentially for $n=1,2,\dots$, to the multiset case, where we fix the $n_i$ and build permutations on $M_t$ sequentially for $t=1,2,\dots$. The number of cycles of a multiset permutation chosen uniformly at random, i.e.~$\hat{I}¸=1$, has distribution given by the sum of independent negative hypergeometric distributed random variables. For all $\hat{I}¸>0$, and under the assumption that $n_i=O(1)$, we show a central limit theorem as $t\to \infty$ for the number of cycles.

13 pages, accepted version