DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2017.41

Mixing of Permutations by Biased Transposition

Authors: Shahrzad Haddadan and Peter Winkler

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

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.

Cite as

Shahrzad Haddadan and Peter Winkler. Mixing of Permutations by Biased Transposition. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{haddadan_et_al:LIPIcs.STACS.2017.41,
  author =	{Haddadan, Shahrzad and Winkler, Peter},
  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 =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.41},
  URN =		{urn:nbn:de:0030-drops-69928},
  doi =		{10.4230/LIPIcs.STACS.2017.41},
  annote =	{Keywords: Markov chains, permutations, self organizing lists, mixing time}
}

Search Results

Documents authored by Winkler, Peter

Mixing of Permutations by Biased Transposition

Abstract

Cite as

Thanks for your feedback!

Could not send message