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.APPROX/RANDOM.2020.3
URN: urn:nbn:de:0030-drops-126069
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12606/
Go to the corresponding LIPIcs Volume Portal


Miracle, Sarah ; Streib, Amanda Pascoe ; Streib, Noah

Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains

pdf-format:
LIPIcs-APPROX3.pdf (0.6 MB)


Abstract

In this paper, we address a conjecture of Fill [Fill03] about the spectral gap of a nearest-neighbor transposition Markov chain ℳ_nn over biased permutations of [n]. Suppose we are given a set of input probabilities 𝒫 = {p_{i,j}} for all 1 ≤ i, j ≤ n with p_{i, j} = 1-p_{j, i}. The Markov chain ℳ_nn operates by uniformly choosing a pair of adjacent elements, i and j, and putting i ahead of j with probability p_{i,j} and j ahead of i with probability p_{j,i}, independent of their current ordering.
We build on previous work [S. Miracle and A.P. Streib, 2018] that analyzed the spectral gap of ℳ_nn when the particles in [n] fall into k classes. There, the authors iteratively decomposed ℳ_nn into simpler chains, but incurred a multiplicative penalty of n^-2 for each application of the decomposition theorem of [Martin and Randall, 2000], leading to an exponentially small lower bound on the gap. We make progress by introducing a new complementary decomposition theorem. We introduce the notion of ε-orthogonality, and show that for ε-orthogonal chains, the complementary decomposition theorem may be iterated O(1/√ε) times while only giving away a constant multiplicative factor on the overall spectral gap. We show the decomposition given in [S. Miracle and A.P. Streib, 2018] of a related Markov chain ℳ_pp over k-class particle systems is 1/n²-orthogonal when the number of particles in each class is at least C log n, where C is a constant not depending on n. We then apply the complementary decomposition theorem iteratively n times to prove nearly optimal bounds on the spectral gap of ℳ_pp and to further prove the first inverse-polynomial bound on the spectral gap of ℳ_nn when k is as large as Θ(n/log n). The previous best known bound assumed k was at most a constant.

BibTeX - Entry

@InProceedings{miracle_et_al:LIPIcs:2020:12606,
  author =	{Sarah Miracle and Amanda Pascoe Streib and Noah Streib},
  title =	{{Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12606},
  URN =		{urn:nbn:de:0030-drops-126069},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.3},
  annote =	{Keywords: Markov chains, Permutations, Decomposition, Spectral Gap, Iterated Decomposition}
}

Keywords: Markov chains, Permutations, Decomposition, Spectral Gap, Iterated Decomposition
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020


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