Mixing of permutations by biased transpositions

DOI10.1007/S00224-018-9899-5MaRDI QIDQ2321931zbMATH OpenOpenAlexWikidataFDO

Authors Shahrzad Haddadan, Peter Winkler

Publication date 27 August 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-018-9899-5

zbMATH Keywords

permutationsMarkov chainsmixing timeself organizing lists

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Recommendations

• Mixing of permutations by biased transposition
• Mixing times of Markov chains for self‐organizing lists and biased permutations
• Rapid mixing of \(k\)-class biased permutations
• Mixing times of Markov chains for self-organizing lists and biased permutations
• Biased random-to-top shuffling

Cites work

• Analyzing Glauber dynamics by comparison of Markov chains
• Approximating the Permanent
• Comparison techniques for random walk on finite groups
• Disjoint Decomposition of Markov Chains and Sampling Circuits in Cayley Graphs
• Generating a random permutation with random transpositions
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing of permutations by biased transposition
• Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk
• Mixing times of Markov chains for self-organizing lists and biased permutations
• Mixing times of lozenge tiling and card shuffling Markov chains
• Mixing times of the biased card shuffling and the asymmetric exclusion process
• NON-NULL RANKING MODELS. I
• On reconstructing a hidden permutation
• On self-organizing sequential search heuristics
• Rapid mixing of \(k\)-class biased permutations
• Sampling biased lattice configurations using exponential metrics
• The mixing time for simple exclusion
• Trailing the dovetail shuffle to its lair

Cited in

(5)

• Rapid Mixing of \({\boldsymbol{k}}\)-Class Biased Permutations
• Mixing times of Markov chains for self-organizing lists and biased permutations
• Mixing times of Markov chains for self‐organizing lists and biased permutations
• Mixing of permutations by biased transposition
• Rapid mixing of \(k\)-class biased permutations

This page was built for publication: Mixing of permutations by biased transpositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2321931)