Cutoff for the cyclic adjacent transposition shuffle

DOI10.1214/19-AAP1495MaRDI QIDQ2299593zbMATHOpenAlexFDO

Authors Danny Nam, Evita Nestoridi

Publication date 21 February 2020

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

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

zbMATH Keywords

Markov chainsmixing timecutoff phenomenonadjacent transpositionstime inhomogeneous card shuffles

Mathematics Subject Classification ID

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

Abstract: We study the cyclic adjacent transposition (CAT) shuffle of $n$ cards, which is a systematic scan version of the random adjacent transposition (AT) card shuffle. In this paper, we prove that the CAT shuffle exhibits cutoff at $frac{n}^{3}2p{i}^{2}logn$, which concludes that it is twice as fast as the AT shuffle.

Recommendations

• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• Cutoff for random to random card shuffle
• Cutoff for a one-sided transposition shuffle
• Extremal measures with prescribed moments
• Mixing time of the card-cyclic-to-random shuffle

Cites work

• scientific article; zbMATH DE number 192908 (Why is no real title available?)
• scientific article; zbMATH DE number 1942428 (Why is no real title available?)
• Attempt at a Strongest Vector Topology
• Can extra updates delay mixing?
• Convergence of some time inhomogeneous Markov chains via spectral techniques
• Merging and stability for time inhomogeneous finite Markov chains
• Merging for time inhomogeneous finite Markov chains. I: Singular values and stability
• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• Mixing time of the card-cyclic-to-random shuffle
• Mixing times of lozenge tiling and card shuffling Markov chains
• Perfect shuffling by lazy swaps
• Probabilistic and combinatorial aspects of the card-cyclic to random insertion shuffle
• Probability
• Shuffling Cards and Stopping Times
• Spatial mixing and non-local Markov chains
• Time inhomogeneous Markov chains with wave-like behavior

Cited in

(9)

• The cutoff phenomenon for randomized riffle shuffles
• Cutoff profile of the metropolis biased card shuffling
• Total variation cutoff for the transpose top-2 with random shuffle
• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• Cutoff phenomenon for the asymmetric simple exclusion process and the biased card shuffling
• Mixing times for the simple exclusion process with open boundaries
• Cutoff for a one-sided transposition shuffle
• Cutoff for random to random card shuffle
• The \(S_k\) shuffle block dynamics

This page was built for publication: Cutoff for the cyclic adjacent transposition shuffle

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