The Mathematics of Shuffling Cards

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 ?_{∞}
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, ?-partitions, and quasisymmetric functions
12.1. Descent theory
12.2. ?-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