Volume 21 (2025) Article 3 pp. 1-41
APPROX-RANDOM 2020 Special Issue

Iterated Decomposition of Biased Permutations Via New Bounds on the Spectral Gap of Markov Chains

by Sarah Miracle, Amanda Pascoe Streib, and Noah Streib

Received: April 2, 2021
Revised: January 30, 2025
Published: August 22, 2025

$ \newcommand{\cP}[0]{\mathbb{P}} \newcommand{\mn}[0]{{\mathbb{M}}_{\text{nn}}} \newcommand{\mk}[0]{{\mathbb{M}}_{\text{pp}}} $

In this paper, we address a conjecture of Fill (2003) about the spectral gap of a nearest-neighbor transposition Markov chain $\mn$ over biased permutations of $[n]$. Suppose we are given an array of input probabilities $\cP = \{p_{i,j}\}$ for all $1 \leq i, j \leq n$ with $p_{i, j} = 1-p_{j, i}$. The Markov chain $\mn$ 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 $\mn$ when the particles in $[n]$ fall into $k$ classes. There, the authors iteratively decomposed $\mn$ 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 $\mk$ 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 $\mk$ and to further prove the first inverse-polynomial bound on the spectral gap of $\mn$ 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).

DOI: 10.4086/toc.2025.v021a003

© 2025 Sarah Miracle, Amanda Pascoe Streib, and Noah Streib
Licensed under a Creative Commons Attribution License (CC-BY)