Perfect shuffling by lazy swaps

DOI10.1214/18-ECP151zbMATH Open1393.05004arXiv1802.05200MaRDI QIDQ1663759FDOQ1663759

Omer Angel, A. E. Holroyd

Publication date: 23 August 2018

Published in: Electronic Communications in Probability (Search for Journal in Brave)

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.

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

zbMATH Keywords

transpositionrandom permutationreduced wordsorting networkshufflingperfect mixing

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Searching and sorting (68P10) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Negative dependence and the geometry of polynomials
• On the number of reduced decompositions of elements of Coxeter groups
• Balanced tableaux
• Some circumstances where extra updates can delay mixing
• Random sorting networks
• Relating Edelman-Greene insertion to the Little map
• A Permutation Network
• On Square Roots of the Uniform Distribution on Compact Groups
• The Representation of Hypergeometric Random Variables using Independent Bernoulli Random Variables

Cited In (3)

• Cutoff for the cyclic adjacent transposition shuffle
• An efficient pairing-based shuffle argument
• Partial Shuffles by Lazy Swaps

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)