Information loss in riffle shuffling

D Stark; AJ Ganesh; N O'Connell

doi:10.1017/S0963548301004990

Information loss in riffle shuffling

D Stark, AJ Ganesh, N O'Connell

Research output: Contribution to journal › Article (Academic Journal) › peer-review

8 Citations (Scopus)

Abstract

We study the asymptotic behaviour of the relative entropy (to stationarity) for a commonly used model for riffle shuffling a deck of n cards m times. Our results establish and were motivated by a prediction in a recent numerical study of Trefethen and Trefethen. Loosely speaking, the relative entropy decays approximately linearly (in m) for in <log(2)n, and approximately exponentially for m > log(2) n. The deck becomes random in this information-theoretic sense after m = 3/2 log(2) n shuffles.

Translated title of the contribution	Information loss in riffle shuffling
Original language	English
Pages (from-to)	79 - 95
Number of pages	17
Journal	Combinatorics, Probability and Computing
Volume	11 (1)
DOIs	https://doi.org/10.1017/S0963548301004990
Publication status	Published - Jan 2002

Bibliographical note

Publisher: Cambridge University Press

Access to Document

10.1017/S0963548301004990

http://tinyurl.com/39jfjx

Handle.net

Persistent link

Cite this

@article{b7bf5678f0b24366a0b1d45b592de978,

title = "Information loss in riffle shuffling",

abstract = "We study the asymptotic behaviour of the relative entropy (to stationarity) for a commonly used model for riffle shuffling a deck of n cards m times. Our results establish and were motivated by a prediction in a recent numerical study of Trefethen and Trefethen. Loosely speaking, the relative entropy decays approximately linearly (in m) for in log(2) n. The deck becomes random in this information-theoretic sense after m = 3/2 log(2) n shuffles.",

author = "D Stark and AJ Ganesh and N O'Connell",

note = "Publisher: Cambridge University Press",

year = "2002",

month = jan,

doi = "10.1017/S0963548301004990",

language = "English",

volume = "11 (1)",

pages = "79 -- 95",

journal = "Combinatorics, Probability and Computing",

issn = "1469-2163",

publisher = "Cambridge University Press",

}

TY - JOUR

T1 - Information loss in riffle shuffling

AU - Stark, D

AU - Ganesh, AJ

AU - O'Connell, N

N1 - Publisher: Cambridge University Press

PY - 2002/1

Y1 - 2002/1

N2 - We study the asymptotic behaviour of the relative entropy (to stationarity) for a commonly used model for riffle shuffling a deck of n cards m times. Our results establish and were motivated by a prediction in a recent numerical study of Trefethen and Trefethen. Loosely speaking, the relative entropy decays approximately linearly (in m) for in log(2) n. The deck becomes random in this information-theoretic sense after m = 3/2 log(2) n shuffles.

AB - We study the asymptotic behaviour of the relative entropy (to stationarity) for a commonly used model for riffle shuffling a deck of n cards m times. Our results establish and were motivated by a prediction in a recent numerical study of Trefethen and Trefethen. Loosely speaking, the relative entropy decays approximately linearly (in m) for in log(2) n. The deck becomes random in this information-theoretic sense after m = 3/2 log(2) n shuffles.

U2 - 10.1017/S0963548301004990

DO - 10.1017/S0963548301004990

M3 - Article (Academic Journal)

SN - 1469-2163

VL - 11 (1)

SP - 79

EP - 95

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

ER -

Information loss in riffle shuffling

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this