The Mathematics of Shuffling Cards

This book gives a lively development of the mathematics needed to answer the question, “How many times should a deck of cards be shuffled to mix it up?” The shuffles studied are the usual ones that real people use: riffle, overhand, and smooshing cards around on the table. The mathematics ranges from probability (Markov chains) to combinatorics (symmetric function theory) to algebra (Hopf algebras). There are applications to magic tricks and gambling along with a careful comparison of the mathematics to the results of real people shuffling real cards. The book explores links between shuffling and higher mathematics—Lie theory, algebraic topology, the geometry of hyperplane arrangements, stochastic calculus, number theory, and more. It offers a useful springboard for seeing how probability theory is applied and leads to many corners of advanced mathematics. The book can serve as a text for an upper division course in mathematics, statistics, or computer science departments and will be appreciated by graduate students and researchers in mathematics, statistics, and computer science, as well as magicians and people with a strong background in mathematics who are interested in games that use playing cards. Readership Graduate students and researchers interested in applications of mathematics to card shuffling. Cover Title page Contents Preface Acknowledgments Chapter 1. Shuffling cards: An introduction 1.1. Riffle shuffling and total variation 1.2. The problem, its motivation, and some theorems 1.3. Outline of the book 1.4. Background for reading this book Chapter 2. Practice and history of shuffling cards 2.1. Illustrations of some shuffles 2.2. Some early history Chapter 3. Convergence rates for riffle shuffles 3.1. Basic properties of riffle shuffling 3.2. Total variation and relative entropy 3.3. Effect of cuts 3.4. Guessing strategies and games 3.5. Strong uniform times and separation distance 3.6. Coupling and riffle shuffles 3.7. Appendix: Distances between probability distributions Chapter 4. Features 4.1. A single card 4.2. Shuffling with repeated cards 4.3. Different methods of dealing 4.4. Cycle structure, random polynomials, and Lie theory 4.5. Inversions 4.6. RSK shape, shuffling, and character theory of S_{∞} 4.7. The sign function 4.8. Other techniques Chapter 5. Eigenvectors and Hopf algebras 5.1. Overview 5.2. Combinatorics of words 5.3. The main theorem 5.4. Hopf algebras and Markov chains 5.5. Restriction/induction (with shuffling and Hopf algebras) 5.6. Shuffling and Hochschild homology 5.7. Appendix 1: Uses for eigenvectors 5.8. Appendix 2: Eigenvectors in this book Chapter 6. Shuffling and carries 6.1. Introduction to carries 6.2. Connection with riffle shuffles 6.3. A bit of why 6.4. Convergence rates of the carries chain 6.5. Eigenvalues and eigenvectors of the carries chain 6.6. Balanced carries 6.7. Carries, number theory, and fractals 6.8. Other connections 6.9. Appendix: Some proofs Chapter 7. Different models for riffle shuffling 7.1. Perfect shuffles 7.2. Thorp shuffle 7.3. Neat and clumpy shuffles: The Markov model 7.4. Dynamical systems and work of Lalley 7.5. Shuffling big decks Chapter 8. Move-to-front shuffling and variations 8.1. Coupling and convergence rates for the move-to-front shuffle 8.2. Formula for move-to-front shuffle 8.3. Spectral aspects of the move-to-front shuffle 8.4. Statistics of features after iterations of top-to-random shuffle 8.5. Weighted move to front and the Plackett-Luce model 8.6. Move-to-front shuffle with Markov dependent requests 8.7. Move to root for binary search trees 8.8. Connection with Stein’s method 8.9. Random-to-random shuffle Chapter 9. Shuffling and geometry 9.1. Hyperplane arrangements and random walks 9.2. Examples 9.3. General theory of hyperplane walks 9.4. An analog of riffle shuffling for general hyperplane arrangements 9.5. Stationary distribution, eigenfunctions, and lumped chains 9.6. Extensions 9.7. Connections and unification 9.8. Adjacent transpositions 9.9. Research problems 9.10. Appendix: Some proofs Chapter 10. Shuffling and algebraic topology 10.1. A topology teaser 10.2. First steps: Homology 10.3. Triangulating a product of simplices (and shuffling) 10.4. The Künneth formula 10.5. Translating shuffling theorems into homology 10.6. A different application of shuffling to topology 10.7. Final remarks Chapter 11. Type B shuffles and shelf-shuffling machines 11.1. Models of Type B shuffles 11.2. Cycle structure and RSK shape 11.3. Shelf shufflers 11.4. Other types 11.5. Research problems 11.6. Appendix: Proof of Proposition 11.3.2 Chapter 12. Descent algebras, P-partitions, and quasisymmetric functions 12.1. Descent theory 12.2. P-partitions and shuffling 12.3. Quasisymmetric functions and shuffles with biased cuts 12.4. Algebras of shuffles 12.5. A strange inequality 12.6. And then ... Chapter 13. Overhand shuffling 13.1. Introduction to the overhand shuffle 13.2. Mathematical models 13.3. Some theorems 13.4. Entertaining (and cheating) with overhand shuffles 13.5. The over-under shuffle 13.6. Coupling and the coin tossing model 13.7. Braid arrangement and overhand shuffles 13.8. Interval exchange maps and overhand shuffles Chapter 14. “Smoosh” shuffle 14.1. Introduction 14.2. Tests of mixing for smoosh shuffles 14.3. A mathematical model for spatial mixing 14.4. Some analysis 14.5. Bells, whistles, and computer implementation 14.6. A different model for spatial mixing 14.7. Combining shuffles and some practical tests Chapter 15. How to shuffle perfectly (randomly) Chapter 16. Applications to magic tricks, traffic merging, and statistics 16.1. Rising sequences 16.2. The Gilbreath principle 16.3. Tops and bottoms are special 16.4. A performable magic trick 16.5. A homework problem 16.6. Riffle stacking 16.7. Close stays close 16.8. Reds and blacks 16.9. Overhand shuffle 16.10. Smooshing 16.11. An application of shuffling to cars merging in traffic 16.12. Statistics of permutations Chapter 17. Shuffling and multiple zeta values 17.1. Multiple zeta values 17.2. A bit of proof 17.3. Chen’s integrals 17.4. Periods Bibliography Index Back Cover This book gives a lively development of the mathematics needed to answer the question, “How many times should a deck of cards be shuffled to mix it up?” The shuffles studied are the usual ones that real people use: riffle, overhand, and smooshing cards around on the table.The mathematics ranges from probability (Markov chains) to combinatorics (symmetric function theory) to algebra (Hopf algebras). There are applications to magic tricks and gambling along with a careful comparison of the mathematics to the results of real people shuffling real cards. The book explores links between shuffling and higher mathematics—Lie theory, algebraic topology, the geometry of hyperplane arrangements, stochastic calculus, number theory, and more. It offers a useful springboard for seeing how probability theory is applied and leads to many corners of advanced mathematics.The book can serve as a text for an upper division course in mathematics, statistics, or computer science departments and will be appreciated by graduate students and researchers in mathematics, statistics, and computer science, as well as magicians and people with a strong background in mathematics who are interested in games that use playing cards. -- Provided by publisher