Improved mixing time bounds for the Thorp shuffle
Skip to main content
eScholarship
Open Access Publications from the University of California

Improved mixing time bounds for the Thorp shuffle

Published Web Location

https://arxiv.org/pdf/0912.2759.pdf
No data is associated with this publication.
Abstract

E. Thorp introduced the following card shuffling model. Suppose the number of cards $n$ is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile according to the outcome of a fair coin flip. Then drop from the other pile. Continue this way until both piles are empty. We show that if $n$ is a power of 2 then the mixing time of the Thorp shuffle is $O(\log^3 n)$. Previously, the best known bound was $O(\log^4 n)$.

Item not freely available? Link broken?
Report a problem accessing this item