Return to Colloquia & Seminar listing
Card-cyclic-to-random shuffling with relabelingMathematical Physics & Probability
|Speaker: ||Johan Jonasson, Chalmers Institute of Technology|
|Location: ||2112 MSB|
|Start time: ||Wed, Feb 3 2016, 4:10PM|
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.