Analysis of top to bottom-k shuffles

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.

Recommendations

Cites Work

Cited In (9)

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