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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12606/
Miracle, Sarah ;
Streib, Amanda Pascoe ;
Streib, Noah
Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains
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 |
