Cutoff for the cyclic adjacent transposition shuffle

Danny Nam; Evita Nestoridi

doi:10.1214/19-AAP1495

Cutoff for the cyclic adjacent transposition shuffle

Danny Nam
, Evita Nestoridi

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

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 ₂ ⁿ _π ³ ₂ 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 language	English
Pages (from-to)	3861-3892
Number of pages	32
Journal	Annals of Applied Probability
Volume	29
Issue number	6
DOIs	https://doi.org/10.1214/19-AAP1495
State	Published - 2019

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

Access to Document

10.1214/19-AAP1495

Cite this

@article{027e9fd2f38b4f95bab6aa5a8a5176a4,

title = "Cutoff for the cyclic adjacent transposition shuffle",

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.",

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",

author = "Danny Nam and Evita Nestoridi",

note = "Publisher Copyright: {\textcopyright} Institute of Mathematical Statistics, 2019",

year = "2019",

doi = "10.1214/19-AAP1495",

language = "English",

volume = "29",

pages = "3861--3892",

journal = "Annals of Applied Probability",

issn = "1050-5164",

number = "6",

}

TY - JOUR

T1 - Cutoff for the cyclic adjacent transposition shuffle

AU - Nam, Danny

AU - Nestoridi, Evita

N1 - Publisher Copyright: © Institute of Mathematical Statistics, 2019

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Adjacent transpositions

KW - Cutoff phenomenon

KW - Markov chains

KW - Mixing time

KW - Time inhomogeneous card shuffles

KW - We are grateful to Yuval Peres and Allan Sly for their helpful comments

UR - https://www.scopus.com/pages/publications/85084193660

U2 - 10.1214/19-AAP1495

DO - 10.1214/19-AAP1495

M3 - Article

AN - SCOPUS:85084193660

SN - 1050-5164

VL - 29

SP - 3861

EP - 3892

JO - Annals of Applied Probability

JF - Annals of Applied Probability

IS - 6

ER -

Cutoff for the cyclic adjacent transposition shuffle

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this