License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.41
URN: urn:nbn:de:0030-drops-69928
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6992/
Go to the corresponding LIPIcs Volume Portal

Haddadan, Shahrzad ; Winkler, Peter

Mixing of Permutations by Biased Transposition

pdf-format:
LIPIcs-STACS-2017-41.pdf (0.7 MB)

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 slow-mixing "move ahead one" chain for self-organizing 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:1--41:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte ValleĢe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6992},
  URN =		{urn:nbn:de:0030-drops-69928},
  doi =		{10.4230/LIPIcs.STACS.2017.41},
  annote =	{Keywords: Markov chains, permutations, self organizing lists, mixing time}
}

Keywords: Markov chains, permutations, self organizing lists, mixing time
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI