EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Chinese restaurant process for multiset permutations

Dudley Stark

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →