Card shuffling and diophantine approximation

• 成果类型: Article
• 署名作者: Angel, Omer; Peres, Yuval; Wilson, David B.
• 署名单位: University of Toronto; Microsoft
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/07-AAP484
• 发表日期: 2008
• 页码: 1215-1231
• 关键词: top

摘要

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 behavior. For example, suppose k is the closest integer to alpha n for a fixed real alpha is an element of (0, 1). Then for rational 01 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)).