The "overlapping-cycles shuffle'' mixes a deck of n cards by moving either the nth 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 behaviour. For example, suppose k is the closest integer to alpha n for a fixed real alpha in (0,1). Then for rational alpha the spectral gap is Theta(n^{-2}), while for poorly approximable irrational numbers alpha, such as the reciprocal of the golden ratio, the spectral gap is Theta(n^{-3/2}).
Related Links
* http://front.math.ucdavis.edu/0707.2994 - arXiv link
view more