Cutoff for the cyclic adjacent transposition shuffle

DOI10.1214/19-AAP1495zbMATH Open1432.60069arXiv1805.10508OpenAlexW2998908935MaRDI QIDQ2299593FDOQ2299593

Authors: Danny Nam, Evita Nestoridi 

Publication date: 21 February 2020

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Total variation cutoff for the transpose top-2 with random shuffle
• Mixing times for the simple exclusion process with open boundaries
• The \(S_k\) shuffle block dynamics
• The cutoff phenomenon for randomized riffle shuffles

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)