The combinatorics of biased riffle shuffles

DOI10.1007/PL00009814MaRDI QIDQ1297761zbMATHOpenAlexFDO

Authors Jason Fulman

Publication date 14 September 1999

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9712240

zbMATH Keywords

random permutationsriffle shufflesGilbert-Shannon-Reeds-shuffles

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05)

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.

Recommendations

• Riffle shuffles with biased cuts
• Riffle shuffles, cycles, and descents
• Trailing the dovetail shuffle to its lair
• Cycle structure of riffle shuffles

Cited in

(20)

• Riffle shuffles and their associated dynamical systems
• Semisimple orbits of Lie algebras and card-shuffling measures on Coxeter groups
• On the rate of mixing for \(p\)-shuffles.
• On leaf related statistics in recursive tree models
• Asymptotic results on weakly increasing subsequences in random words
• Cutoff for the asymmetric riffle shuffle
• Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting
• Descent algebras, hyperplane arrangements, and shuffling cards
• Applications of symmetric functions to cycle and increasing subsequence structure after shuffles
• Analysis of casino shelf shuffling machines
• Sorting signed permutations by tandem duplication random loss and inverse tandem duplication random loss
• Biased random-to-top shuffling
• A generalization of carries process and riffle shuffles
• Applications of the Brauer complex: card shuffling, permutation statistics, and dynamical systems
• Determinantal formula for generalized riffle shuffle
• Descent-inversion statistics in riffle shuffles
• On an alternative sequence comparison statistic of Steele
• Riffle shuffles of decks with repeated cards
• Riffle shuffles with biased cuts
• Cycle structure of riffle shuffles

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)