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 <= i,j <= 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 & varepsilon;-orthogonality, and show that for & varepsilon;-orthogonal chains, the complementary decomposition theorem may be iterated O(1/root & varepsilon;) 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 & varepsilon;-orthogonal for some & varepsilon;<= 1/n(2) as long as the number of particles in each class is at least Clogn, 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/logn). The previous best known bound assumed k was bounded.