Ising models on locally tree-like graphs

Introduction

A ferromagnetic Ising model on the finite graph $G$ (with vertex set $V$, and edge set $E$) is defined by the following Boltzmann distributions over $\underline{x}=\{x_{i}\colon\;i\in V\}$, with $x_{i}\in\{+1,-1\}$:

These distributions are parametrized by the “magnetic field” $B$ and “inverse temperature” $\beta\geq 0$, where the partition function $Z(\beta,B)$ is fixed by the normalization condition $\sum_{\underline{x}}\mu(\underline{x})=1$. Throughout the paper, we will be interested in sequences of graphs We adopt the notation $[i]=\{1,2,\dots,i\}$ for the set of first $i$ integers. $G_{n}=(V_{n}\equiv[n],E_{n})$ of diverging size $n$.

Nonrigorous statistical mechanics techniques, such as the “replica” and “cavity methods,” allow to make a number of predictions on the model (1), when the graph $G$ “lacks any finite-dimensional structure.” The most basic quantity in this context is the asymptotic free entropy density

(this quantity is also sometimes called in the literature also free energy or pressure). The limit free entropy density and the large deviation properties of Boltzmann distribution were characterized in great detail NewmanEllis in the case of a complete graph $G_{n}=K_{n}$ (the inverse temperature must then be scaled by $1/n$ to get a nontrivial limit). Statistical physics predictions exist, however, for a much wider class of graphs, including most notably sparse random graphs with bounded average degree; see, for instance, Dorogotsev; Johnston; Vespignani. This is a direction of interest for at least two reasons:

Sparse graphical structures arise in a number of problems from combinatorics and theoretical computer science. Examples include random satisfiability, coloring of random graphs and graph partitioning MezardMontanari. In all of these cases, the uniform measure over solutions can be regarded as the Boltzmann distribution for a modified spin glass with multispin interactions. Such problems have been successfully attacked using nonrigorous statistical mechanics techniques.

A mathematical foundation of this approach is still lacking, and would be extremely useful.

Sparse graphs allow to introduce a nontrivial notion of distance between vertices, namely the length of the shortest path connecting them. This geometrical structure allows for new characterizations of the measure (1) in terms of correlation decay. This type of characterization is in turn related to the theory of Gibbs measures on infinite trees KMRSZ.

The asymptotic free entropy density (2) was determined rigorously only in a few cases for sparse graphs. In GerschenMon1, this task was accomplished for random regular graphs. De Sanctis and Guerra deSantisGuerra developed interpolation techniques for random graphs with independent edges (Erdös–Renyi type) but only determined the free entropy density at high temperature and at zero temperature (in both cases with vanishing magnetic field). The latter is in fact equivalent to counting the number of connected components of a random graph. Interestingly, the partition function $Z_{n}(\beta,B)$ can be approximated in polynomial time for $\beta\geq 0$, using an appropriate Markov chain Monte Carlo algorithm JerrumSinclair. It is intriguing that no general approximation algorithms exists in the case $\beta<0$ (the “antiferromagnetic” Ising model). Correspondingly, the statistical physics conjecture for the free entropy density MezardMontanari becomes significantly more intricate (presenting the so-called “replica symmetry breaking” phenomenon).

In this paper we generalize the previous results by rigorously verifying the validity of the Bethe free entropy prediction for the value of the limit in (2) for generic graph sequences that converge locally to trees. Indeed, we control the free entropy density by proving that the Boltzmann measure (1) converges locally to the Boltzmann measure of a model on a tree. The philosophy is related to the local weak convergence method of Aldous.

Finally, several of the proofs have an algorithmic interpretation, providing an efficient procedure for approximating the local marginals of the Boltzmann measure. The essence of this procedure consists in solving by iteration certain mean field (cavity) equations. Such an algorithm is known in artificial intelligence and computer science under the name of belief propagation. Despite its success and wide applicability, only weak performance guarantees have been proved so far. Typically, it is possible to prove its correctness in the high temperature regime, as a consequence of a uniform decay of correlations holding there (spatial mixing) CompTree; Gamarnik; Devavrat. The behavior of iterative inference algorithms on Ising models was recently considered in Mooij; Sudderth.

The emphasis of the present paper is on the low-temperature regime in which uniform decorrelation does not hold. We are able to prove that belief propagation converges exponentially fast on any graph, and that the resulting estimates are asymptotically exact for large locally tree-like graphs. The main idea is to introduce a magnetic field to break explicitly the $+/-$ symmetry, and to carefully exploit the monotonicity properties of the model.

A key step consists of estimating the correlation between the root spin of an Ising model on a tree and positive boudary conditions. Ising models on trees are interesting per se, and have been the object of significant mathematical work; see, for instance, Lyons; Steif; PeresReconstr. The question considered here appears, however, to be novel.

The next section provides the basic technical definitions (in particular concerning graphs and local convergence to trees), and the formal statement of our main results. Notation and certain key tools are described in Section 3 with Section 4 devoted to proofs of the relevant properties of Ising models on trees (which are of independent interest). The latter are used in Sections 5 and 6 to derive our main results concerning models on tree-like graphs. A companion paper GerschenMon2 deals with the related challenging problem of spin glass models on sparse graphs.

Definitions and main results

The next subsections contain some basic definitions on graph sequences and the notion of local convergence to random trees. Sections 2.2 and 2.3 present our results on the free entropy density and the algorithmic implications of our analysis.

Let $P=\{P_{k}\colon\;k\geq 0\}$ a probability distribution over the nonnegative integers, with finite, positive first moment, and denote by

its size-biased version. For any $t\geq 0$, we let $\mathsf{T}(P,\rho,t)$ denote the random rooted tree generated as follows. First draw an integer $k$ with distribution $P_{k}$, and connect the root to $k$ offspring. Then recursively, for each node in the last generation, generate an integer $k$ independently with distribution $\rho_{k}$, and connect the node to $k-1$ new nodes. This is repeated until the tree has $t$ generations.

Sometimes it will be useful to consider the ensemble $\mathsf{T}(\rho,t)$ whereby the root node has degree $k-1$ with probability $\rho_{k}$. We will drop the degree distribution arguments from $\mathsf{T}(P,\rho,t)$ or $\mathsf{T}(\rho,t)$ and write $\mathsf{T}(t)$ whenever clear from the context. Notice that the infinite trees $\mathsf{T}(P,\rho,\infty)$ and $\mathsf{T}(\rho,\infty)$ are well defined.

The average branching factor of trees will be denoted by $\overline{\rho}$, and the average root degree by $\overline{P}$. In formulae

We denote by $G_{n}=(V_{n},E_{n})$ a graph with vertex set $V_{n}\equiv[n]=\{1,\dots,n\}$. The distance $d(i,j)$ between $i,j\in V_{n}$ is the length of the shortest path from $i$ to $j$ in $G_{n}$. Given a vertex $i\in V_{n}$, we let $\mathsf{B}_{i}(t)$ be the set of vertices whose distance from $i$ is at most $t$. With a slight abuse of notation, $\mathsf{B}_{i}(t)$ will also denote the subgraph induced by those vertices. For $i\in V_{n}$, we let ${\partial i}$ denote the set of its neighbors ${\partial i}\equiv\{j\in V_{n}\colon\;(i,j)\in E_{n}\}$, and $|{\partial i}|$ its size (i.e. the degree of $i$).

2 Free entropy

According to the statistical physics derivation Vespignani, the model (1) has a line of first-order phase transitions for $B=0$ and $\beta>\beta_{\rm c}$ [i.e., where the continuous function $B\mapsto\phi(\beta,B)$ exhibits a discontinuous derivative]. The critical temperature depends on the graph only through the average branching factor and is determined by the condition

Notice that $\beta_{\rm c}\simeq 1/\overline{\rho}$ for large degrees.

The asymptotic free-entropy density is given in terms of the fixed point of a distributional recursion. One characterization of this fixed point is as follows.

Consider the sequence of random variables $\{h^{(t)}\}$ defined by $h^{(0)}=0$ identically and, for $t\geq 0$,

where $K$ is an integer valued random variable of distribution $\rho$,

and the $h^{(t)}_{i}$’s are i.i.d. copies of $h^{(t)}$ that are independent of $K$. If $B>0$ and $\rho$ has finite first moment, then the distributions of $h^{(t)}$ are stochastically monotone and $h^{(t)}$ converges in distribution to the unique fixed point $h^{*}$ of the recursion (8) that is supported on $[0,\infty)$.

Our next result confirms the statistical physics prediction for the free-entropy density.

Moreover, for $B>0$ the limit is given by

where $L$ has distribution $P_{l}$ and is independent of the “cavity fields” $h_{i}$ that are i.i.d. copies of the fixed point $h^{*}$ of Lemma 2.3. Also, $\phi(\beta,B)=\phi(\beta,-B)$ and $\phi(\beta,0)$ is the limit of $\phi(\beta,B)$ as $B\to 0$.

The proof of Theorem 2.4 is based on two steps:

Reduce the computation of $\phi_{n}(\beta,B)=\frac{1}{n}\log Z_{n}(\beta,B)$ to computing expectations of local (in $G_{n}$) quantities with respect to the Boltzmann measure (1). This is achieved by noticing that the derivative of $\phi_{n}(\beta,B)$ with respect to $\beta$ is a sum of such expectations.

Show that expectations of local quantities on $G_{n}$ are well approximated by the same expectations with respect to an Ising model on the associated tree $\mathsf{T}(P,\rho,t)$ (for $t$ and $n$ large). This is proved by showing that, on such a tree, local expectations are insensitive to boundary conditions that dominate stochastically free boundaries. The theorem then follows by monotonicity arguments.

The key step is of course the last one. A stronger requirement would be that these expectation values are insensitive to any boundary condition, which would coincide with uniqueness of the Gibbs measure on $\mathsf{T}(P,\rho,\infty)$. Such a requirement would allow for an elementary proof, but holds only at “high” temperature, $\beta\leq\beta_{\rm c}$.

Indeed, insensitivity to positive boundary conditions is proved in Section 4 for the following collection of trees of conditionally independent (and of bounded average) offspring numbers.

An infinite tree $\mathsf{T}$ rooted at the vertex $\o$ is called conditionally independent if for each integer $k\geq 0$, conditional on the subtree $\mathsf{T}(k)$ of the first $k$ generations of $\mathsf{T}$, the number of offspring $\Delta_{j}$ for $j\in\partial\mathsf{T}(k)$ are independent of each other, where $\partial\mathsf{T}(k)$ denotes the set of vertices at generation $k$. We further assume that the [conditional on $\mathsf{T}(k)$] first moments of $\Delta_{j}$ are uniformly bounded by a given nonrandom finite constant $\Delta$.

Beyond the random tree $\mathsf{T}(P,\rho,\infty)$, these include deterministic trees with bounded degrees and certain multi-type branching processes (such as random bipartite trees and percolation clusters on deterministic trees of bounded degree). Consequently, Theorem 2.4 extends to any uniformly sparse graph sequence that converge locally to a random tree $\mathsf{T}$ of the form of Definition 2.5 except that the formula $\phi(\beta,B)$ is in general more involved than the one given in (11). For example, such an extension allows one to handle uniformly random bipartite graphs with different degree distributions $P_{k}$ and $Q_{k}$ for the two types of vertices.

While we refrain from formalizing and proving such generalizations, we note in passing that our derivation of the formula (11) implicitly uses the fact that $\mathsf{T}(P,\rho,\infty)$ possesses the involution invariance of Aldous. As pointed out in AL, every local limit of finite graphs must have the involution invariance property (which clearly not every conditionally independent tree has).

3 Algorithmic implications

The free entropy density is not the only quantity that can be characterized for Ising models on locally tree-like graphs. Indeed local marginals can be efficiently computed with good accuracy. The basic idea is to solve a set of mean field equations iteratively. These are known as Bethe–Peierls or cavity equations and the corresponding algorithm is referred to as “belief propagation” (BP).

More precisely, associate to each directed edge in the graph $i\to j$, with $(i,j)\in G$, a distribution $\nu_{i\to j}(x_{i})$ over $x_{i}\in\{+1,-1\}$. In the computer science literature these distributions are referred to as “messages.” They are updated as follows:

The initial conditions $\nu_{i\to j}^{(0)}(\cdot)$ may be taken to be uniform or chosen

according to some heuristic. We will say that the initial condition is positive

if $\nu_{i\to j}^{(0)}(+1)\geq\nu_{i\to j}^{(0)}(-1)$ for each of these messages.

Assume $\beta\geq 0$, $B>0$ and $G$ is a graph of finite maximal degree $\Delta$. Then, there exists $A=A(\beta,B,\Delta)$ finite, $\lambda=\lambda(\beta,B,\Delta)>0$ and a fixed point $\{\nu^{*}_{i\to j}\}$ of the BP iteration (12) such that for any positive initial

condition $\{\nu^{(0)}_{l\to k}\}$ and all $t\geq 0$,

For $i_{*}\in V$ let $U\equiv\mathsf{B}_{i_{*}}(r)$ be the ball of radius $r$ around $i_{*}$ in $G$, denoting by $E_{U}$ its edge set, by $\partial U$ its border (i.e., the set of its vertices at distance $r$ from $i_{*}$), and for each $i\in\partial U$ let $j(i)$ denote any one fixed neighbor of $i$ in $U$.

Our next result shows that the probability distribution

with $\{\nu_{i\to j}^{*}(\cdot)\}$ the fixed point of the BP iteration per Theorem 2.6, is a good approximation for the marginal $\mu_{U}(\cdot)$ of variables $\underline{x}_{U}\equiv\{x_{i}\colon\;i\in U\}$ under the Ising model (1).

Assume $\beta\geq 0$, $B>0$ and $G$ is a graph of finite maximal degree $\Delta$. Then, there exist finite $c=c(\beta,B,\Delta)$ and $\lambda=\lambda(\beta,B,\Delta)>0$ such that for any $i_{*}\in G$ and $U=\mathsf{B}_{i_{*}}(r)$, if $\mathsf{B}_{i_{*}}(t)$ is a tree then

4 Examples

Many common random graph ensembles Rgraphs naturally fit our framework.

Let $G_{n}$ be a uniformly random graph with degree $k$. As $n\to\infty$, the sequence $\{G_{n}\}$ is obviously uniformly sparse, and converges locally almost surely to the rooted infinite tree of degree $k$ at every vertex. Therefore, in this case Theorem 2.4 applies with $P_{k}=1$ and $P_{i}=0$ for $i\neq k$. The distributional recursion (8) then evolves with a deterministic sequence $h^{(t)}$ recovering the result of GerschenMon1.

Erdös–Renyi graphs

Let $G_{n}$ be a uniformly random graph with $m=n\gamma$ edges over $n$ vertices. The sequence $\{G_{n}\}$ converges locally almost surely to a Galton–Watson tree with Poisson offspring distribution of mean $2\gamma$. This corresponds to taking $P_{k}=(2\gamma)^{k}e^{-2\gamma}/k!$. The same happens to classical variants of this ensemble. For instance, one can add an edge independently for each pair $(i,j)$ with probability $2\gamma/n$, or consider a multi-graph with $\operatorname{Poisson}(2\gamma/n)$ edges between each pair $(i,j)$.

The sequence $\{G_{n}\}$ is with probability one uniformly sparse in each of these cases. Thus, Theorem 2.4 extends the results of deSantisGuerra to arbitrary nonzero temperature and magnetic field.

Arbitrary degree distribution

Let $P$ be a distribution with finite second moment and $G_{n}$ a uniformly random graph with degree distribution $P$ (more precisely, we set the number of vertices of degree $k\geq 1$ to $\lfloor nP_{k}\rfloor$, adding one for $k=1$ if needed for an even sum of degrees). Then, $\{G_{n}\}$ is uniformly sparse and with probability one it converges locally to $\mathsf{T}(P,\rho,\infty)$. The same happens if $G_{n}$ is drawn according to the so-called configuration model (cf. Bollobas).

Preliminaries

We review here the notations and a couple of classical tools we use throughout this paper. To this end, when proving our results it is useful to allow for vertex-dependent magnetic fields $B_{i}$, that is, to replace the basic model (1) by

The first classical result we need is Griffiths inequality (see Liggett, Theorem IV.1.21).

Consider two Ising models $\mu(\cdot)$ and $\mu^{\prime}(\cdot)$ on graphs $G=(V,E)$ and $G^{\prime}=(V,E^{\prime})$, inverse temperatures $\beta$ and $\beta^{\prime}$, and magnetic fields $\{B_{i}\}$ and $\{B_{i}^{\prime}\}$, respectively. If $E\subseteq E^{\prime}$, $\beta\leq\beta^{\prime}$ and $0\leq B_{i}\leq B_{i}^{\prime}$ for all $i\in V$, then $0\leq\langle\mu,\prod_{i\in U}x_{i}\rangle\leq\langle\mu^{\prime},\prod_{i\in U}x_{i}\rangle$ for any $U\subseteq V$.

The second classical result we use is the GHS inequality (see GHS) about the effect of the magnetic field $\underline{B}$ on the local magnetizations at various vertices.

Let $\beta\geq 0$ and for $\underline{B}=\{B_{i}\colon\;i\in V\}$, denote by $m_{j}(\underline{B})\equiv\mu(\{\underline{x}\colon\;x_{j}=+1\})-\mu(\{\underline{x}\colon\;x_{j}=-1\})$ the local magnetization at vertex $j$ in the Ising model (16). If $B_{i}\geq 0$ for all $i\in V$, then for any three vertices $j,k,l\in V$ (not necessarily distinct),

Finally, we need the following elementary inequality:

For any function $f\colon\;\mathcal{X}\mapsto[0,f_{\max}]$ and distributions $\nu$, $\nu^{\prime}$ on the finite set $\mathcal{X}$ such that $\nu(f>0)>0$ and $\nu^{\prime}(f>0)>0$,

Assuming without loss of generality that $\langle\nu^{\prime},f\rangle\geq\langle\nu,f\rangle>0$, the left-hand side of (18) can be bounded as

Ising models on trees

We start with the following simple but useful observation.

For a subtree $U$ of a finite tree $T$ let $\partial_{*}U$ denote the subset of vertices of $U$ connected by an edge to $W\equiv T\setminus U$ and for each $u\in\partial_{*}U$ let $\langle x_{u}\rangle_{W}$ denote the root magnetization of the Ising model on the maximal subtree $T_{u}$ of $W\cup\{u\}$ rooted at $u$. The marginal on $U$ of the Ising measure on $T$, denoted $\mu^{T}_{U}$ is then an Ising measure on $U$ with magnetic field $B_{u}^{\prime}=\operatorname{atanh}(\langle x_{u}\rangle_{W})\geq B_{u}$ for $u\in\partial_{*}U$ and $B_{u}^{\prime}=B_{u}$ for $u\notin\partial_{*}U$.

Since $U$ is a subtree of the tree $T$, the subtrees $T_{u}$ for $u\in\partial_{*}U$ are disjoint. Therefore, with $\hat{\mu}_{u}(\underline{x})$ denoting the Ising model distribution for $T_{u}$ we have that

Further, $x_{u}\in\{+1,-1\}$ so for each $u\in\partial_{*}U$ and some constants $c_{u}$,

Embedding the normalization constants $c_{u}$ within $\hat{Z}$ we thus conclude that $\mu^{T}_{U}$ is an Ising measure on $U$ with the stated magnetic field $B_{u}^{\prime}$. Finally, comparing the root magnetization for $T_{u}$ with that for $\{u\}$ we have by Griffiths inequality that $\langle x_{u}\rangle_{W}\geq\tanh(B_{u})$, as claimed.

for $\delta(t)=M/t$, all $U\subseteq\mathsf{T}(r)$ and $\beta\leq\beta_{\max}$.

Suppose $\mathsf{T}$ is a conditionally independent infinite tree of average offspring numbers bounded by $\Delta$. For $0<B_{\min}\leq B_{\max}$, $\beta_{\max}$ and $\Delta$ finite, there exist $M=M(\beta_{\max},B_{\min},\Delta)$ such that

and denote by $m^{k}(\underline{B},\underline{H})$ the corresponding root magnetization. Writing $H$ instead of $\underline{H}$ for constant magnetic field on the leave nodes, that is, when $H_{i}=H$ for each $i\in\partial\mathsf{T}(k)$, we note that $m^{k,+}(\underline{B})=m^{k}(\underline{B},\infty)$ and $m^{k,0}(\underline{B})=m^{k}(\underline{B},0)$. Further, applying Lemma 4.1 for the subtree $\mathsf{T}(k-1)$ of $\mathsf{T}(k)$ we represent $m^{k}(\underline{B},\infty)$ as the root magnetization $m^{k-1}(\underline{B}^{\prime},0)$ on $\mathsf{T}(k-1)$ where $B^{\prime}_{i}=B_{i}+\beta\Delta_{i}$ for $i\in\partial\mathsf{T}(k-1)$ and $B^{\prime}_{i}=B_{i}$ for all other $i$. Consequently,

Next note that $\xi(\beta,B)\leq\beta\leq\beta\Delta$ and by GHS inequality $H\mapsto m^{k-1}(\underline{B},H)$ is concave. Hence,

and all $\beta\leq\beta_{\max}$. Combining (25), (26) and (27) we obtain that

Simon’s inequality (see Simon, Theorem 2.1) allows one to bound the (centered) two point correlation functions in ferromagnetic Ising models with zero magnetic field. We provide next its generalization to arbitrary magnetic field, in the case of Ising models on trees.

where $\langle\cdot\rangle^{(r)}_{i}$ denotes the expectation with respect to the Ising distribution $\hat{\mu}_{i}(\cdot)$ on the subtree $\mathsf{T}_{i}$ of $i$ and all its descendants in $\mathsf{T}(r)$ and $\langle x;y\rangle\equiv\langle xy\rangle-\langle x\rangle\langle y\rangle$ denotes the centered two point correlation function.

It is not hard to check that if $x,y,z$ are $\{+1,-1\}$-valued random variables with $x$ and $z$ conditionally independent given $y$, then

Equipped with the preceding lemma we next establish the exponential decay of correlations and of the effect of boundary conditions in Theorem 4.2.

There exist $A$ finite and $\lambda$ positive, depending only on $\beta_{\max}$, $B_{\min}$, $B_{\max}$ and $\Delta$ such that

By GHS inequality the latter derivative is nonincreasing in $H_{r}$, whence

Let $B_{i}^{\prime}=B_{i}-B_{\min}/2$ if $i\in\partial\mathsf{T}(r)$ and $B_{i}^{\prime}=B_{i}$ otherwise, so $\langle x_{\o}\rangle_{H_{r}=-B_{\rm min}/2}=m^{r,0}(\underline{B}^{\prime})$. Further, from Griffiths inequality also $\langle x_{\o}\rangle_{H_{r}=0}\leq\langle x_{\o}\rangle_{H_{r}=\infty}=m^{r,+}(\underline{B}^{\prime})$ and it follows that

In particular, setting $c=\cosh^{2}(2\beta_{\max}+B_{\max})$, in view of Lemma 4.3 we find that $\Gamma_{d-1}\leq 1/(ec\Delta)$ for $d=1+\lceil 2ec\Delta M(\beta_{\max},B_{\min}/2,\Delta)/B_{\min}\rceil$. Further, since $\mathsf{T}$ is conditionally independent, the same proof shows that if $t+d=r^{\prime}\leq r$ and $\mathsf{T}_{j}$ is the subtree of $\mathsf{T}(r)$ of depth $d-1$ rooted at $j\in\partial\mathsf{T}(t+1)$ then

Considering inequality (28) of Lemma 4.4 for $t=r-d\equiv r_{1}$ and all $k\in\partial\mathsf{T}(r)$ we find that

Iterating the preceding bound at $r_{s}=r-sd$, for $s=1,\ldots,\lfloor r/d\rfloor$ and noting that by (32) we have the bound $\Gamma_{r^{\prime}}\leq 2/B_{\min}$ at the last step, we get the uniform in $\beta\leq\beta_{\max}$ exponential decay of (31).

we get the rate $\delta(t)=A\exp(-\lambda t)$ from (31) as soon as we show that for $i=i(s+1)$ and $s=0,\ldots,k-1$,

which by GHS inequality is maximal at $s=0$, yielding (33) and completing the proof.

As promised, Lemma 2.3 follows from the preceding results.

[Proof of Lemma 2.3] Consider the Galton–Watson tree $\mathsf{T}(\rho,\infty)$ of Section 2.1 and the corresponding Ising models $\mu^{t,+/0}(\underline{x})$ of constant magnetic field $B_{i}=B>0$ on the subtrees $\mathsf{T}(\rho,t)$. It is easy to check that the random variables $h^{(t)}=\operatorname{atanh}(m^{t,0}(B))$ satisfy the distributional recursion (8) starting at $h^{(0)}=0$. By Griffiths inequality $m^{t,0}(B)$, hence $h^{(t)}$, is nondecreasing in $t$, and so converges almost surely as $t\to\infty$ to a limiting random variable $h^{*}$. Further, the bounds $0=h^{(0)}\leq h^{(t)}\leq B+\Delta_{\o}$ hold for all $t$ and hence also for $h^{*}$. We thus deduce that the distributions $Q_{t}$ of $h^{(t)}$ as determined by (8) are stochastically monotone (in $t$) and converge weakly to some law $Q^{*}$ of $h^{*}$ that is supported on $[0,\infty)$.

are continuous and bounded. Further, it follows from (8) that for all $t$

Taking $t\to\infty$ followed by $k\to\infty$, we deduce by the preceding arguments [and the uniform boundedness $|\Psi_{g_{j}}(Q^{*})|\leq C$ for all $j$], that

As this applies for every bounded continuous function $g(\cdot)$, we conclude that $h^{*}$ and its law $Q^{*}$ are a fixed point of the distributional recursion (8).

We next control the dependence on $\beta$ of the distribution of the fixed point $h^{*}$ from Lemma 2.3.

Fixing a random tree $\mathsf{T}=\mathsf{T}(\rho,\infty)$ of degree distribution $\rho$, recall that while proving Lemma 2.3 we provided a coupling of the random variables $\tanh(h^{*}_{\beta})$ and the Ising root magnetizations $m^{t,+/0}(\beta,B)$ at $\beta$ such that

for each $\beta$ and all $t$. By Griffiths inequality the magnetizations at the root are nondecreasing in $\beta$ so from the bound (23) we get that for $M=M(\beta_{\max},B,\overline{\rho})$ and any $\beta_{1}\leq\beta_{2}\leq\beta_{\max}$,

where $\gamma$ is the arithmetic mean of the conditional expected value of $x_{j}$ for $x_{i}=-1$ and the conditional expected value of $x_{j}$ for $x_{i}=1$. Thus, $|\gamma|\leq 1$ and recalling (30) that $\langle x_{\o};x_{i}\rangle$ is nonnegative by Griffiths inequality, we deduce that

where $\Delta_{i}$ denotes the offspring number at $i\in\mathsf{T}$ and by (30)

[with $m^{k}(\underline{B},\underline{H})$ the root magnetization for the measure $\mu^{\underline{B},\underline{H}}$ of (4)]. In view of Lemma 4.1 we have that $m^{k}(\underline{B},0)=m^{k-1}(\underline{B},\underline{H})$ for some nonnegative vector $\underline{H}$. By GHS inequality we deduce that for any $i\in\mathsf{T}(k-1)$

Algorithms

The theorems stated in Section 2.3 are in fact consequences of Corollary 4.5.

[Proof of Theorem 2.6] The proof is based on the well-known representation of the iteration (12) in terms of “computation tree” CompTree. Namely, $\nu^{(t)}_{i\to j}(\cdot)$ coincides with the marginal at the root of the Ising model (1) on a properly constructed, deterministic tree $\mathsf{T}^{\mathsf{c}}_{i\to j}(t)$ of $t$ generations. While we refer to the literature for the precise definition of $\mathsf{T}^{\mathsf{c}}_{i\to j}(t)$, here are some immediate properties:

One can construct an infinite tree $\mathsf{T}^{\mathsf{c}}_{i\to j}(\infty)$ such that, for any $t$, $\mathsf{T}^{\mathsf{c}}_{i\to j}(t)$ is the subtree formed by the first $t$ generations of $\mathsf{T}^{\mathsf{c}}_{i\to j}(\infty)$.

The maximal degree of $\mathsf{T}^{\mathsf{c}}_{i\to j}(\infty)$ is bounded by the maximal degree of $G$ (and equal to the latter when $G$ is connected).

A positive initialization corresponds to adding $H_{l\to k}=\operatorname{atanh}(\nu^{(0)}_{l\to k}(+1)-\nu^{(0)}_{l\to k}(-1))$ nonnegative to the field $B$ on the $t$th generation vertices of $\mathsf{T}^{\mathsf{c}}_{i\to j}(t)$.

Denote by $\nu^{+,(t)}_{i\to j}(\cdot)$, $\nu^{0,(t)}_{i\to j}(\cdot)$ the messages obtained under initializations$\nu^{+,(0)}_{k\to l}(+1)=1$ and $\nu^{0,(0)}_{k\to l}(+1)=\nu^{0,(0)}_{k\to l}(-1)=1/2$, respectively. By Griffiths inequality, $\nu^{+,(t)}_{i\to j}(+1)$ is nonincreasing in $t$, $\nu^{0,(t)}_{i\to j}(+1)$ is nondecreasing in $t$ and any positive initialization results with $\nu^{(t)}_{i\to j}(\cdot)$ such that

By Corollary 4.5 we have that $\nu^{+,(t)}_{i\to j}(+1)-\nu^{0,(t)}_{i\to j}(+1)\leq Ae^{-\lambda t}$ for all $t\geq 0$. Since $A<\infty$ and $\lambda>0$ depend only on $\beta$, $B$ and the maximal degree of $G$, this immediately yields our thesis.

[Proof of Theorem 2.7] We use an additional property of the computation tree:

If $\mathsf{B}_{i}(k)$ is a tree then $\mathsf{T}^{\mathsf{c}}_{i\to j}(k)$ is a tree rooted at $i\to j$ whose vertices are the directed edges on the maximal subtree of $\mathsf{B}_{i}(k)$ rooted at $i$ that does not include $j$.

Without loss of generality we may and shall assume that $t>r$. For $U=\mathsf{B}_{i_{*}}(r)$ consider the local marginal approximations $\nu_{U}^{+}(\cdot)$, $\nu_{U}^{0}(\cdot)$ defined as in (14) except that the fixed point messages $\nu^{*}_{i\to j(i)}(\cdot)$ at $i\in\partial\mathsf{B}_{i_{*}}(r)$ are replaced by

those obtained after $(t-r)$ iterations starting at $\nu^{+,(0)}_{k\to l}(+1)=1$ and $\nu^{0,(0)}_{k\to l}(+1)=\nu^{0,(0)}_{k\to l}(-1)=1/2$, respectively. Since $\mathsf{B}_{i_{*}}(t)$ is a tree, here $j(i)$ is necessarily the neighbor of $i$ on the path from $i_{*}$ to $i\in\partial\mathsf{B}_{i_{*}}(r)$ and from the preceding property (d) we see that $\mathsf{T}^{\mathsf{c}}_{i\to j(i)}(t-r)$ corresponds to the subtree of $i$ and its lines of descendant in $\mathsf{B}_{i_{*}}(t)$. By property (c) we thus have that $\nu_{U}^{+}(\cdot)$ and $\nu_{U}^{0}(\cdot)$ are the marginals on $U$ of the Ising model $\nu^{+}$ on $G$ with $B_{i}=\infty$ at all $i\notin\mathsf{B}_{i_{*}}(t)$ and the Ising model $\nu^{0}$ on the vertices of $G$ and the edges within the tree $\mathsf{B}_{i_{*}}(t)$. Such reasoning also shows that the probability measure $\nu_{U}$ of (14) is the marginal on $U$ of the Ising model $\nu$ on vertices of $G$ and edges of $\mathsf{B}_{i_{*}}(t)$ with an additional nonnegative magnetic field $H_{l\to k}=\operatorname{atanh}(\nu^{*}_{l\to k}(+1)-\nu^{*}_{l\to k}(-1))$ at $\partial\mathsf{B}_{i_{*}}(t)$. Consequently, with $x_{F}\equiv\prod_{i\in F}x_{i}$ we have by Griffiths inequality that for any $F\subseteq U$

and we deduce that for any $F\subseteq U$,

Recall that since $x_{i}\in\{-1,1\}$, for any possible value $\underline{y}=\{y_{i},i\in U\}$ of $\underline{x}_{U}$,

This applies for any of the $2^{|U|}$ possible values of $\underline{x}_{U}$, so

Applying Corollary 4.5 for the deterministic tree $\mathsf{B}_{i_{*}}(t)$ rooted at $i_{*}$, we get the bound (22) on the right side of the preceding inequality with $\delta(k)=A\exp(-\lambda k)$, some finite $A$ and $\lambda>0$ that depend only on $\beta$, $B$ and $\Delta$. Thus, noting that $|U|=|\mathsf{B}_{i_{*}}(r)|\leq\Delta^{r+1}+1$ we establish our thesis upon choosing $c=c(A,C,\Delta)$ large enough.

From trees to graphs

We start with the following technical lemma.

Then, for any i.i.d. $Y,Y_{i}\in\mathcal{K}$ also independent of $L$,

Finally, taking $\gamma\downarrow 1$ yields the bound (6.1).

Consider the functional $h\mapsto\varphi_{h}$ that, given a random variable $h$, evaluates the right-hand side of Equation (11). It is not hard to check that $\varphi_{h}$ is well defined and finite for every random variable $h$. The following corollary of Lemma 6.1 plays an important role in the proof of Theorem 2.4.

Setting $u=\tanh(\beta)$ so $|u|<1$, we verify the conditions ofLemma 6.1 when $X_{i}$ are i.i.d. copies of $X=\tanh(h^{*})$ and $Y_{i}$ i.i.d. copies of $Y=\tanh(h)$, all of whom take values in $\mathcal{K}=$ and are independent of the random variable $L$. We apply the lemma in this setting for the symmetric, twice differentiable functions

for some constant $F_{0}$ and that both series are absolutely summable.

Let $\overline{\mathsf{T}}(\rho,\infty)$ denote the infinite random tree obtained by “gluing” two independent trees from the ensemble $\mathsf{T}(\rho,\infty)$ through an extra edge $e$ between their roots and considering $e$ as the root of $\overline{\mathsf{T}}(\rho,\infty)$ denote by $\overline{\mathsf{T}}(\rho,t)$ the subtree formed by its first $t$ generations [i.e., consisting of $e$ and the corresponding two independent copies from $\mathsf{T}(\rho,t)$]. An alternative way to sample from $\overline{\mathsf{T}}(\rho,\infty)$ is to have independent offspring number $k-1$ with probability $\rho_{k}$ at each end of the root edge $e$ and thereafter independently sample from this offspring distribution at each revealed new node of the tree. Equipped with these notations we have the following consequence of the local convergence of the graph sequence $\{G_{n}\}$.

Suppose a uniformly sparse graph sequence $\{G_{n}\}$ converges locally to the random tree $\mathsf{T}(P,\rho,\infty)$. Fixing a nonnegative integer $t$, for each $(i,j)\in E_{n}$ denote the subgraph of $G_{n}$ induced by vertices at distance at most $t$ from $(i,j)$ by $\mathsf{B}_{ij}(t)$. Let $F(\cdot)$ be a fixed, bounded function on the collection of all possible subgraphs that may occur as $\mathsf{B}_{ij}(t)$, such that $F(T_{1})=F(T_{2})$ whenever $T_{1}\simeq T_{2}$. Then,

Marking uniformly at random one offspring of $\o$ in $\mathsf{T}(P,\rho,t+1)$ [as corresponding to $j(i)$], let $\mathsf{T}_{*}(t+1)$ denote the subtree induced by vertices whose distance from either $\o$ or its marked offspring is at most $t$. Since $\mathsf{B}_{ij(i)}(t)\subseteq\mathsf{B}_{i}(t+1)$ and with probability $q_{t,k}\to 1$ as $k\to\infty$ the random tree $\mathsf{T}(P,\rho,t+1)$ belongs to the finite collection of trees with $t+1$ generations and maximal degree at most $k$, it follows by dominated convergence and the local convergence of $\{G_{n}\}$ that for any fixed $l$,

Further, by the uniform sparsity of $\{G_{n}\}$,

goes to zero as $l\to\infty$. Since $P$ has a finite first moment, $\Delta_{\o}$ is integrable, so by the preceding, upon taking $l\to\infty$ we deduce by dominated convergence that

[Proof of Theorem 2.4] Since $\phi_{n}(\beta,B)\equiv\frac{1}{n}\log Z_{n}(\beta,B)$ is invariant under $B\to-B$ and is uniformly (in $n$) Lipschitz continuous in $B$ with Lipschitz constant one, it suffices to fix $B>0$ and show that $\phi_{n}(\beta,B)$ converges as $n\to\infty$ to the predicted $\varphi_{h^{*}}(\beta,B)$ of (11), whereby $h^{*}=h^{*}_{\beta}$ is the unique fixed point of the recursion (8) that is supported on $[0,\infty)$ (see Lemma 2.3).

This is obviously true for $\beta=0$ since $\phi_{n}(0,B)=\log(2\cosh B)=\varphi_{h}(0,B)$. Next, denoting by $\langle\cdot\rangle_{n}$ the expectation with respect to the Ising measure on $G_{n}$ (at parameters $\beta$ and $B$), it is easy to see that

Clearly $|\partial_{\beta}\phi_{n}(\beta,B)|\leq|E_{n}|/n$ is bounded by the uniform sparsity of $\{G_{n}\}$ so it is enough to show that the expression in (44) converges to the partial derivative of $\varphi_{h^{*}_{\beta}}(\beta,B)$ with respect to $\beta$. Turning to compute the latter derivative, by Lemma 4.6 and Corollary 6.3 we can ignore the dependence of $h^{*}_{\beta}$ on $\beta$. That is, we simply compute the partial derivative in $\beta$ of the expression (11) while considering (the law of) $h_{i}$ to be fixed. Indeed, with notation $u=\tanh(\beta)$ and $X_{i}=\tanh(h_{i})$ as in the derivation of Corollary 6.3, a direct computation leads by the exchangeability of $X_{i}$ to

Consequently, it is not hard to verify that

where $\langle\cdot\rangle_{\overline{\mathsf{T}}}$ denotes the expectation with respect to the Ising model

on one edge $(ij)$ and random magnetic fields $H_{i}$ and $H_{j}$ that are independent copies of $h^{*}_{\beta}$.

In comparison, fixing a positive integer $t$, by Griffiths inequality the correlation $\langle x_{i}x_{j}\rangle_{n}$ lies between the correlations $F_{0}(\mathsf{B}_{ij}(t))\equiv\langle x_{i}x_{j}\rangle^{0}_{\mathsf{B}_{ij}(t)}$ and $F_{+}(\mathsf{B}_{ij}(t))\equiv\langle x_{i}x_{j}\rangle^{+}_{\mathsf{B}_{ij}(t)}$ for the Ising model on the subgraph $\mathsf{B}_{ij}(t)$ with free and plus, respectively, boundary conditions at $\partial\mathsf{B}_{ij}(t)$. Thus, in view of (44)

and taking $n\to\infty$ we get by Lemma 6.4 that

which completes the proof of the theorem.

References