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
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
- NSF-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
-
-
more » « less
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+1-j}$ 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 evil-avoiding permutations, which are the permutations avoiding the patterns $2413, 4132, 4213,$ and $3214$. We show that there are $\frac {(2+\sqrt {2})^{n-1}+(2-\sqrt {2})^{n-1}}{2}$ evil-avoiding permutations in $S_n$, and for each evil-avoiding 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.
-
more » « less
The Swendsen‐Wang (SW) dynamics is a popular Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph
G = (V ,E ). The dynamics is conjectured to converge to equilibrium inO (|V |1/4) steps at any (inverse) temperatureβ , yet there are few results providingo (|V |) upper bounds. We prove fast convergence of the SW dynamics on general graphs in the tree uniqueness region. In particular, whenβ <β c (d ) whereβ c (d ) denotes the uniqueness/nonuniqueness threshold on infinited ‐regular trees, we prove that therelaxation time (i.e., the inverse spectral gap) of the SW dynamics is Θ(1) on any graph of maximum degreed ≥ 3. Our proof utilizes amonotone version of the SW dynamics which only updates isolated vertices. We establish that this variant of the SW dynamics has mixing timeand relaxation time Θ(1) on any graph of maximum degree d for allβ <β c (d ). Our proof technology can be applied to general monotone Markov chains, including for example theheat‐bath block dynamics , for which we obtain new tight mixing time bounds. -
more » « less
Abstract Introgression might be exceptionally common during the evolution of narrowly endemic species. For instance, in the springs of the small and isolated
C uatroC iénegasV alley, the mitogenome of the cichlid fishH erichthys cyanoguttatusH . minckleyiSNP s) from the nuclear genome showed that mitochondrial introgression intoH . minckleyiSNP assignment probabilities also indicated that cichlids with more hybrid ancestry are not more commonly female providing no support for asymmetric backcrossing or hybrid‐induced sex‐ratio distortion in generating the bias in mitochondrial introgression. Smaller effective population size inH . minckleyiSNP s coupled with sequences of all 13 mitochondrial proteins suggests that relaxed selection on the mitogenome could be facilitating the introgression of “H. cyanoguttatus ” haplotypes. Additionally, we showed that springs with colder temperatures had greater amounts of mitochondrial introgression fromH. cyanoguttatus . Relaxed selection inH. minckleyi coupled with temperature‐related molecular adaptation could be facilitating mitogenomic introgression intoH. minckleyi . -
more » « less
Abstract We study the performance of Markov chains for the
q -state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis and, in fact, even analysing the properties of the Potts distribution has remained elusive. It is conjectured that the performance of Markov chains is dictated by metastability phenomena, i.e., the presence of “phases” (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape, and therefore cause slow mixing. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task. Our first contribution is to detail the emergence of the two relevant phases for theq -state Potts model on thed -regular random graph for all integers$$q,d\ge 3$$ d -regular tree, the two phases coexist (as possible metastable states). The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. This significantly refines earlier results by Helmuth, Jenssen, and Perkins who had established phase coexistence for a small interval around the so-called ordered-disordered threshold (via different arguments) that applied for largeq and$$d\ge 5$$
