A Chinese restaurant process for multiset permutations
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914328657002496 |
|---|---|
| author | Stark, Dudley |
| author_facet | Stark, Dudley |
| contents | Multisets are like sets, except that they can contain multiple copies of their elements. If there are $n_i$ copies of $i$, $1\leq i\leq t$, in multiset $M_t$, then there are $\binom{n_1+\cdots+n_t}{n_1,\ldots, n_t}$ possible permutations of $M_t$. Knuth showed how to factor any multiset permutation into cycles. For fixed $n_i$, $i\geq 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,\ldots$, to the multiset case, where we fix the $n_i$ and build permutations on $M_t$ sequentially for $t=1,2,\ldots$. 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\to\infty$ for the number of cycles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13979 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Chinese restaurant process for multiset permutations Stark, Dudley Probability 60C05 60J10 60F05 Multisets are like sets, except that they can contain multiple copies of their elements. If there are $n_i$ copies of $i$, $1\leq i\leq t$, in multiset $M_t$, then there are $\binom{n_1+\cdots+n_t}{n_1,\ldots, n_t}$ possible permutations of $M_t$. Knuth showed how to factor any multiset permutation into cycles. For fixed $n_i$, $i\geq 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,\ldots$, to the multiset case, where we fix the $n_i$ and build permutations on $M_t$ sequentially for $t=1,2,\ldots$. 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\to\infty$ for the number of cycles. |
| title | A Chinese restaurant process for multiset permutations |
| topic | Probability 60C05 60J10 60F05 |
| url | https://arxiv.org/abs/2509.13979 |