Abstract
In this paper, we address a conjecture of Fill [Fill03] about the spectral gap of a nearestneighbor 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} = 1p_{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 kclass 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 inversepolynomial 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:13:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12606},
URN = {urn:nbn:de:0030drops126069},
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 