Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-03T01:19:14.425Z Has data issue: false hasContentIssue false
  • English
  • Français

Information Loss in Riffle Shuffling

Published online by Cambridge University Press:  14 February 2002

DUDLEY STARK ,
A. GANESH  and
NEIL O’CONNELL
DUDLEY STARK
Affiliation:
Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail: [email protected])
A. GANESH
Affiliation:
Microsoft Research, St. George House, 1 Guildhall Street, Cambridge CB2 3NH, UK (e-mail: [email protected] )
NEIL O’CONNELL
Affiliation:
BRIMS, Hewlett-Packard Laboratories, Filton Road, Bristol BS34 8QZ, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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 m < log2n, and approximately exponentially for m > log2n. The deck becomes random in this information-theoretic sense after m = 3/2 log2n shuffles.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 1 , January 2002 , pp. 79 - 95
Copyright
2002 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)