Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

The well-known random transpositions shuffle mixes in time of order $n \log n$. That this is a lower bound for the mixing time follows from that it takes this order of shuffles until every card has been touched at all. The top-to-random shuffle also takes order $n \log n$ for similar reasons. Lately some different non time-homogenous shuffles have been proposed where one makes sure that each card has been touched after time $n$. The question is if some such strategy can speed up mixing so as to make it of order $n$ or at least of lower order than $n \log n$. One such shuffle is the cyclic-to-random transpositions where at time $t$ mod $n$, the card at position $t$ is transposed with a uniformly random card. This shuffle was analyzed by Mossel et. al. (2004) and Saloff-Coste and Zuniga (2007). The showed that the order om mixing is still of order $n \log n$. Another shuffling technique of this kind is the card-cyclic-to-random shuffle (CCR shuffle), proposed by Ross Pinsky. This shuffle was analyzed by Morris et. al. (2014) and was also found to have a mixing time of order $n \log n$. A different variant of this, proposed by Morris, is the CCR shuffle with relabeling, where after each round the cards are relabeled according to their present position. We present a proof that this shuffle also takes time at least $n \log n$ to mix.