Partial mixing of semi-random transposition shuffles

Publication date: 11 February 2013

Abstract: We show that for any semi-random transposition shuffle on

n

cards, the mixing time of any given

k

cards is at most

n l o g k

, provided

k = o ((n / l o g n)^{1 / 2})

. In the case of the top-to-random transposition shuffle we show that there is cutoff at this time with a window of size O(n), provided further that

k o i n f t y

as

n o i n f t y

(and no cutoff otherwise). For the random-to-random transposition shuffle we show cutoff at time

(1 / 2) n l o g k

for the same conditions on

k

. Finally, we analyse the cyclic-to-random transposition shuffle and show partial mixing occurs at time

l e a l p h a n l o g k

for some

a l p h a

just larger than 1/2. We prove these results by relating the mixing time of

k

cards to the mixing of one card. Our results rely heavily on coupling arguments to bound the total variation distance.

This page was built for publication: Partial mixing of semi-random transposition shuffles