Theory of Computing
-------------------
Title     : Iterated Decomposition of Biased Permutations Via New Bounds on the Spectral Gap of Markov Chains
Authors   : Sarah Miracle, Amanda Pascoe Streib, and Noah Streib
Volume    : 21
Number    : 3
Pages     : 1-41
URL       : https://theoryofcomputing.org/articles/v021a003

Abstract
--------

In this paper, we address a conjecture of Fill (2003) about the
spectral gap of a nearest-neighbor transposition Markov chain $M_{nn}$
over biased permutations of $[n]$. Suppose we are given an array of input
probabilities $P = (p_{i,j})$ for all $1 \leq i, j \leq n$ with
$p_{i,j} = 1-p_{j,i}$. The Markov chain $M_{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 of Miracle and Streib (LATIN'18 and _SIAM J.
Discr. Math._ , 2024) that analyzed the spectral gap of $M_{nn}$ when
the particles in $[n]$ fall into $k$ classes. There, the authors
iteratively decomposed $M_{nn}$ into simpler chains, but incurred a
multiplicative penalty of $n^{-2}$ for each application of the
decomposition theorem of Martin and Randall (FOCS '00), 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 $\epsilon$-orthogonality, and show that for
$\epsilon$-orthogonal chains, the complementary decomposition theorem
may be iterated $O(1/\sqrt{\epsilon})$ times while only giving away a
constant multiplicative factor on the overall spectral gap. We show
that the decomposition given by Miracle and Streib ( _op. cit._ ) of
a related Markov chain $M_{pp}$ over $k$-class particle systems is
$\epsilon$-orthogonal for some $\epsilon\leq 1/n^2$ as long as 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 $M_{pp}$ and to further prove the first
inverse-polynomial bound on the spectral gap of $M_{nn}$ when $k$ is as
large as $\Theta(n/\log n)$. The previous best known bound assumed $k$
was bounded.

-------------

A preliminary version of this paper appeared in the Proceedings of the 
24th International Conference on Randomization and Computation (RANDOM'20).