Abstract
We study the mixing time of the (n, k) Bernoulli-Laplace urn model, where k ∈ {0, 1, . . ., n}. Consider two urns, each containing n balls, so that when combined they have precisely n red balls and n white balls. At each step of the process choose uniformly at random k balls from the left urn and k balls from the right urn and switch them simultaneously. We show that if k = o(n), this Markov chain exhibits mixing time cutoff at n/4k log n and window of the order n/k log log n. This is an extension of a classical theorem of Diaconis and Shahshahani who treated the case k = 1.
| Original language | English |
|---|---|
| Pages (from-to) | 2621-2639 |
| Number of pages | 19 |
| Journal | Annales de l'institut Henri Poincare (B) Probability and Statistics |
| Volume | 56 |
| Issue number | 4 |
| DOIs | |
| State | Published - Nov 2020 |
Keywords
- Bernoulli-Laplace urn model
- Cutoff phenomenon
- Markov chain
- Mixing time
Fingerprint
Dive into the research topics of 'Cutoff for the Bernoulli-Laplace urn model with o(n) swaps'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver