Cutoff for the Bernoulli-Laplace urn model with o(n) swaps

Alexandros Eskenazis, Evita Nestoridi

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)2621-2639
Number of pages19
JournalAnnales de l'institut Henri Poincare (B) Probability and Statistics
Volume56
Issue number4
DOIs
StatePublished - 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

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