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.

We study rectangular dissections of an $n \times n$ lattice region into rectangles of area $n$, where $n=2^k$ for an even integer $k$. We show there is a natural edge-flipping Markov chain that connects the state space. A similar edge-flipping chain is known to connect the state space when restricted to dyadic tilings, where each rectangle is required to have the form $R = [s2^{u},(s+1)2^{u}]\times [t2^{v}, (t+1)2^{v}],$ where $s, t, u$, and $v$ are nonnegative integers. The mixing time of this Markov chain for general rectangular dissections remains open, while recent work by Cannon, Levin, and Stauffer [ Proceedings of APPROX/RANDOM 2017, pp. 34:1--34:21] gave a polynomial upper bound on the mixing time when restricting to dyadic tilings. We consider a weighted version of these Markov chains where, given a parameter $\lambda > 0,$ we would like to generate each rectangular dissection (or dyadic tiling) $\sigma$ with probability proportional to $\lambda^{|\sigma|},$ where $|\sigma|$ is the total edge length. We show there is a phase transition in the dyadic setting: when $\lambda < 1,$ the edge-flipping chain mixes in time $O(n^2)$, and when $\lambda > 1,$ the mixing time is $\exp(\Omega({n^2}))$. The behavior for general rectangular dissections is more subtle, and even establishing ergodicity of the chain requires a careful inductive argument. As in the dyadic case, we show that the edge-flipping Markov chain for rectangular dissections requires exponential time when $\lambda > 1$. Surprisingly, the chain also requires exponential time when $\lambda < 1$, which we show using a different argument. Simulations suggest that the chain converges quickly at the isolated point $\lambda =1$, but this case remains open.

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 rectangular dissections of an n × n lattice region into rectangles of area n, where n = 2k for an even integer k. We show that there is a natural edge-flipping Markov chain that connects the state space. A similar edge-flipping chain is also known to connect the state space when restricted to dyadic tilings, where each rectangle is required to have the form R = [s2u, (s + 1)2u] × [t2v, (t+1)2v], where s, t, u and v are nonnegative integers. The mixing time of these chains is open. We consider a weighted version of these Markov chains where, given a parameter λ > 0, we would like to generate each rectangular dissection (or dyadic tiling) σ with probability proportional to λ|σ|, where |σ| is the total edge length. We show there is a phase transition in the dyadic setting: when λ < 1, the edge-flipping chain mixes in time O(n2 log n), and when λ > 1, the mixing time is exp(Ω(n2)). Simulations suggest that the chain converges quickly when λ = 1, but this case remains open. The behavior for general rectangular dissections is more subtle, and even establishing ergodicity of the chain requires a careful inductive argument. As in the dyadic case, we show that the edge-flipping Markov chain for rectangular dissections requires exponential time when λ > 1. Surprisingly, the chain also requires exponential time when λ < 1, which we show using a different argument. Simulations suggest that the chain converges quickly at the isolated point λ = 1.

The Schelling segregation model attempts to explain possible causes of racial segregation in cities. Schelling considered residents of two types, where everyone prefers that the majority of his or her neighbors are of the same type. He showed through simulations that even mild preferences of this type can lead to segregation if residents move whenever they are not happy with their local environments. We generalize the Schelling model to include a broad class of bias functions determining individuals happiness or desire to move, called the General Influence Model. We show that for any influence function in this class, the dynamics will be rapidly mixing and cities will be integrated (i.e., there will not be clustering) if the racial bias is sufficiently low. Next we show complementary results for two broad classes of influence functions: Increasing Bias Functions (IBF), where an individual's likelihood of moving increases each time someone of the same color leaves (this does not include Schelling's threshold models), and Threshold Bias Functions (TBF) with the threshold exceeding one half, reminiscent of the model Schelling originally proposed. For both classes (IBF and TBF), we show that when the bias is sufficiently high, the dynamics take exponential time to mix and we will have segregation and a large “ghetto” will form.

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.