Trailing the Dovetail Shuffle to its Lair

1992/05/01 by Dave Bayer, Persi Diaconis · 9 citations
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Mathematics and Applications #Algorithms and Data Compression

paper · pdf · doi:10.1214/aoap/1177005705

openalex publication_date 1992/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02

Abstract

We analyze the most commonly used method for shuffling cards. The main result is a simple expression for the chance of any arrangement after any number of shuffles. This is used to give sharp bounds on the approach to randomness: (3)/(2) log₂ n + θ shuffles are necessary and sufficient to mix up n cards. Key ingredients are the analysis of a card trick and the determination of the idempotents of a natural commutative subalgebra in the symmetric group algebra.

Cited by

• THE ACHILLES' HEEL OF THE GSR SHUFFLE: A NOTE ON NEW AGE SOLITAIRE
• The overhand shuffle mixes in Θ(n2logn) steps
• The Nature of Computation
• A look at generalized perfect shuffles
• Mixing times of lozenge tiling and card shuffling Markov chains
• q-exchangeability via quasi-invariance
• Binary logarithm [wikipedia]
• Markov chain mixing time [wikipedia]
• Shuffling [wikipedia]