Cutoff for a One-sided Transposition Shuffle

Michael Bate; Stephen Connor; Oliver Matheau-Raven

doi:10.1214/20-AAP1632

Cutoff for a One-sided Transposition Shuffle

Michael Bate, Stephen Connor, Oliver Matheau-Raven

Mathematics

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

Abstract

We introduce a new type of card shuffle called one-sided transpositions. At each step a card is chosen uniformly from the pack and then transposed with another card chosen uniformly from below it. This defines a random walk on the symmetric group generated by a distribution which is non-constant on the conjugacy class of transpositions. Nevertheless, we provide an explicit formula for all eigenvalues of the shuffle by demonstrating a useful correspondence between eigenvalues and standard Young tableaux. This allows us to prove the existence of a total-variation cutoff for the one-sided transposition shuffle at time $n\log n$. We also study a weighted generalisation of the shuffle which, in particular, allows us to recover the well known mixing time of the classical random transposition shuffle.

Original language	English
Pages (from-to)	1746-1773
Number of pages	28
Journal	The Annals of Applied Probability
Volume	31
Issue number	4
DOIs	https://doi.org/10.1214/20-AAP1632
Publication status	Published - 1 Aug 2021

Bibliographical note

This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

Access to Document

10.1214/20-AAP1632

One-SidedTranspositionsV2
This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.
Accepted author manuscript, 444 KB

Cite this

@article{9df4464f6a8044b5a6a4aaf710241241,

title = "Cutoff for a One-sided Transposition Shuffle",

abstract = "We introduce a new type of card shuffle called one-sided transpositions. At each step a card is chosen uniformly from the pack and then transposed with another card chosen uniformly from below it. This defines a random walk on the symmetric group generated by a distribution which is non-constant on the conjugacy class of transpositions. Nevertheless, we provide an explicit formula for all eigenvalues of the shuffle by demonstrating a useful correspondence between eigenvalues and standard Young tableaux. This allows us to prove the existence of a total-variation cutoff for the one-sided transposition shuffle at time $n\log n$. We also study a weighted generalisation of the shuffle which, in particular, allows us to recover the well known mixing time of the classical random transposition shuffle.",

author = "Michael Bate and Stephen Connor and Oliver Matheau-Raven",

note = "This is an author-produced version of the published paper. Uploaded in accordance with the publisher{\textquoteright}s self-archiving policy. Further copying may not be permitted; contact the publisher for details. ",

year = "2021",

month = aug,

day = "1",

doi = "10.1214/20-AAP1632",

language = "English",

volume = "31",

pages = "1746--1773",

journal = "The Annals of Applied Probability",

issn = "1050-5164",

publisher = "Institute of Mathematical Statistics",

number = "4",

}

TY - JOUR

T1 - Cutoff for a One-sided Transposition Shuffle

AU - Bate, Michael

AU - Connor, Stephen

AU - Matheau-Raven, Oliver

N1 - This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

PY - 2021/8/1

Y1 - 2021/8/1

N2 - We introduce a new type of card shuffle called one-sided transpositions. At each step a card is chosen uniformly from the pack and then transposed with another card chosen uniformly from below it. This defines a random walk on the symmetric group generated by a distribution which is non-constant on the conjugacy class of transpositions. Nevertheless, we provide an explicit formula for all eigenvalues of the shuffle by demonstrating a useful correspondence between eigenvalues and standard Young tableaux. This allows us to prove the existence of a total-variation cutoff for the one-sided transposition shuffle at time $n\log n$. We also study a weighted generalisation of the shuffle which, in particular, allows us to recover the well known mixing time of the classical random transposition shuffle.

AB - We introduce a new type of card shuffle called one-sided transpositions. At each step a card is chosen uniformly from the pack and then transposed with another card chosen uniformly from below it. This defines a random walk on the symmetric group generated by a distribution which is non-constant on the conjugacy class of transpositions. Nevertheless, we provide an explicit formula for all eigenvalues of the shuffle by demonstrating a useful correspondence between eigenvalues and standard Young tableaux. This allows us to prove the existence of a total-variation cutoff for the one-sided transposition shuffle at time $n\log n$. We also study a weighted generalisation of the shuffle which, in particular, allows us to recover the well known mixing time of the classical random transposition shuffle.

U2 - 10.1214/20-AAP1632

DO - 10.1214/20-AAP1632

M3 - Article

SN - 1050-5164

VL - 31

SP - 1746

EP - 1773

JO - The Annals of Applied Probability

JF - The Annals of Applied Probability

IS - 4

ER -