Carries, Shuffling, and an Amazing Matrix
Authors:
- Persi DiaconisPDPersi Diaconis
- Jason FulmanJFJason Fulman
- 1 November 2009
- journal article
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 116 (9) , 788-803
Abstract
The number of ``carries'' when $n$ random integers are added forms a Markov chain [23]. We show that this Markov chain has the same transition matrix as the descent process when a deck of $n$ cards is repeatedly riffle shuffled. This gives new results for the statistics of carries and shuffling.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Carries, shuffling, and symmetric functionsAdvances in Applied Mathematics, 2009
- The Veronese construction for formal power series and graded algebrasAdvances in Applied Mathematics, 2009
- MATHEMATICAL DEVELOPMENTS FROM THE ANALYSIS OP RIFFLE SHUFFLING2003
- Applications of Symmetric Functions to Cycle and Increasing Subsequence Structure after ShufflesJournal of Algebraic Combinatorics, 2002
- Applications of the Brauer Complex: Card Shuffling, Permutation Statistics, and Dynamical SystemsJournal of Algebra, 2001
- No-feedback card guessing for dovetail shufflesThe Annals of Applied Probability, 1998
- Enumerative Combinatorics1997
- Riffle shuffles, cycles, and descentsCombinatorica, 1995
- Random walks on finite groups and rapidly mixing markov chains1983
- Advanced Combinatorics1974