Card shuffling and Diophantine approximation

DOI10.1214/07-AAP484zbMATH Open1142.60046arXiv0707.2994OpenAlexW3101268327MaRDI QIDQ930684FDOQ930684

David B. Wilson, Yuval Peres, Omer Angel

Publication date: 1 July 2008

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: 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 $alphan$ for a fixed real $alphain(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})$.

Full work available at URL: https://arxiv.org/abs/0707.2994

Recommendations

• The Mathematics of Shuffling Cards
• From shuffling cards to Artin's conjecture
• Card Shuffling and the Polynomial Numerical Hull of Degree k
• Card shuffling and \(P\)-partitions
• Random orderings of the integers and card shuffling
• Card shuffling and a transformation on \(S_ n\)
• On card shuffling, a mathematical menu
• A discrete probability problem in card shuffling

zbMATH Keywords

card shufflingDiophantine approximation

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Comparison techniques for random walk on finite groups
• Mixing time of the Rudvalis shuffle
• The Asymptotic Behavior of the Solutions of a Class of Differential-Difference Equations
• Title not available (Why is that?)
• Analysis of top to bottom-\(k\) shuffles
• Biased random-to-top shuffling

Cited In (4)

• Analysis of a non-reversible Markov chain speedup by a single edge
• Random orderings of the integers and card shuffling
• Card shuffling and a transformation on \(S_ n\)
• Sensitivity of Mixing Times in Eulerian Digraphs

This page was built for publication: Card shuffling and Diophantine approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930684)