We study the mixing time of a Markov chain on biased permutations, a problem related to self‐organizing lists. We are given probabilities for all such that . The chain iteratively chooses two adjacent elements and , and swaps them with probability . It has been conjectured that is rapidly mixing whenever the set of probabilities are “positively biased,” that is, for all . We define two general classes and give the first proofs that is rapidly mixing for both. We also demonstrate that the chain can have exponential mixing time, disproving the most general version of this conjecture.
more » « less Award ID(s):
 1733812
 NSFPAR ID:
 10444429
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Random Structures & Algorithms
 Volume:
 61
 Issue:
 4
 ISSN:
 10429832
 Page Range / eLocation ID:
 p. 638665
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract Monotonic surfaces spanning finite regions of ℤ d arise in many contexts, including DNAbased selfassembly, cardshuffling and lozenge tilings. One method that has been used to uniformly generate these surfaces is a Markov chain that iteratively adds or removes a single cube below the surface during a step. We consider a biased version of the chain, where we are more likely to add a cube than to remove it, thereby favouring surfaces that are ‘higher’ or have more cubes below it. We prove that the chain is rapidly mixing for any uniform bias in ℤ 2 and for bias λ > d in ℤ d when d > 2. In ℤ 2 we match the optimal mixing time achieved by Benjamini, Berger, Hoffman and Mossel in the context of biased card shuffling [2], but using much simpler arguments. The proofs use a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias , where the bias can vary depending on the location of the tile. We show that the chain continues to be rapidly mixing if the biases are close to uniform, but that the chain can converge exponentially slowly in the general setting.more » « less

Abstract The Swendsen–Wang algorithm is a sophisticated, widely‐used Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain has proved difficult to analyze, due in part to its global nature. We present optimal bounds on the convergence rate of the Swendsen–Wang algorithm for the complete ‐ary tree. Our bounds extend to the non‐uniqueness region and apply to all boundary conditions. We show that the spatial mixing conditions known as
variance mixing andentropy mixing imply spectral gap and mixing time, respectively, for the Swendsen–Wang dynamics on the ‐ary tree. We also show that these bounds are asymptotically optimal. As a consequence, we establish mixing for the Swendsen–Wang dynamics forall boundary conditions throughout (and beyond) the tree uniqueness region. Our proofs feature a novel spectral view of the variance mixing condition and utilize recent work on block factorization of entropy. 
Abstract Consider a lattice of n sites arranged around a ring, with the $n$ sites occupied by particles of weights $\{1,2,\ldots ,n\}$; the possible arrangements of particles in sites thus correspond to the $n!$ permutations in $S_n$. The inhomogeneous totally asymmetric simple exclusion process (or TASEP) is a Markov chain on $S_n$, in which two adjacent particles of weights $i<j$ swap places at rate $x_i  y_{n+1j}$ if the particle of weight $j$ is to the right of the particle of weight $i$. (Otherwise, nothing happens.) When $y_i=0$ for all $i$, the stationary distribution was conjecturally linked to Schubert polynomials [18], and explicit formulas for steady state probabilities were subsequently given in terms of multiline queues [4, 5]. In the case of general $y_i$, Cantini [7] showed that $n$ of the $n!$ states have probabilities proportional to double Schubert polynomials. In this paper, we introduce the class of evilavoiding permutations, which are the permutations avoiding the patterns $2413, 4132, 4213,$ and $3214$. We show that there are $\frac {(2+\sqrt {2})^{n1}+(2\sqrt {2})^{n1}}{2}$ evilavoiding permutations in $S_n$, and for each evilavoiding permutation $w$, we give an explicit formula for the steady state probability $\psi _w$ as a product of double Schubert polynomials. (Conjecturally, all other probabilities are proportional to a positive sum of at least two Schubert polynomials.) When $y_i=0$ for all $i$, we give multiline queue formulas for the $\textbf {z}$deformed steady state probabilities and use this to prove the monomial factor conjecture from [18]. Finally, we show that the Schubert polynomials arising in our formulas are flagged Schur functions, and we give a bijection in this case between multiline queues and semistandard Young tableaux.

Efficient algorithms for approximate counting and sampling in spin systems typically apply in the so‐called high‐temperature regime, where the interaction between neighboring spins is “weak.” Instead, recent work of Jenssen, Keevash, and Perkins yields polynomial‐time algorithms in the low‐temperature regime on bounded‐degree (bipartite) expander graphs using polymer models and the cluster expansion. In order to speed up these algorithms (so the exponent in the run time does not depend on the degree bound) we present a Markov chain for polymer models and show that it is rapidly mixing under exponential decay of polymer weights. This yields, for example, an
‐time sampling algorithm for the low‐temperature ferromagnetic Potts model on bounded‐degree expander graphs. Combining our results for the hard‐core and Potts models with Markov chain comparison tools, we obtain polynomial mixing time for Glauber dynamics restricted to appropriate portions of the state space. 
We provide a general framework for computing mixing times of finite Markov chains when its minimal ideal is left zero. Our analysis is based on combining results by Brown and Diaconis with our previous work on stationary distributions of finite Markov chains. We introduce a new Markov chain on linear extensions of a poset with n vertices, which is a variant of the promotion Markov chain of Ayyer, Klee and the last author, and show that it has a mixing time O(n log n).more » « less