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

Alexandros Eskenazis; Evita Nestoridi

doi:10.1214/20-AIHP1052

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

Alexandros Eskenazis, Evita Nestoridi

Mathematics

Research output: Contribution to journal › Article › peer-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 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	https://doi.org/10.1214/20-AIHP1052
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

Access to Document

10.1214/20-AIHP1052

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

@article{fdf82c6bf57d48eda422e3f05dbbb6df,

title = "Cutoff for the Bernoulli-Laplace urn model with o(n) swaps",

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.",

keywords = "Bernoulli-Laplace urn model, Cutoff phenomenon, Markov chain, Mixing time",

author = "Alexandros Eskenazis and Evita Nestoridi",

note = "Funding Information: This work was completed while the first named author was in residence at the Institute for Pure & Applied Mathematics at UCLA for the long program on Quantitative Linear Algebra. He would like to thank the organizers of the program for the excellent working conditions. He was also supported in part by the Simons Foundation. Publisher Copyright: {\textcopyright} Association des Publications de l'Institut Henri Poincar{\'e}, 2020.",

year = "2020",

month = nov,

doi = "10.1214/20-AIHP1052",

language = "English (US)",

volume = "56",

pages = "2621--2639",

journal = "Annales de l'institut Henri Poincare (B) Probability and Statistics",

issn = "0246-0203",

publisher = "Institute of Mathematical Statistics",

number = "4",

}

TY - JOUR

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

AU - Eskenazis, Alexandros

AU - Nestoridi, Evita

N1 - Funding Information: This work was completed while the first named author was in residence at the Institute for Pure & Applied Mathematics at UCLA for the long program on Quantitative Linear Algebra. He would like to thank the organizers of the program for the excellent working conditions. He was also supported in part by the Simons Foundation. Publisher Copyright: © Association des Publications de l'Institut Henri Poincaré, 2020.

PY - 2020/11

Y1 - 2020/11

N2 - 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.

AB - 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.

KW - Bernoulli-Laplace urn model

KW - Cutoff phenomenon

KW - Markov chain

KW - Mixing time

UR - http://www.scopus.com/inward/record.url?scp=85094964929&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85094964929&partnerID=8YFLogxK

U2 - 10.1214/20-AIHP1052

DO - 10.1214/20-AIHP1052

M3 - Article

AN - SCOPUS:85094964929

VL - 56

SP - 2621

EP - 2639

JO - Annales de l'institut Henri Poincare (B) Probability and Statistics

JF - Annales de l'institut Henri Poincare (B) Probability and Statistics

SN - 0246-0203

IS - 4

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Cite this