HP Labs Technical Reports
Click here for full text:
Information Loss in Card Shuffling
Stark, Dudley; Ganesh, A.; O'Connell, Neil
HPL-BRIMS-1999-05
Keyword(s): card shuffling; Kullback-Leibler distance; Markov chains
Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. We find limits for the relative entropy (to stationarity) of a commonly used model for riffle-shuffling a deck of n cards m times. We establish the somewhat surprising fact, which was predicted by Trefethen and Trefethen in a recent numerical study, that for m< log2 n the relative entropy decreases linearly and for m> log2 n it decreases geometrically. Thus there is a kind of secondary phase transition, which may be to some extent general in nature. The deck becomes random in relative entropy after m = 3/2 log2 n shuffles.
14 Pages
Back to Index
| 
