Abstract: This paper studies biased riffle shuffles, first defined by Diaconis, Fill, and Pitman. These shuffles generalize the well-studied Gilbert-Shannon-Reeds shuffle and convolve nicely. An upper bound is given for the time for these shuffles to converge to the uniform distribution; this matches lower bounds of Lalley. A careful version of a bijection of Gessel leads to a generating function for cycle structure after one of these shuffles and gives new results about descents in random permutations. Results are also obtained about the inversion and descent structure of a permutation after one of these shuffles.
A generalization of the riffle shuffle as introduced by Gilbert, Shannon and Reeds (GSR) is discussed. This generalization was already introduced before but had still to be analyzed. The author generalizes several of the known results on the GSR-shuffles. He gives bounds on the time the new shuffles need to converge to the uniform distribution. Next the statistics on the structure (cycles, inversions and descents) of the permutations evolving from biased riffle shuffles are investigated.
Recommendations
Cited in
(20)- Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting
- Asymptotic results on weakly increasing subsequences in random words
- Applications of symmetric functions to cycle and increasing subsequence structure after shuffles
- On the rate of mixing for \(p\)-shuffles.
- Cycle structure of riffle shuffles
- Riffle shuffles and their associated dynamical systems
- Semisimple orbits of Lie algebras and card-shuffling measures on Coxeter groups
- Cutoff for the asymmetric riffle shuffle
- Determinantal formula for generalized riffle shuffle
- On leaf related statistics in recursive tree models
- Riffle shuffles of decks with repeated cards
- Descent algebras, hyperplane arrangements, and shuffling cards
- On an alternative sequence comparison statistic of Steele
- Analysis of casino shelf shuffling machines
- Descent-inversion statistics in riffle shuffles
- Riffle shuffles with biased cuts
- Applications of the Brauer complex: card shuffling, permutation statistics, and dynamical systems
- Sorting signed permutations by tandem duplication random loss and inverse tandem duplication random loss
- A generalization of carries process and riffle shuffles
- Biased random-to-top shuffling
This page was built for publication: The combinatorics of biased riffle shuffles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1297761)
