Cutoff for generalised Bernoulli-Laplace urn models
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914157170786304 |
|---|---|
| author | Goenka, Ritesh Hermon, Jonathan Schmid, Dominik |
| author_facet | Goenka, Ritesh Hermon, Jonathan Schmid, Dominik |
| contents | We introduce a multi-colour multi-urn generalisation of the Bernoulli-Laplace urn model, consisting of $d$ urns, $m$ colours, and $dmn$ balls, with $dn$ balls of each colour and $mn$ balls in each urn. At each step, one ball is drawn uniformly at random from each urn, and the chosen balls are redistributed among the urns based on a permutation drawn from a distribution $μ$ on the symmetric group $S_d$. We study the mixing time of this Markov chain for fixed $m$, $d$, and $μ$, as $n \rightarrow \infty$. We show that there is cutoff whenever the chain on $[d]$ corresponding to the evolution of a single ball is irreducible, and that the same holds for a labeled version of the model. As an application, we also obtain partial results on cutoff for a card shuffling version of the model in which the cards are labeled and their ordering within each stack matters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_10630 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cutoff for generalised Bernoulli-Laplace urn models Goenka, Ritesh Hermon, Jonathan Schmid, Dominik Probability Combinatorics 60J10 (Primary) 60C05 (Secondary) We introduce a multi-colour multi-urn generalisation of the Bernoulli-Laplace urn model, consisting of $d$ urns, $m$ colours, and $dmn$ balls, with $dn$ balls of each colour and $mn$ balls in each urn. At each step, one ball is drawn uniformly at random from each urn, and the chosen balls are redistributed among the urns based on a permutation drawn from a distribution $μ$ on the symmetric group $S_d$. We study the mixing time of this Markov chain for fixed $m$, $d$, and $μ$, as $n \rightarrow \infty$. We show that there is cutoff whenever the chain on $[d]$ corresponding to the evolution of a single ball is irreducible, and that the same holds for a labeled version of the model. As an application, we also obtain partial results on cutoff for a card shuffling version of the model in which the cards are labeled and their ordering within each stack matters. |
| title | Cutoff for generalised Bernoulli-Laplace urn models |
| topic | Probability Combinatorics 60J10 (Primary) 60C05 (Secondary) |
| url | https://arxiv.org/abs/2511.10630 |