Abstract. In this paper, we study a biased version of the nearest-neighbor transposition Markov chain on the set of permutations where neighboring elements [Formula: see text] and [Formula: see text] are placed in order [Formula: see text] with probability [Formula: see text]. Our goal is to identify the class of parameter sets [Formula: see text] for which this Markov chain is rapidly mixing. Specifically, we consider the open conjecture of Jim Fill [ Background on the Gap Problem (2003) and An Interesting Spectral Gap Problem (2003)] that all monotone, positively biased distributions are rapidly mixing. We resolve Fill’s conjecture in the affirmative for distributions arising from [Formula: see text]-class particle processes, where the elements are divided into [Formula: see text] classes and the probability of exchanging neighboring elements depends on the particular classes the elements are in. We further require that [Formula: see text] is a constant and that all probabilities between elements in different classes are bounded away from [Formula: see text]. These particle processes arise in the context of self-organizing lists, and our result also applies beyond permutations to the setting where all particles in a class are indistinguishable. Our work generalizes recent work by Haddadan and Winkler [ Mixing of permutations by biased transposition (2017)] studying 3-class particle processes. Additionally, we show that a broader class of distributions based on trees is also rapidly mixing, which generalizes a class analyzed by Bhakta et al. [ Mixing times of Markov chains for self-organizing lists and biased permutations (2013)]. Our proof involves analyzing a generalized biased exclusion process, which is a nearest-neighbor transposition chain applied to a 2-particle system. Biased exclusion processes are of independent interest, with applications in self-assembly. We generalize the results of Greenberg et al. [ Sampling biased lattice configurations using exponential metrics (2009)] and Benjamini et al. [ Mixing times of the biased card shuffling and the asymmetric exclusion process (2005)] on biased exclusion processes to allow the probability of swapping neighboring elements to depend on the entire system, as long as the minimum bias is bounded away from 1.

In this paper, we address a conjecture of Fill [Fill03] about the spectral gap of a nearest-neighbor 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} = 1-p_{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 k-class 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 inverse-polynomial 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.

Given a planar triangulation, a 3-orientation is an orientation of the internal edges so all internal vertices have out-degree three. Each 3-orientation gives rise to a unique edge coloring known as a Schnyder wood that has proven powerful for various computing and combinatorics applications. We consider natural Markov chains for sampling uniformly from the set of 3-orientations. First, we study a “triangle-reversing” chain on the space of 3-orientations of a fixed triangulation that reverses the orientation of the edges around a triangle in each move. We show that, when restricted to planar triangulations of maximum degree six, this Markov chain is rapidly mixing and we can approximately count 3-orientations. Next, we construct a triangulation with high degree on which this Markov chain mixes slowly. Finally, we consider an “edge-flipping” chain on the larger state space consisting of 3-orientations of all planar triangulations on a fixed number of vertices. We prove that this chain is always rapidly mixing.

We study the mixing time of a Markov chain Mnn on permutations that performs nearest neighbor transpositions in the non-uniform setting, a problem arising in the context of self-organizing lists. We are given “positively biased” probabilities {pij ≥ 1/2} for all i < j and let pj,i = 1 − pj,i. In each step, the chain Mnn chooses two adjacent elements k, and ℓ and exchanges their positions with probability pℓ,k. Here we define two general classes and give the first proofs that the chain is rapidly mixing for both. In the first case we are given constants r1, … rn−1 with 1/2 ≤ ri ≤ 1 for all i and we set pi,j = ri for all i < j. In the second we are given a binary tree with n leaves labeled 1, … n and constants q1, … qn−1 associated with all of the internal vertices, and we let pi,j = qi⁁j for all i < j. Our bounds on the mixing time of Mnn rely on bijections between permutations, inversion tables and asymmetric simple exclusion processes (ASEPs) that allow us to express moves of the chain in the context of these other combinatorial families. We also demonstrate that the chain is not always rapidly mixing by constructing an example requiring exponential time to converge to equilibrium. This proof relies on a reduction to biased lattice paths in ℤ2.

Monotonic surfaces spanning finite regions of ℤd arise in many contexts, including DNA-based self-assembly, card-shuffling and lozenge tilings. We explore how we can sample these surfaces when the distribution is biased to favor higher surfaces. We show that a natural local chain is rapidly mixing with any bias for regions in ℤ2, and for bias λ > d2 in ℤd, when d > 2. Moreover, our bounds on the mixing time are optimal on d-dimensional hyper-cubic regions. The proof uses a geometric distance function and introduces a variant of path coupling in order to handle distances that are exponentially large.