The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Card shuffling and Diophantine approximation

Wilson, D (Microsoft Research)
Friday 28 March 2008, 09:30-10:00

Seminar Room 1, Newton Institute


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


[ppt ]




The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧