A Chinese restaurant process for multiset permutations

2025/09/17 by Stark, Dudley
#60C05 60J10 60F05 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2509.13979

Abstract

Multisets are like sets, except that they can contain multiple copies of their elements. If there are n_i copies of i, 1≤ i≤ t, in multiset M_t, then there are \binomn₁+⋯+n_tn₁,…, n_t possible permutations of M_t. Knuth showed how to factor any multiset permutation into cycles. For fixed n_i, i≥ 1, we show how to adapt the Chinese restaurant process, which generates random permutations on n elements with weighting θ^# \rm cycles, θ>0, sequentially for n=1,2,…, to the multiset case, where we fix the n_i and build permutations on M_t sequentially for t=1,2,…. The number of cycles of a multiset permutation chosen uniformly at random, i.e.~θ=1, has distribution given by the sum of independent negative hypergeometric distributed random variables. For all θ>0, and under the assumption that n_i=O(1), we show a central limit theorem as t→∞ for the number of cycles.

Citations

• Scaling limit for small blocks in the Chinese restaurant process
• Limit theorems for random permutations induced by Chinese restaurant processes
• A two-table theorem for a disordered Chinese restaurant process
• Random Permutations and Queues

Related

• Limit theorems for random permutations induced by Chinese restaurant processes
• Some Connections Between Cycles and Permutations that Fix a Set and Touchard Polynomials and Covers of Multisets
• Random Permutations and Queues
• Large cycles and a functional central limit theorem for generalized weighted random permutations
• The number of cycles of specified normalized length in permutations