Analysis of top to bottom-\(k\) shuffles (Q2494572): Difference between revisions

The aim of this paper is to analyze a class of walks that generalizes the top to random chain, namely, top to bottom-\(k\) shuffles. These shuffles are generated by moving the top card uniformly at random to any of the bottom \(k_n\) positions of the deck. The author gives upper and lower bounds on the total variation mixing time for this shuffle as \(k_n\) ranges from a constant to \(n\). He also considers a symmetric variant of this shuffle in which at each step either the top card is randomly inserted into the bottom \(k_n\) positions or a random card from the bottom \(k_n\) positions is moved to the top. For this reversible shuffle the author derives bounds on the \(L^2\) mixing time. Finally, he transfers mixing time estimates for the above shuffles to the lazy top to bottom-\(k\) walks that move with probability 1/2 at each step.