Cutoff for random to random card shuffle

Megan Bernstein; Evita Nestoridi

doi:10.1214/19-AOP1340

Cutoff for random to random card shuffle

Megan Bernstein, Evita Nestoridi

Mathematics

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

9 Scopus citations

Abstract

In this paper, we use the eigenvalues of the random to random card shuffle to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at 3/4 n log n-1/4 n log log n with window of order n, answering a conjecture of Diaconis.

Original language	English (US)
Pages (from-to)	3303-3320
Number of pages	18
Journal	Annals of Probability
Volume	47
Issue number	5
DOIs	https://doi.org/10.1214/19-AOP1340
State	Published - Sep 1 2019

All Science Journal Classification (ASJC) codes

Statistics and Probability
Statistics, Probability and Uncertainty

Keywords

Card shuffle
Cutoff
Cyclic-to-random
Mixing times
Random-to-random

Access to Document

10.1214/19-AOP1340

Cite this

@article{00fa59ea2acc40d8a6d686f24be8ede3,

title = "Cutoff for random to random card shuffle",

abstract = "In this paper, we use the eigenvalues of the random to random card shuffle to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at 3/4 n log n-1/4 n log log n with window of order n, answering a conjecture of Diaconis.",

keywords = "Card shuffle, Cutoff, Cyclic-to-random, Mixing times, Random-to-random",

author = "Megan Bernstein and Evita Nestoridi",

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

year = "2019",

month = sep,

day = "1",

doi = "10.1214/19-AOP1340",

language = "English (US)",

volume = "47",

pages = "3303--3320",

journal = "Annals of Probability",

issn = "0091-1798",

publisher = "Institute of Mathematical Statistics",

number = "5",

}

TY - JOUR

T1 - Cutoff for random to random card shuffle

AU - Bernstein, Megan

AU - Nestoridi, Evita

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

PY - 2019/9/1

Y1 - 2019/9/1

N2 - In this paper, we use the eigenvalues of the random to random card shuffle to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at 3/4 n log n-1/4 n log log n with window of order n, answering a conjecture of Diaconis.

AB - In this paper, we use the eigenvalues of the random to random card shuffle to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at 3/4 n log n-1/4 n log log n with window of order n, answering a conjecture of Diaconis.

KW - Card shuffle

KW - Cutoff

KW - Cyclic-to-random

KW - Mixing times

KW - Random-to-random

UR - http://www.scopus.com/inward/record.url?scp=85076760002&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85076760002&partnerID=8YFLogxK

U2 - 10.1214/19-AOP1340

DO - 10.1214/19-AOP1340

M3 - Article

AN - SCOPUS:85076760002

SN - 0091-1798

VL - 47

SP - 3303

EP - 3320

JO - Annals of Probability

JF - Annals of Probability

IS - 5

ER -

Cutoff for random to random card shuffle

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this