Haddadan, Shahrzad ;
Winkler, Peter
Mixing of Permutations by Biased Transposition
Abstract
Markov chains defined on the set of permutations of n elements have been studied widely by mathematicians and theoretical computer scientists. We consider chains in which a position i<n is chosen uniformly at random, and then sigma(i) and sigma(i+1) are swapped with probability depending on sigma(i) and sigma(i+1). Our objective is to identify some conditions that assure rapid mixing.
One case of particular interest is what we call the "gladiator chain," in which each number g is assigned a "strength" s_g and when g and g' are swapped, g comes out on top with probability s_g / ( s_g + s_g' ). The stationary probability of this chain is the same as that of the slowmixing "move ahead one" chain for selforganizing lists, but an open conjecture of Jim Fill's implies that all gladiator chains mix rapidly. Here we obtain some positive partial results by considering cases where the gladiators fall into only a few strength classes.
BibTeX  Entry
@InProceedings{haddadan_et_al:LIPIcs:2017:6992,
author = {Shahrzad Haddadan and Peter Winkler},
title = {{Mixing of Permutations by Biased Transposition}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {41:141:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6992},
URN = {urn:nbn:de:0030drops69928},
doi = {10.4230/LIPIcs.STACS.2017.41},
annote = {Keywords: Markov chains, permutations, self organizing lists, mixing time}
}
06.03.2017
Keywords: 

Markov chains, permutations, self organizing lists, mixing time 
Seminar: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Issue date: 

2017 
Date of publication: 

06.03.2017 