Improved mixing time bounds for the Thorp shuffle

الأصل · EN

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(³ n). Previously, the best known bound was O(⁴ n).