1 Search Results for "Streib, Amanda Pascoe"

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.3

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

Authors: Sarah Miracle, Amanda Pascoe Streib, and Noah Streib

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

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.

Cite as

Sarah Miracle, Amanda Pascoe Streib, and Noah Streib. Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{miracle_et_al:LIPIcs.APPROX/RANDOM.2020.3,
  author =	{Miracle, Sarah and Streib, Amanda Pascoe and Streib, Noah},
  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 =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.3},
  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}
}

Refine by Author
1 Miracle, Sarah
1 Streib, Amanda Pascoe
1 Streib, Noah

Refine by Classification
1 Theory of computation → Random walks and Markov chains

Refine by Keyword
1 Decomposition
1 Iterated Decomposition
1 Markov chains
1 Permutations
1 Spectral Gap

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Streib, Amanda Pascoe"

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

Abstract

Cite as

Thanks for your feedback!

Could not send message