Analysis of top to bottom-k shuffles

Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: A deck of

n

cards is shuffled by repeatedly moving the top card to one of the bottom

k_{n}

positions uniformly at random. We give upper and lower bounds on the total variation mixing time for this shuffle as

k_{n}

ranges from a constant to

n

. We also consider 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 we derive bounds on the

L^{2}

mixing time. Finally, we transfer mixing time estimates for the above shuffles to the lazy top to bottom-

k

walks that move with probability 1/2 at each step.

Review text

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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Analysis of top to bottom-\(k\) shuffles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494572)