Abstract: We characterize the minimum-length sequences of independent lazy simple transpositions whose composition is a uniformly random permutation. For every reduced word of the reverse permutation there is exactly one valid way to assign probabilities to the transpositions. It is an open problem to determine the minimum length of such a sequence when the simplicity condition is dropped.
Recommendations
Cites work
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3327350 (Why is no real title available?)
- A Permutation Network
- Balanced tableaux
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Negative dependence and the geometry of polynomials
- On Square Roots of the Uniform Distribution on Compact Groups
- On the number of reduced decompositions of elements of Coxeter groups
- Random sorting networks
- Relating Edelman-Greene insertion to the Little map
- Some circumstances where extra updates can delay mixing
- The Representation of Hypergeometric Random Variables using Independent Bernoulli Random Variables
Cited in
(4)
This page was built for publication: Perfect shuffling by lazy swaps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1663759)
