Card shuffling and diophantine approximation

Angel, Omer; Peres, Yuval; Wilson, David B.

Card shuffling and diophantine approximation

Authors

Angel, Omer

Peres, Yuval

Wilson, David B.

Description

The ``overlapping-cycles shuffle'' mixes a deck of $n$ cards by moving either the $n$th card or the $(n-k)$th card to the top of the deck, with probability half each. We determine the spectral gap for the location of a single card, which, as a function of $k$ and $n$, has surprising behavior. For example, suppose $k$ is the closest integer to $αn$ for a fixed real $α\in(0,1)$. Then for rational $α$ the spectral gap is $Θ(n^{-2})$, while for poorly approximable irrational numbers $α$, such as the reciprocal of the golden ratio, the spectral gap is $Θ(n^{-3/2})$.
Published in at http://dx.doi.org/10.1214/07-AAP484 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)