An official website of the United States government
Abstract Monotonic surfaces spanning finite regions of ℤ d arise in many contexts, including DNA-based self-assembly, card-shuffling 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
Mixing times of Markov chains for self‐organizing lists and biased permutations
Abstract 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
- PAR ID:
- 10444429
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 61
- Issue:
- 4
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 638-665
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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 asvariance mixingandentropy mixingimply 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 forallboundary 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.more » « less
-
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.more » « less
-
Megow, Nicole; Smith, Adam (Ed.)We study the mixing time of the single-site update Markov chain, known as the Glauber dynamics, for generating a random independent set of a tree. Our focus is obtaining optimal convergence results for arbitrary trees. We consider the more general problem of sampling from the Gibbs distribution in the hard-core model where independent sets are weighted by a parameter λ > 0; the special case λ = 1 corresponds to the uniform distribution over all independent sets. Previous work of Martinelli, Sinclair and Weitz (2004) obtained optimal mixing time bounds for the complete Δ-regular tree for all λ. However, Restrepo et al. (2014) showed that for sufficiently large λ there are bounded-degree trees where optimal mixing does not hold. Recent work of Eppstein and Frishberg (2022) proved a polynomial mixing time bound for the Glauber dynamics for arbitrary trees, and more generally for graphs of bounded tree-width. We establish an optimal bound on the relaxation time (i.e., inverse spectral gap) of O(n) for the Glauber dynamics for unweighted independent sets on arbitrary trees. Moreover, for λ ≤ .44 we prove an optimal mixing time bound of O(n log n). We stress that our results hold for arbitrary trees and there is no dependence on the maximum degree Δ. Interestingly, our results extend (far) beyond the uniqueness threshold which is on the order λ = O(1/Δ). Our proof approach is inspired by recent work on spectral independence. In fact, we prove that spectral independence holds with a constant independent of the maximum degree for any tree, but this does not imply mixing for general trees as the optimal mixing results of Chen, Liu, and Vigoda (2021) only apply for bounded degree graphs. We instead utilize the combinatorial nature of independent sets to directly prove approximate tensorization of variance/entropy via a non-trivial inductive proof.more » « less
-
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
