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 is an element of 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.