Shuffling large decks of cards and the Bernoulli-Laplace urn model (Q1721921): Difference between revisions

This paper provides the analysis of a Markov chain on the symmetric group, which extends classic urn schemes. If we think of this in terms of card shuffling, at each step a deck of cards of size \(2n\) is divided into two equal parts and these are perfectly shuffled independently. Then the \(k\) top cards from the first deck are removed from it and are put at the end of the other deck. One can think of this as two distinct urns containing \(n\) red and \(n\) black balls in which at each round one selects \(k\) balls uniformly at random from each urn and swaps them. The state of this chain can be taken to be the number of red balls in one of the urns. The authors show results on the mixing time of this chain. They derive several results depending on the limit of the ratio \(k/n\), distinguishing between a case where \(k/n \to 0\) and the one where \(k/n\to b>0\), with \(b\leq 1/2\). Furthermore, they determine an almost matching function below which the total variation distance from the stationary distribution can be close to 1. Also, they derive an explicit bound on the rate of convergence when \(k\) is very close to \(n/2\). A generalisation of this scheme is also considered, where the deck of cards is divided into more than 2 piles.