On the hardness of sampling independent sets beyond the tree threshold

We consider local Markov chain Monte–Carlo algorithms for sampling from the weighted distribution of independent sets with activity λ, where the weight of an independent set I is λ^|I|. A recent result has established that Gibbs sampling is rapidly mixing in sampling the distribution for graphs of maximum degree d and λ < λ _c (d), where λ _c (d) is the critical activity for uniqueness of the Gibbs measure (i.e., for decay of correlations with distance in the weighted distribution over independent sets) on the d-regular infinite tree. We show that for d ≥ 3, λ just above λ _c (d) with high probability over d-regular bipartite graphs, any local Markov chain Monte–Carlo algorithm takes exponential time before getting close to the stationary distribution. Our results provide a rigorous justification for “replica” method heuristics. These heuristics were invented in theoretical physics and are used in order to derive predictions on Gibbs measures on random graphs in terms of Gibbs measures on trees. A major theoretical challenge in recent years is to provide rigorous proofs for the correctness of such predictions. Our results establish such rigorous proofs for the case of hard-core model on bipartite graphs. We conjecture that λ _c is in fact the exact threshold for this computational problem, i.e., that for λ > λ _c it is NP-hard to approximate the above weighted sum over independent sets to within a factor polynomial in the size of the graph.     

A Hard-Core Model on a Cayley Tree: An Example of a Loss Network

The paper is about a nearest-neighbor hard-core model, with fugacity λ>0, on a homogeneous Cayley tree of order k(with k+1 neighbors). This model arises as as a simple example of a loss network with a nearest-neighbor exclusion. We focus on Gibbs measures for the hard core model, in particular on ‘splitting’ Gibbs measures generating a Markov chain along each path on the tree. In this model, ?λ>0 and k≥1, there exists a unique translation-invariant splitting Gibbs measure μ^*. Define λ_c=1/(k?1)×(k/(k?1)) ^k . Then: (i) for λ≤λ_c, the Gibbs measure is unique (and coincides with the above measure μ^*), (ii) for λ>λ_c, in addition to μ^*, there exist two distinct translation-periodic measures, μ₊and μ_?, taken to each other by the unit space shift. Measures μ₊and μ_?are extreme ?λ>λ_c. We also construct a continuum of distinct, extreme, non-translational-invariant, splitting Gibbs measures. For $\lambda >1/(\sqrt k - 1) \times (\sqrt k /\sqrt k - 1))^k $ , measure μ^*is not extreme (this result can be improved). Finally, we consider a model with two fugacities, λ_eand λ_o, for even and odd sites. We discuss open problems and state several related conjectures.     

Markov type properties for mixtures of probability measures

Summary We show that, given a general Markov type property M, and a finite dimensional set of probability measures , the set of elements of having M can be described by finitely many quadratic equations. We apply the result to the problem of the global Markov property for nonextremal Gibbs states.This work was prepared during the author's stay at the University of Hull, England, and supported by the Science and Engineering Research Council of Great Britatin     

Nonuniqueness of a Gibbs measure for the Ising ball model

We study a new model, the so-called Ising ball model on a Cayley tree of order k ≥ 2. We show that there exists a critical activity \(\lambda _{cr} = \sqrt[4]{{0.064}}\) such that at least one translation-invariant Gibbs measure exists for λ ≥ λ _cr , at least three translation-invariant Gibbs measures exist for 0 < λ < λ _cr , and for some λ, there are five translation-invariant Gibbs measures and a continuum of Gibbs measures that are not translation invariant. For any normal divisor \(\hat G\) of index 2 of the group representation on the Cayley tree, we study \(\hat G\) -periodic Gibbs measures. We prove that there exists an uncountable set of \(\hat G\) -periodic (not translation invariant and “checkerboard” periodic) Gibbs measures.     

On Wiener-Poisson type multivalued stochastic differential equations with non-Lipschitz coefficients

In this paper, we prove local uniqueness for multivalued stochastic differential equations with Poisson jumps. Then existence and uniqueness of global solutions is obtained under the conditions that the coefficients satisfy locally Lipschitz continuity and one-sided linear growth of b. Moreover, we also prove the Markov property of the solution and the existence of invariant measures for the corresponding transition semigroup.     

Hyperbolic structure preserving isomorphisms of Markov shifts. II

This paper is a continuation of [14] and deals with metric isomorphisms of Markov shifts which are finitary and hyperbolic structure preserving. We prove that theβ-function introduced by S. Tuncel in [15] is an invariant of such isomorphisms. Following [5] this result is extended to Gibbs measures arising from functions with summable variation. Finally we prove that, for anyC ² Axiom A diffeomorphism on a basic set Ω, and for any equilibrium state associated with a Hölder continuous function on Ω, the Markov shifts arising from different Markov partitions of Ω are isomorphic via a finitary, hyperbolic structure preserving isomorphism. This fact leads to a rich class of examples of such isomorphisms (other examples are provided by finitary isomorphisms of Markov shifts with finite expected code lengths — cf. [14]).     

A new criterion for the logarithmic Sobolev inequality and two applications

We give a criterion for the logarithmic Sobolev inequality (LSI) on the product space X₁×?×XN. We have in mind an N-site lattice, unbounded continuous spin variables, and Glauber dynamics. The interactions are described by the Hamiltonian H of the Gibbs measure. The criterion for LSI is formulated in terms of the LSI constants of the single-site conditional measures and the size of the off-diagonal entries of the Hessian of H. It is optimal for Gaussians with positive covariance matrix. To illustrate, we give two applications: one with weak interactions and one with strong interactions and a decay of correlations condition.     

Thermodynamic formalism for countable to one Markov systems

For countable to one transitive Markov systems we establish thermodynamic formalism for non-Hölder potentials in nonhyperbolic situations. We present a new method for the construction of conformal measures that satisfy the weak Gibbs property for potentials of weak bounded variation and show the existence of equilibrium states equivalent to the weak Gibbs measures. We see that certain periodic orbits cause a phase transition, non-Gibbsianness and force the decay of correlations to be slow. We apply our results to higher-dimensional maps with indifferent periodic points.

     

Decay parameter and related properties of n-type branching processes

We consider decay properties including the decay parameter, invariant measures, invariant vectors, and quasistationary distributions for n-type Markov branching processes on the basis of the 1-type Markov branching processes and 2-type Markov branching processes. Investigating such behavior is crucial in realizing life period of branching models. In this paper, some important properties of the generating functions for n-type Markov branching q-matrix are firstly investigated in detail. The exact value of the decay parameter λC of such model is given for the communicating class C = Zn+ \ 0. It is shown that this λC can be directly obtained from the generating functions of the corresponding q-matrix. Moreover, the λC -invariant measures/vectors and quasi-distributions of such processes are deeply considered. λC -invariant measures and quasi-stationary distributions for the process on C are presented.     

Eigentime identity for transient Markov chains

An eigentime identity is proved for transient symmetrizable Markov chains. For general Markov chains, if the trace of Green matrix is finite, then the expectation of first leap time is uniformly bounded, both of which are proved to be equivalent for single birth processes. For birth-death processes, the explicit formulas are presented. As an application, we give the bounds of exponential convergence rates of (sub-) Markov semigroup Pt from l_∞ to l_∞.     

Markov random fields,Markov cocycles and the 3-colored chessboard

The well-known Hammersley–Clifford Theorem states (under certain conditions) that any Markov random field is a Gibbs state for a nearest neighbor interaction. In this paper we study Markov random fields for which the proof of the Hammersley–Clifford Theorem does not apply. Following Petersen and Schmidt we utilize the formalism of cocycles for the homoclinic equivalence relation and introduce “Markov cocycles”, reparametrizations of Markov specifications. The main part of this paper exploits this to deduce the conclusion of the Hammersley–Clifford Theorem for a family of Markov random fields which are outside the theorem’s purview where the underlying graph is Z_d. This family includes all Markov random fields whose support is the d-dimensional “3-colored chessboard”. On the other extreme, we construct a family of shift-invariant Markov random fields which are not given by any finite range shift-invariant interaction.     

Loss without recovery of Gibbsianness during diffusion of continuous spins

We consider a specific continuous-spin Gibbs distribution μ_t=0 for a double-well potential that allows for ferromagnetic ordering. We study the time-evolution of this initial measure under independent diffusions. For `high temperature' initial measures we prove that the time-evoved measure μ<sub>t</sub> is Gibbsian for all t. For `low temperature' initial measures we prove that μ_t stays Gibbsian for small enough times t, but loses its Gibbsian character for large enough t. In contrast to the analogous situation for discrete-spin Gibbs measures, there is no recovery of the Gibbs property for large t in the presence of a non-vanishing external magnetic field. All of our results hold for any dimension d≥2. This example suggests more generally that time-evolved continuous-spin models tend to be non-Gibbsian more easily than their discrete-spin counterparts. Research carried out at EURANDOM and supported by Deutsche Forschungsgemeinschaft     

Construction of a set of <Emphasis Type="Italic">p</Emphasis>-adic distributions

Adapting some methods for real-valued Gibbs measures on Cayley trees to the p-adic case, we construct several p-adic distributions on the set ?_p of p-adic integers. In addition, we give conditions under which these p-adic distributions become p-adic measures (i.e., bounded distributions).     

Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

A support property for infinite-dimensional interacting diffusion processes

The Dirichlet form associated with the intrinsic gradient on Poisson space is known to be quasi-regular on the complete metric space Γ = {ℤ₊-valued Radon measures on ℝ^d}. We show that under mild conditions, the set Γ\Γ is ɛ-exceptional, where Γ is the space of locally finite configurations in ℝ^d, that is, measures γ ε Γ satisfying sup_xε, γ({x}) ≤ 1. Thus, the associated diffusion lives on the smaller space Γ. This result also holds for Gibbs measures with superstable interactions.     

Coarse-grained entropy in dynamical systems

Let M be the phase space of a physical system. Consider the dynamics, determined by the invertible map T: M → M, preserving the measure µ on M. Let ν be another measure on M, dν = ρdµ. Gibbs introduced the quantity s(ρ) = ?∝ρ log ρdµ as an analog of the thermodynamical entropy. We consider a modification of the Gibbs (fine-grained) entropy the so called coarse-grained entropy. First we obtain a formula for the difference between the coarse-grained and Gibbs entropy. The main term of the difference is expressed by a functional usually referenced to as the Fisher information. Then we consider the behavior of the coarse-grained entropy as a function of time. The dynamics transforms ν in the following way: ν → ν _n , dν _n = ρ ○ T ^?n dµ. Hence, we obtain the sequence of densities ρ _n = ρ ○ T ^?n and the corresponding values of the Gibbs and the coarse-grained entropy. We show that while the Gibbs entropy remains constant, the coarse-grained entropy has a tendency to a growth and this growth is determined by dynamical properties of the map T. Finally, we give numerical calculation of the coarse-grained entropy as a function of time for systems with various dynamical properties: integrable, chaotic and with mixed dynamics and compare these calculation with theoretical statements.     

Every nonsingular C1 flow on a closed manifold of dimension greater than two has a global transverse disk

We prove three results about global cross sections which are disks, henceforth called global transverse disks. First we prove that every nonsingular (fixed point free) C¹ flow on a closed (compact, no boundary) connected manifold of dimension greater than 2 has a global transverse disk. Next we prove that for any such flow, if the directed graph G_h has a loop then the flow does not have a closed manifold which is a global cross section. This property of G_h is easy to read off from the first return map for the global transverse disk. Lastly, we give criteria for an “M-cellwise continuous” (a special case of piecewise continuous) map $\text{h}\text{:D}{}^2\text{→D}{}^2$ that determines whether h is the first return map for some global transverse disk of some flow ϕ. In such a case, we call ϕ the suspension of h.     

N/V-limit for stochastic dynamics in continuous particle systems

We provide an N/V-limit for the infinite particle, infinite volume stochastic dynamics associated with Gibbs states in continuous particle systems on ℝ ^d ,d≥1. Starting point is an N-particle stochastic dynamic with singular interaction and reflecting boundary condition in a subset Λ⊂ℝ ^d with finite volume (Lebesgue measure) V=|Λ|<∞. The aim is to approximate the infinite particle, infinite volume stochastic dynamic by the above N-particle dynamic in Λ as N→∞ and V→∞ such that N/V→ρ, where ρ is the particle density. First we derive an improved Ruelle bound for the canonical correlation functions under an appropriate relation between N and V. Then tightness is shown by using the Lyons–Zheng decomposition. The equilibrium measures of the accumulation points are identified as infinite volume canonical Gibbs measures by an integration by parts formula and the accumulation points themselves are identified as infinite particle, infinite volume stochastic dynamics via the associated martingale problem. Assuming a property closely related to Markov uniqueness and weaker than essential self-adjointness, via Mosco convergence techniques we can identify the accumulation points as Markov processes and show uniqueness. I.e., all accumulation corresponding to one invariant canonical Gibbs measure coincide. The proofs work for general repulsive interaction potentials ϕ of Ruelle type and all temperatures, densities, and dimensions d≥1, respectively. ϕ may have a nontrivial negative part and infinite range as e.g. the Lennard–Jones potential. Additionally, our result provides as a by-product an approximation of grand canonical Gibbs measures by finite volume canonical Gibbs measures with empty boundary condition.     

Towards a Characterization of Markov Processes Enjoying the Time-Inversion Property

We give a necessary and sufficient condition for a homogeneous Markov process taking values in ℝ ⁿ to enjoy the time-inversion property of degree α. The condition sets the shape for the semigroup densities of the process and allows to further extend the class of known processes satisfying the time-inversion property. As an application we recover the result of Watanabe (Z. Wahrscheinlichkeitstheor. Verwandte Geb. 31:115–124, 1975) for continuous and conservative Markov processes on ℝ₊. As new examples we generalize Dunkl processes and construct a matrix-valued process with jumps related to the Wishart process by a skew-product representation.