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

2018/05/20 by Eskenazis, Alexandros, Nestoridi, Evita
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1805.07803

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)loglog n. This is an extension of a classical theorem of Diaconis and Shahshahani who treated the case k=1.

Related

• Cutoff in the Bernoulli-Laplace Model With Unequal Colors and Urn Sizes
• Cutoff for generalised Bernoulli-Laplace urn models
• Cutoff in the Bernoulli-Laplace model with O(n) swaps
• Limit Profile for the Bernoulli--Laplace Urn
• Shuffling large decks of cards and the Bernoulli-Laplace urn model