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

CSM

Seminar

Card shuffling and Diophantine approximation

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

Seminar Room 1, Newton Institute

Abstract

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

Presentation

[ppt ]

Audio

MP3MP3

Video

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 ∧