A Chinese restaurant process for multiset permutations
Modern Stochastics: Theory and Applications · 01.01.2026 · 289-301
DOI: 10.15559/26-vmsta294 ↗Kurz gefasst
Fachartikel in der Zeitschrift Modern Stochastics: Theory and Applications, online erschienen am 03.03.2026. Verfasst von Dudley Stark. Die Arbeit nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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{}{}{0.0pt}{}{{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 ${\theta ^{\# \hspace{0.1667em}\mathrm{cycles}}}$, $\theta \gt 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. $\theta =1$, has distribution given by the sum of independent negative hypergeometric distributed random variables. For all $\theta \gt 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.
Zitieren
APA
Stark, D. (2026). A Chinese restaurant process for multiset permutations. Modern Stochastics: Theory and Applications, 289-301. https://doi.org/10.15559/26-vmsta294
Vancouver
Stark D. A Chinese restaurant process for multiset permutations. Modern Stochastics: Theory and Applications. 2026:289-301. doi:10.15559/26-vmsta294
BibTeX
@article{Stark2026,
author = {Stark, Dudley},
title = {A Chinese restaurant process for multiset permutations},
journal = {Modern Stochastics: Theory and Applications},
year = {2026},
pages = {289--301},
doi = {10.15559/26-vmsta294}
}
EUVIMED