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 (US) |
---|---|
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 |
All Science Journal Classification (ASJC) codes
- Statistics and Probability
- Statistics, Probability and Uncertainty
Keywords
- Bernoulli-Laplace urn model
- Cutoff phenomenon
- Markov chain
- Mixing time