Summary: In this paper, we address a conjecture by J. Fill [An interesting spectral gap problem. Unpublished manuscript (2003)] about the spectral gap of a nearest-neighbor transposition Markov chain \(\mathcal{M}_{nn}\) over biased permutations of \([n]\). Suppose we are given a set of input probabilities \(\mathcal{P}=\{p_{i,j}\}\) for all \(1=i\), \(j=n\) with \(p_{i,j}= 1-p_{j,i}\). The Markov chain \(\mathcal{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 [S. Miracle and A. P. Streib, Lect. Notes Comput. Sci. 10807, 820–834 (2018; Zbl 1505.60069)] that analyzed the spectral gap of \(\mathcal{M}_{nn}\) when the particles in \([n]\) fall into \(k\) classes. There, the authors iteratively decomposed \(\mathcal{M}_{nn}\) into simpler chains, but incurred a multiplicative penalty of \(n^{-2}\) for each application of the decomposition theorem by R. Martin and D. Randall [in: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, 492–502 (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 \(\varepsilon\)-orthogonality, and show that for \(\varepsilon\)-orthogonal chains, the complementary decomposition theorem may be iterated \(O(1/\sqrt{\varepsilon})\) times while only giving away a constant multiplicative factor on the overall spectral gap. We show the decomposition given by Miracle and Streib [loc. cit.] of a related Markov chain \(\mathcal{M}_{pp}\) over \(k\)-class particle systems is \(1/n^2\)-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 \(\mathcal{M}_{pp}\) and to further prove the first inverse-polynomial bound on the spectral gap of \(\mathcal{M}_{nn}\) when \(k\) is as large as \(\Theta(n/\log n)\). The previous best known bound assumed \(k\) was at most a constant.
For the entire collection see [Zbl 1445.68009].