Cutoff for the cyclic adjacent transposition shuffle

Danny Nam, Evita Nestoridi

Research output: Contribution to journalArticle

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 2 n π 3 2 logn, which concludes that it is twice as fast as the AT shuffle. This is the first verification of cutoff phenomenon for a time-inhomogeneous card shuffle.

Original languageEnglish (US)
Pages (from-to)3861-3892
Number of pages32
JournalAnnals of Applied Probability
Volume29
Issue number6
DOIs
StatePublished - Jan 1 2019

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Adjacent transpositions
  • Cutoff phenomenon
  • Markov chains
  • Mixing time
  • Time inhomogeneous card shuffles
  • We are grateful to Yuval Peres and Allan Sly for their helpful comments

Fingerprint Dive into the research topics of 'Cutoff for the cyclic adjacent transposition shuffle'. Together they form a unique fingerprint.

  • Cite this