共查询到20条相似文献,搜索用时 15 毫秒
1.
Elchanan Mossel Dror Weitz Nicholas Wormald 《Probability Theory and Related Fields》2009,143(3-4):401-439
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. 相似文献
2.
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. 相似文献
3.
C. Kessler 《Probability Theory and Related Fields》1988,78(2):253-259
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 相似文献
4.
N. M. Khatamov 《Theoretical and Mathematical Physics》2014,180(3):1030-1039
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. 相似文献
5.
On Wiener-Poisson type multivalued stochastic differential equations with non-Lipschitz coefficients
Jing Wu 《数学学报(英文版)》2013,29(4):675-690
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. 相似文献
6.
Klaus Schmidt 《Israel Journal of Mathematics》1987,58(2):225-242
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 2 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]). 相似文献
7.
Felix Otto 《Journal of Functional Analysis》2007,243(1):121-157
We give a criterion for the logarithmic Sobolev inequality (LSI) on the product space X1×?×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. 相似文献
8.
Michiko Yuri 《Transactions of the American Mathematical Society》2003,355(7):2949-2971
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.
9.
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. 相似文献
10.
Yong-Hua Mao 《Journal of Mathematical Analysis and Applications》2006,315(2):415-424
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∞. 相似文献
11.
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 Zd. 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. 相似文献
12.
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 μt 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 相似文献
13.
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). 相似文献
14.
Constantinos Daskalakis Elchanan Mossel S��bastien Roch 《Probability Theory and Related Fields》2011,149(1-2):149-189
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. 相似文献
15.
《Comptes Rendus de l'Academie des Sciences Series IIA Earth and Planetary Science》1998,326(3):359-364
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 supxε, γ({x}) ≤ 1. Thus, the associated diffusion lives on the smaller space Γ. This result also holds for Gibbs measures with superstable interactions. 相似文献
16.
17.
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. 相似文献
18.
《Topology and its Applications》2004,135(1-3):131-148
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) C1 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 Gh has a loop then the flow does not have a closed manifold which is a global cross section. This property of Gh 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 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. 相似文献
19.
Martin Grothaus Yuri G. Kondratiev Michael Röckner 《Probability Theory and Related Fields》2007,137(1-2):121-160
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. 相似文献
20.
Stephan Lawi 《Journal of Theoretical Probability》2008,21(1):144-168
We give a necessary and sufficient condition for a homogeneous Markov process taking values in ℝ
n
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.
相似文献