# Broadcasting with Random Matrices

Charilaos Efthymiou∗ and Kostas Zampetakis∗ Charilaos Efthymiou,
<EMAIL_ADDRESS>The University of Warwick, Coventry, CV4
7AL, UK.  Kostas Zampetakis<EMAIL_ADDRESS>The University
of Warwick, Coventry, CV4 7AL, UK.

###### Abstract.

Motivated by the theory of spin-glasses in physics, we study the so-called
reconstruction problem on the tree, and on the sparse random graph
$\mathbold{G}(n,d/n)$. Both cases reduce naturally to analysing broadcasting
models, where each edge has its own broadcasting matrix, and this matrix is
drawn independently from a predefined distribution.

We establish the reconstruction threshold for the cases where the broadcasting
matrices give rise to symmetric, 2-spin Gibbs distributions. This threshold
seems to be a natural extension of the well-known Kesten-Stigum bound that
manifests in the classic version of the reconstruction problem. Our results
determine, as a special case, the reconstruction threshold for the prominent
Edwards–Anderson model of spin-glasses, on the tree.

Also, we extend our analysis to the setting of the Galton-Watson random tree,
and the (sparse) random graph $\mathbold{G}(n,d/n)$, where we establish the
corresponding thresholds. Interestingly, for the Edwards–Anderson model on the
random graph, we show that the replica symmetry breaking phase transition,
established by Guerra and and Toninelli in [21], coincides with the
reconstruction threshold.

Compared to classical Gibbs distributions, spin-glasses have several unique
features. In that respect, their study calls for new ideas, e.g. we introduce
novel estimators for the reconstruction problem. The main technical challenge
in the analysis of such systems, is the presence of (too) many levels of
randomness, which we manage to circumvent by utilising recently proposed tools
coming from the analysis of Markov chains.

∗Research supported by EPSRC New Investigator Award, grant EP/V050842/1, and
Centre of Discrete Mathematics and Applications (DIMAP), University of
Warwick, UK

##  1\. Introduction

Motivated by the theory of spin-glasses in physics, we study the so-called
reconstruction problem with respect to the related distributions, on the tree,
and on the sparse random graph $\mathbold{G}(n,d/n)$.

Spin-glasses are disordered magnetic materials that are studied by physicists
(not necessarily the theoretical ones). It has been noted that even though
they are a type of magnet, actually, “they are not very good at being
magnets”. Metallic spin-glasses are “unremarkable conductors”, and the
insulating spin-glasses are “fairly useless as practical insulators …”, e.g.
see [30].

However, the research on spin-glasses has provided tools to analyse some
exciting, and extremely challenging, problems in mathematics, physics, but
also real world ones. Through their study, we have garnered a deep
understanding of the nature of complex systems. A case in point is the
pioneering work of Giorgio Parisi in ‘70s on the so-called _Sherrington-
Kirkpatrick_ spin-glass, which introduces the formulation of the renowned
replica symmetry breaking [27]. Parisi’s ideas were highly influential in
physics community, and later, in mathematics, and computer science. The theory
of replica symmetry breaking was among the groundbreaking ideas which got
Parisi the Nobel Prize in Physics in 2021.

Perhaps one of the most successful, and extensively studied spin-glass models,
is the famous _Edwards-Anderson_ model (EA-model for short), introduced back
in ‘70s by Sam Edwards and Philip Anderson in [16]. Few months after the work
of Edwards and Anderson, David Sherrington and Scott Kirkpatrick, in [28],
introduced their own model of spin-glasses, the well-known in computer science
literature, Sherrington-Kirkpatrick model (SK-model for short). As it turns
out, the SK-model corresponds to the mean field version of the EA-model.

Given a fixed graph $G=(V,E)$, the Edwards-Anderson model with inverse
temperature $\beta>0$, is the random Gibbs distribution $\mathbold{\mu}$ on
the configuration space $\\{\pm 1\\}^{V}$ defined as follows: let
$\\{{\mathbold{J}}_{e}:{e\in E}\\}$ be independent identically distributed
(i.i.d.) standard Gaussians. Then each configuration $\sigma\in\\{\pm
1\\}^{V}$ receives probability mass $\mathbold{\mu}(\sigma)$, defined by

$\displaystyle\mathbold{\mu}(\sigma)$
$\displaystyle\propto\exp\left(\beta\cdot\sum_{\\{u,w\\}\in E}{\bf
1}\\{\sigma(u)=\sigma(w)\\}\cdot{\mathbold{J}}_{\\{u,w\\}}\right)\enspace,$
(1)

where $\propto$ stands for “proportional to”. We usually refer to
$\\{{\mathbold{J}}_{e}\\}_{e\in E}$ as the coupling parameters. Let us comment
here that, alternatively, the Gibbs distribution is defined by replacing the
indicator ${{\bf 1}\\{\sigma(u)=\sigma(w)\\}}$ in (1), with the product
$\sigma(u)\sigma(w)$. However, the two formulations are equivalent, as a
simple transformation converts one to the other (see Appendix A). We also note
that there is a simpler version of the Edwards-Anderson model, in which
coupling parameters take independently $\pm 1$ values, uniformly at random.

Apart from its mathematical elegance, and theoretical importance, the Edwards-
Anderson model, and the related spin-glass distributions, arise also in
applications such as neural networks (e.g. the so-called Hopfield model),
protein folding, and conformational dynamics. We refer the interested reader
to [30], and references therein.

In this work, we largely study the Edwards-Anderson model on trees, and the
(locally tree-like) random graph $\mathbold{G}(n,d/n)$ with constant expected
degree $d$. This is the random graph on $n$ vertices, such that each edge
appears independently with probability $d/n$. Since the Edwards-Anderson model
on $\mathbold{G}(n,d/n)$ shares essential features with random Constraint
Satisfaction Problems ($r$-CSPs for short), it is not surprising that has been
studied extensively in terms of phase transitions, in physics, e.g. [19, 25],
mathematics, e.g. [21, 12], but also in computer science, e.g. for sampling
algorithms [17, 2].

In contrast to the standard Gibbs distributions on trees, e.g. the Ising
model, the Hard-core model, and the Potts model, the Edwards-Anderson model,
despite being the most basic distribution for spin-glasses, has not been
sufficiently studied. As a result, several fundamental questions about it
still remain open. Here, we consider the tree reconstruction problem for the
Edwards-Anderson model (and some natural extensions).

The reconstruction problem studies the effect of the configuration at a vertex
$r$, on that of the vertices at distance $h$ from $r$, as $h\to\infty$.
Specifically, we want to distinguish the region of parameters where the effect
is vanishing, from that where the effect is non-vanishing. Typically, the two
regions are specified in terms of a sharp threshold, i.e., we have an abrupt
transition from one region to the other as we vary the parameters of the
model. We usually call this phenomenon reconstruction threshold, and it has
been the subject of intense study, e.g. [26, 1, 22, 7, 29, 10]. In the context
of r-CSPs, the onset of reconstruction has been linked to an abrupt
deterioration of the performance of algorithms (both searching and counting),
e.g. see [1].

In this work, among other results, we establish precisely the reconstruction
threshold for the Edwards-Anderson model on the $\Delta$-ary tree, the Galton-
Watson tree with general offspring distribution, and the random graph
$\mathbold{G}(n,d/n)$. Furthermore, as far as the Edwards-Anderson model on
$\mathbold{G}(n,d/n)$ is concerned, we combine our results with [21, 12], to
conclude that the reconstruction threshold coincides with the so-called
Replica Symmetry Breaking phase transition.

Interestingly, for the $\Delta$-ary tree, we establish the reconstruction
threshold, not only for the Edwards-Anderson model, but also for the general
version of the Gibbs distribution $\mathbold{\mu}$ defined in (1). That is,
the coupling parameters are i.i.d. following a general distribution, not
necessary the standard Normal.

It turns out that the corresponding reconstruction problems on the Galton-
Watson tree with $\mathrm{Poisson}(d)$ offspring, and on the sparse random
graph $\mathbold{G}(n,d/n)$, are not too different from each other.
Connections have been established between these two Gibbs distributions, e.g.
see [4, 15, 11, 14]. We relate the two reconstruction results, i.e., for the
tree and the graph, by exploiting the idea of planted-model (Teacher-Student
model [31]) and the notion of contiguity [12]. In that respect, our basic
analysis involves the complete $\Delta$-tree, and the Galton-Watson tree,
while, subsequently, we extend these results to the random graph
$\mathbold{G}(n,d/n)$.

We study the reconstruction problem on trees by means of the broadcasting
models. These are abstractions of noisy transmitted information over the edges
of the tree, i.e., the edges act as noisy channels. To our knowledge, the
study of the broadcasting models, and the closely related reconstruction
problem, dates back to ‘60s with the seminal work of Kesten and Stigum [24].

Establishing the reconstruction threshold for the Edwards-Anderson model on
the $\Delta$-ary tree, as well as the generalisation of this distribution,
turns out to be a challenging problem. The difficulty of these models stems
from the manifestation of local frustration phenomena, i.e., mixed
ferromagnetic and antiferromagnetic interaction in the same neighbourhood, but
also from the “many levels of randomness” we need to deal with in their
analysis.

To this end, we make an extensive use of various potentials in order to
simplify the analysis. To establish non-reconstruction, we employ some newly
introduced techniques in the area of Markov chains and Spectral Independence
[3, 9], that combine potential functions to analyse tree recursions. To
establish reconstruction, we use a carefully crafted potential as an estimator
for the root configuration. We call this estimator flip-majority vote.

###  1.1. Broadcasting, Reconstruction and the Kesten-Stigum bound

Consider the $\Delta$-ary tree $T=(V,E)$, of height $h>0$. Let $r$ be the root
of the tree $T$. Broadcasting on $T$, is a stochastic process which abstracts
noisy transmission of information over the edges of the tree.

There is a finite set of spins ${\mathcal{A}}$, and an
${\mathcal{A}}\times{\mathcal{A}}$ stochastic matrix $M$, which we call the
broadcasting matrix, or transition matrix. With the broadcasting we obtain a
configuration ${\mathbold{\sigma}}\in{\mathcal{A}}^{V}$ by working recursively
as follows: assume that the configuration at the root $r$ is obtained
according to some predefined distribution over ${\mathcal{A}}$. If for the
non-leaf vertex $u$ in $T$ we have ${\mathbold{\sigma}}(u)=i$, then for each
vertex $w$, child of $u$, we have ${\mathbold{\sigma}}(w)=j$ with probability
$M(i,j)$, independently of the other children, i.e.,

$\Pr[{\mathbold{\sigma}}(w)=j\ |\ {\mathbold{\sigma}}(u)=i]=M(i,j)\enspace.$

Here we assume that ${\mathbold{\sigma}}(r)$ is distributed uniformly at
random in ${\mathcal{A}}$.

A natural problem to study in this setting is the so-called reconstruction
problem. Suppose that $\mu_{h}$ is the marginal distribution of the
configuration of the vertices at distance $h$ from the root. The
reconstruction problem amounts to studying the influence of the configuration
at the root of the tree to the marginal $\mu_{h}$. Specifically, we want to
compare the two distributions $\mu_{h}(\cdot\ |\ {\mathbold{\sigma}}(r)=i)$,
and $\mu_{h}(\cdot\ |\ {\mathbold{\sigma}}(r)=j)$ for different
$i,j\in{\mathcal{A}}$, i.e., $\mu_{h}$ conditional on the configuration at the
root being $i$ and $j$, respectively. The comparison is by means of the total
variation distance, i.e.,

$\left|\left|\mu_{h}(\cdot\ |\ {\mathbold{\sigma}}(r)=i)-\mu_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=j)\right|\right|_{\rm TV}\enspace.$

Typically, we focus on the behaviour of the quantity above, as $h$ grows.

######  Definition 1.1.

We say that the distribution $\mu$ exhibits reconstruction if there exist
spins $i,j\in{\mathcal{A}}$ such that

$\limsup_{h\to\infty}\left|\left|\mu_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=i)-\mu_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=j)\right|\right|_{\rm TV}>0\enspace.$

On the other hand, if for all $i,j\in{\mathcal{A}}$ the above limit is zero,
then we have non-reconstruction.

The broadcasting process we describe above gives rise to well-known Gibbs
distributions on $T$ such as the Ising model, the Potts model etc. In terms of
the Gibbs distributions on the tree, the reconstruction problem can be
formulated as to whether the free-measure on the tree is extremal, or not. The
extremality here is considered with respect to whether the Gibbs distribution
can be expressed as a convex combination of two, or more measures, e.g. see
[20]. It is interesting to compare the extremality condition with various
spatial mixing conditions of the Gibbs distribution. Perhaps the most
interesting case is to compare it with the Gibbs tree uniqueness. Then, it is
standard to show that the extremality is a weaker condition than uniqueness.

The reconstruction problem has been studied since 1960s. Perhaps the most
general result in the area is the so-called Kesten-Stigum bound [24], or KS-
bound for short. Let $\Delta_{\rm KS}=\Delta_{\rm KS}(M)$ be such that

$\Delta_{\rm KS}=\lambda_{2}^{-2}(M)\enspace,$ (2)

where $\lambda_{2}(M)$ is the second largest, in magnitude, eigenvalue of the
transition matrix $M$. The result of [24] implies that if $\Delta>\Delta_{\rm
KS}$, then we have reconstruction.

In light of the above, a natural question is whether the condition
$\Delta<\Delta_{\rm KS}$ implies that we have non-reconstruction. In general,
the answer to this question is no, e.g. see [5, 29]. However, for several
important distributions, including the Ising model, the KS-bound is tight, in
the sense that the condition $\Delta<\Delta_{\rm KS}$ indeed implies non-
reconstruction, see [7, 18, 22].

###  1.2. Broadcasting with random matrices

Here, we consider the natural problem of broadcasting on a tree, where the
transition matrix is random. In this setting, as before, we consider the
$\Delta$-ary tree $T=(V,E)$, of height $h>0$, rooted at $r$. Also, we have a
finite set of spins ${\mathcal{A}}$. Rather than using the same matrix for
every edge of the tree, each edge has its own matrix, which is an independent
sample from a predefined distribution $\psi$.

More formally, every ${\mathcal{A}}\times{\mathcal{A}}$ stochastic matrix can
be viewed as a point in the ${|{\mathcal{A}}|^{2}}$ Euclidean space. We endow
the set of all ${\mathcal{A}}\times{\mathcal{A}}$ stochastic matrices with the
$\sigma$-algebra induced by the Borel algebra. Then, $\psi$ is a distribution
over the set of these matrices.

Once we have a matrix for each edge of $T$, the broadcasting proceeds with the
same rules as in the deterministic case. If for the non-leaf vertex $u$ in $T$
we have ${\mathbold{\sigma}}(u)=i$, then the vertex $w$, child of $u$, gets
${\mathbold{\sigma}}(w)=j$ with probability ${\mathbold{M}}_{e}(i,j)$,
independently of the other children of $u$, i.e.,

$\Pr[{\mathbold{\sigma}}(w)=j\ |\
{\mathbold{\sigma}}(u)=i]={\mathbold{M}}_{e}(i,j)\enspace,$

where $e=\\{u,w\\}$.

The above setting gives rise to a random probability measure on the set of
configurations ${\mathcal{A}}^{V}$ which we denote as
$\mathbold{\mu}=\mathbold{\mu}_{T,\psi}$. Hence, the configuration
${\mathbold{\sigma}}\in{\mathcal{A}}^{V}$ we get from the broadcasting,
consists of two-levels of randomness. The first level is due to the fact that
the measure $\mathbold{\mu}$ is induced by the random instances of the
broadcasting matrices $\\{{\mathbold{M}}_{e}\\}_{e\in E}$. Once these matrices
have been fixed, the second level of randomness emerges from the random
choices of the broadcasting process. The above formulation gives rise to well-
studied Gibbs distributions, such as the Edwards–Anderson model of spin-
glasses, by choosing appropriately the distribution $\psi$.

In this new setting, we study the reconstruction problem. Here, the definition
of reconstruction differs slightly from Definition 1.1 above. Denote with
$\mathbold{\mu}_{h}$ the marginal of $\mathbold{\mu}$ on the vertices at
distance $h$ from the root of the tree $T$. Then, the reconstruction problem
is defined as follows:

######  Definition 1.2.

For a distribution $\psi$ on ${\mathcal{A}}\times{\mathcal{A}}$ stochastic
matrices , we say that the random measure
$\mathbold{\mu}=\mathbold{\mu}_{T,\psi}$ exhibits reconstruction if there
exist spins $i,j\in{\mathcal{A}}$ such that

$\limsup_{h\to\infty}\mathbb{E}\left[\left|\left|\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=i)-\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=j)\right|\right|_{\rm TV}\right]>0\enspace,$

where the expectation is with respect to the randomness of $\mathbold{\mu}$.

On the other hand, if for all $i,j\in{\mathcal{A}}$ the above limit is zero,
then we have non-reconstruction.

We consider the reconstruction problem in terms of the KS-bound, i.e., we
examine whether it is tight, or not. Before addressing this question, we need
to specify what the parameter $\Delta_{\rm KS}$ might be in this setting.

It turns out that a natural candidate for $\Delta_{\rm KS}$ can be defined as
follows: Let ${\mathbold{M}}$ be a matrix sampled from the distribution
$\psi$, and define

$\Xi=\mathbb{E}\left[{\mathbold{M}}\otimes{\mathbold{M}}\right]\enspace,$ (3)

i.e., the matrix $\Xi$ is the expectation of the tensor product of the matrix
${\mathbold{M}}$ with itself. Let ${\bf 1}\in\mathbb{R}^{{\mathcal{A}}}$
denote the vector whose entries are all equal to one. Also, write

${\mathcal{E}}=\left\\{z\in\mathbb{R}^{{\mathcal{A}}}\otimes\mathbb{R}^{{\mathcal{A}}}:\forall
y\in\mathbb{R}^{{\mathcal{A}}}\ \langle z,{\bf 1}\otimes y\rangle=\langle
z,y\otimes{\bf 1}\rangle=0\right\\}\enspace,$

where $\langle\cdot,\cdot\rangle$ is the standard inner product operation.
Then, we define $\Delta_{\rm KS}(\psi)$ to be such that

$\Delta_{\rm
KS}(\psi)=\left(\max_{x\in{\mathcal{E}}:\left|\left|x\right|\right|=1}\langle\Xi
x,x\rangle\right)^{-1}\enspace.$ (4)

The above quantity, $\Delta_{\rm KS}$, arises in the study of phases
transitions in random CSPs [12]. Specifically, it signifies an upper bound on
the density of the so-called Replica Symmetric phase, of symmetric Gibbs
distributions. The value $\Delta_{\rm KS}$ is derived in [12] by means of a
stability analysis of the so-called free-energy functional. Note that the
above definition for $\Delta_{\rm KS}(\psi)$ applies to any set of spins
${\mathcal{A}}$, and any distribution $\psi$ on
${\mathcal{A}}\times{\mathcal{A}}$ matrices.

Here, we prove that the above is indeed the analogue of KS-bound for
symmetric, 2-spin distributions $\mathbold{\mu}$ (including the EA model).
That is, for any distribution $\psi$ over the broadcasting matrices whose
support is comprised of symmetric $2\times 2$ matrices, we prove that the
$\Delta$-ary tree $T$ exhibits reconstruction when $\Delta>\Delta_{\rm
KS}(\psi)$, while we have non-reconstruction when $\Delta<\Delta_{\rm
KS}(\psi)$.

Furthermore, we go beyond the basic case of the $\Delta$-ary tree. Firstly, we
extend our results to the cases where the underlying graph is the Galton-
Watson random tree with general offspring distribution. Secondly, we exploit
the notion of contiguity of measures to derive non-reconstruction results for
the Edwards-Anderson model on the random graph $\mathbold{G}(n,d/n)$.

##  2\. Results

We start the presentation of our results on the 2-spin, symmetric
distributions, by considering the $\Delta$-ary tree. Specifically, for
integers $\Delta>0$ and $h>0$, let $T=(V,E)$ be the $\Delta$-ary tree of
height $h$, rooted at vertex $r$. We let ${\mathcal{A}}=\\{\pm 1\\}$ be the
set of spins.

Suppose that we have a broadcasting process on $T$, while assume that each
edge of the tree is equipped with its own broadcasting matrix, each matrix
drawn independently from the distribution induced by the following experiment:
We have two parameters, a real number $\beta>0$, and a distribution $\phi$ on
the real numbers $\mathbb{R}$, i.e., we have the probability space
$(\mathbb{R},{\mathcal{F}},\phi)$ where ${\mathcal{F}}$ is the
$\sigma$-algebra induced by the Borel algebra. We generate a matrix
${\mathbold{M}}$ following the two steps below:

Step 1:

Draw ${\mathbold{J}}\in\mathbb{R}$ from the distribution $\phi$.

Step 2:

Generate the ${\mathcal{A}}\times{\mathcal{A}}$ matrix ${\mathbold{M}}$ such
that

$\displaystyle{\mathbold{M}}$
$\displaystyle=\frac{1}{\exp(\beta{\mathbold{J}})+1}\left[\begin{array}[]{cc}\exp(\beta{\mathbold{J}})&1\\\
\vspace{-.3cm}\hfil\\\ 1&\exp(\beta{\mathbold{J}})\end{array}\right]\enspace.$
(8)

Note that our broadcasting matrices are always symmetric.

The above broadcasting process gives rise to configurations in
${\mathcal{A}}^{V}$ following the Gibbs distribution
$\mathbold{\mu}_{\beta,\phi}$ specified as follows: Let
$\\{{\mathbold{J}}_{e}\\}_{e\in E}$ be independent, identically distributed
(i.i.d.) random variables such that each one of them is distributed as in
$\phi$ (this is the same distribution used to generate matrix
${\mathbold{M}}$). Each $\sigma\in{\mathcal{A}}^{V}$ is assigned probability
mass $\mathbold{\mu}_{\beta,\phi}(\sigma)$ defined by

$\mathbold{\mu}_{\beta,\phi}(\sigma)\propto\textstyle\exp\left(\beta\sum_{\\{w,u\\}\in
E}{\bf
1}\\{\sigma(u)=\sigma(w)\\}\cdot{\mathbold{J}}_{\\{u,w\\}}\right)\enspace,$
(9)

where $\propto$ stands for “proportional to”.

At this point, it is immediate that by choosing $\phi$ to be the standard
Gaussian distribution, we retrieve the Edwards-Anderson model in (1). Note
however, that (9) above generates a whole family of “spin-glass” distributions
with the EA-model being a special case.

The definition of the distribution of the broadcasting matrix in (8) allows us
to derive an explicit formula for the quantity $\Delta_{\rm KS}$ in (4).
Specifically, for ${\mathbold{J}}$ distributed according to $\phi$, it is not
hard to prove (see Appendix B) that

$\Delta_{\rm
KS}(\beta,\phi)=\textstyle\left(\mathbb{E}\left[\left(\frac{1-\exp(\beta{\mathbold{J}})}{1+\exp(\beta{\mathbold{J}})}\right)^{2}\right]\right)^{-1}\enspace,$
(10)

where the expectation is with respect to the random variable ${\mathbold{J}}$.
In light of the above, we prove the following result for the general Gibbs
distribution.

######  Theorem 2.1.

For a real number $\beta>0$, and a distribution $\phi$ on the real numbers
$\mathbb{R}$ let $\Delta_{\rm KS}=\Delta_{\rm KS}(\beta,\phi)$ be defined as
in (10).

For any integer $\Delta>\Delta_{\rm KS}$, the Gibbs distribution
$\mathbold{\mu}_{\beta,\phi}$, defined as in (9), on the $\Delta$-ary tree
exhibits reconstruction. On the other hand, if $\Delta<\Delta_{\rm KS}$ the
distribution $\mathbold{\mu}_{\beta,\phi}$ exhibits non-reconstruction.

The proof of Theorem 2.1 appears in Section 5. Let us state the implications
of Theorem 2.1 for the Edwards-Anderson model on the $\Delta$-ary tree.

######  Corollary 2.2.

For $\beta>0$ and the standard Gaussian ${\mathbold{J}}$, let

$\Delta_{\rm
EA}(\beta)=\textstyle\left(\mathbb{E}\left[\left(\frac{1-\exp(\beta{\mathbold{J}})}{1+\exp(\beta{\mathbold{J}})}\right)^{2}\right]\right)^{-1}\enspace,$

where the expectation is with respect to ${\mathbold{J}}$.

For any integer $\Delta>\Delta_{\rm EA}(\beta)$, the distribution
$\mathbold{\mu}_{\beta}$, the Edwards-Anderson model with inverse temperature
$\beta$ on the $\Delta$-ary tree, exhibits reconstruction. On the other hand,
if $\Delta<\Delta_{\rm EA}(\beta)$ the distribution $\mathbold{\mu}_{\beta}$
exhibits non-reconstruction.

###  2.1. The case of the Galton-Watson tree

As a further step, we study the reconstruction problem on the Galton-Watson
tree. Even though this is a very interesting problem on its own, we make use
of our results for the Galton-Watson tree to derive subsequent results for
$\mathbold{G}(n,d/n)$, see Section 2.2.

Let $\zeta:\mathbb{Z}_{\geq 0}\to[0,1]$ be a distribution over the non-
negative integers. Then, the rooted tree $\mathbold{T}$ is a Galton-Watson
tree with offspring distribution $\zeta$, if the number of children for each
vertex in $\mathbold{T}$ is distributed according to $\zeta$, independently
from the other vertices.

Note that broadcasting with random matrices over the Galton-Watson tree
$\mathbold{T}$, gives rise to configurations that consist of three levels of
randomness. One of the challenges we circumvent with our analysis, is to
disentangle all of three levels of randomness, and make clear the contribution
of each one of them. Before getting there, we need to clarify what we mean by
(non-)reconstruction in the current setting.

######  Definition 2.3.

Consider the distributions $\phi$ over $\mathbb{R}$ and $\zeta$ over
$\mathbb{Z}_{\geq 0}$, and a real number $\beta\geq 0$. Let the Galton-Watson
tree $\mathbold{T}$ with offspring distribution $\zeta$, while let the measure
$\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$ be defined as in (9), on the tree
$\mathbold{T}$. We say that $\mathbold{\mu}$ exhibits reconstruction if

$\limsup_{h\to\infty}\mathbb{E}_{\mathbold{T}}\left[\
\mathbb{E}_{\mathbold{\mu}}\left[\left|\left|\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=+1)-\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=-1)\right|\right|_{\rm TV}\ |\ \mathbold{T}\right]\
\right]>0\enspace.$

On the other hand, if the above limit is zero, then we have non-
reconstruction.

For the above, recall that $\mathbold{\mu}_{h}$ is the marginal of
$\mathbold{\mu}$ on the set of vertices at distance $h$ from the root. Note
that if $\mathbold{T}$ has no vertex at level $h$, then the total variation
distance above is, degenerately, equal to zero. We use the double expectation
in Definition 2.3 for the sake of clarity: we can just replace it by a single
expectation with respect to both the random tree $\mathbold{T}$, and the
random measure $\mathbold{\mu}$.

As far as the reconstruction problem on the Galton-Watson trees is concerned,
we have the following result, which we prove in Section 8.

######  Theorem 2.4.

For any real numbers $d>0,\beta>0$, for any distribution $\phi$ on
$\mathbb{R}$, for any distribution $\zeta$ on $\mathbb{Z}_{\geq 0}$ with
expectation $d$ and bounded second moment, let $\mathbold{T}$ be the Galton-
Watson tree with offspring distribution $\zeta$. Let also
$\mathbold{\mu}_{\beta,\phi}$ be the Gibbs distribution defined as in (9), on
the tree $\mathbold{T}$. Finally, let $\Delta_{\rm KS}=\Delta_{\rm
KS}(\beta,\phi)$ be defined as in (10).

The distribution $\mathbold{\mu}_{\beta,\phi}$ exhibits reconstruction if
$d>\Delta_{\rm KS}$. On the other hand, if $d<\Delta_{\rm KS}$, the
distribution $\mathbold{\mu}_{\beta,\phi}$ exhibits non-reconstruction.

Let us now state the implications of Theorem 2.4 for the Edwards-Anderson
model on the Galton-Watson tree.

######  Corollary 2.5.

For $\beta>0$, consider the quantity $\Delta_{\rm EA}(\beta)$ defined in
Corollary 2.2. For any real number $d>0$, and any distribution
$\zeta:\mathbb{Z}_{\geq 0}\to[0,1]$ with expectation $d$, and bounded second
moment, let $\mathbold{T}$ be the Galton-Watson tree with offspring
distribution $\zeta$.

Then, for $\mathbold{\mu}_{\beta}$ the Edwards-Anderson model with inverse
temperature $\beta$, on the tree $\mathbold{T}$, the following is true. The
distribution $\mathbold{\mu}_{\beta}$ exhibits reconstruction if
$d>\Delta_{\rm EA}(\beta)$. On the other hand, if $d<\Delta_{\rm EA}(\beta)$,
the distribution $\mathbold{\mu}_{\beta}$ exhibits non-reconstruction.

###  2.2. The Edwards-Anderson model on $\mathbold{G}(n,d/n)$

For integer $n\geq 1$, and real $p\in[0,1]$, let
$\mathbold{G}=\mathbold{G}(n,p)$ be the random graph on
$V_{n}=\\{x_{1},\ldots,x_{n}\\}$, whose edge set $E(\mathbold{G})$ is obtained
by including each edge with probability, $p$ independently.

The Edwards-Anderson model on $\mathbold{G}$ at inverse temperature $\beta>0$,
is defined as follows: for ${\mathbold{J}}=\\{{\mathbold{J}}_{e}\\}_{e\in
E(\mathbold{G})}$ a family of independent standard Gaussians, we let

$\mu_{\mathbold{G},{{\mathbold{J}}},\beta}(\sigma)\textstyle=\frac{1}{Z_{\beta}(\mathbold{G},{\mathbold{J}})}\exp\left(\beta\sum_{x\sim
y}{\bf
1}\\{\sigma(y)=\sigma(x)\\}\cdot{\mathbold{J}}_{\\{x,y\\}}\right)\enspace,$
(11)

where

$Z_{\beta}(\mathbold{G},{{\mathbold{J}}})\textstyle=\sum_{\tau\in\\{\pm
1\\}^{V_{n}}}\exp\left(\beta\sum_{x\sim y}{\bf
1}\\{\tau(y)=\tau(x)\\}\cdot{\mathbold{J}}_{\\{x,y\\}}\right)\enspace.$

Here we assume that $p=\frac{d}{n}$, where $d>0$ is a fixed number. Typically,
we study this distribution as $n\to\infty$. The natural question we ask here
is how does the model change as we vary $d$. According to the physics
predictions, for any $\beta$ there exists a condensation threshold, denoted as
$d_{\rm cond}(\beta)$, where the function

$d\mapsto\lim_{n\to\infty}\frac{1}{n}\mathbb{E}[\ln
Z_{\beta}(\mathbold{G},{{\mathbold{J}}})]$

is non-analytic [19]. This conjecture was proved by Guerra and Toninelli [21].
The regime $d<d_{\rm cond}(\beta)$ is called the replica symmetric phase. This
region has several interesting properties; here we consider one that seems to
be most relevant to our discussion. For any $d<d_{\rm cond}(\beta)$ the
distribution $\mu_{\mathbold{G},{\mathbold{J}},\beta}$ satisfies the following
property: for ${\mathbold{\sigma}}$ distributed as in
$\mu_{\mathbold{G},{\mathbold{J}},\beta}$, for two randomly chosen vertices
${\bf x}$ and ${\bf y}$, the configurations ${\mathbold{\sigma}}({\bf x})$ and
${\mathbold{\sigma}}({\bf y})$ are asymptotically independent. Formally, the
above can be expressed as follows: for $d<d_{\rm cond}(\beta)$ and any
$i,j\in\\{\pm 1\\}$, we have that

$\limsup_{n\to\infty}\frac{1}{n^{2}}\sum_{x,y\in
V_{n}}\mathbb{E}\left[\left\langle{\bf
1}\\{{\mathbold{\sigma}}(x)=i\\}\times{\bf
1}\\{{\mathbold{\sigma}}(y)=j\\}\right\rangle-\left\langle{\bf
1}\\{{\mathbold{\sigma}}(x)=i\\}\right\rangle\times\left\langle{\bf
1}\\{{\mathbold{\sigma}}(y)=j\\}\right\rangle\right]=0\enspace,$

where $\left\langle\cdot\right\rangle$ denotes expectation with respect to the
Gibbs distribution $\mu_{\mathbold{G},{\mathbold{J}},\beta}$. Note that the
above holds not only for pairs of vertices, but also for sets of $k$ vertices,
for any fixed integer $k>0$. Using our notation, the work by Guerra and
Toninelli [21] implies the following result.

######  Theorem 2.6 ([21]).

For any $\beta>0$, for the distribution
$\mu_{\mathbold{G},{\mathbold{J}},\beta}$ defined as in (11), we have that

$\displaystyle d_{\rm cond}(\beta)$
$\displaystyle=\textstyle\left(\mathbb{E}\left[\left(\frac{1-\exp(\beta{\mathbold{J}})}{1+\exp(\beta{\mathbold{J}})}\right)^{2}\right]\right)^{-1}\enspace,$

where ${\mathbold{J}}$ is a standard Gaussian random variable.

Interestingly, one obtains the above by combining our Theorem 2.4 and using
standard results from [12, 13]. Our main focus is on the reconstruction
threshold for the Edwards-Anderson model on $\mathbold{G}$. The reconstruction
for $\mu_{\mathbold{G},{\mathbold{J}},\beta}(\cdot)$ is defined in a slightly
different way than what we have for the random tree.

######  Definition 2.7.

For $d>0$, for $\beta>0$, consider the Gibbs distribution
$\mu_{\mathbold{G},{\mathbold{J}},\beta}$ as this is defined in (11). We say
that the measure $\mu=\mu_{\mathbold{G},{\mathbold{J}},\beta}$ exhibits
reconstruction if

$\displaystyle\limsup_{h\to\infty}\lim_{n\to\infty}\frac{1}{n}\sum_{x\in
V_{n}}\mathbb{E}\left[\left|\left|\mu_{x,h}(\cdot\ |\
{\mathbold{\sigma}}(x)=+1)-\mu_{x,h}(\cdot\ |\
{\mathbold{\sigma}}(x)=-1)\right|\right|_{\rm TV}\ \right]>0\enspace,$

where $\mu_{x,h}$ denote the Gibbs marginal at the vertices at distance $h$
from vertex $x$. On the other hand, if the above limit is zero, then we have
non-reconstruction.

Perhaps, it is interesting to notice the order with which we take the double
limit in the above definition.

Furthermore, we let the reconstruction threshold, denoted as $d_{\rm recon}$,
to be the infimum over $d>0$ such that

$\displaystyle\limsup_{h\to\infty}\lim_{n\to\infty}\frac{1}{n}\sum_{x\in
V_{n}}\mathbb{E}\left[\left|\left|\mu_{h}(\cdot\ |\
{\mathbold{\sigma}}(x)=+1)-\mu_{h}(\cdot\ |\
{\mathbold{\sigma}}(x)=-1)\right|\right|_{\rm TV}\ \right]>0\enspace.$

The region of values of $d$ such that $d<d_{\rm recon}$ is called the non-
reconstruction phase. It is immediate from Definition 2.7 that, for any
$d<d_{\rm recon}$, we have that non-reconstruction.

In the following result, we prove that the replica symmetric phase coincides
with the non-reconstruction phase of the Edwards-Anderson model on
$\mathbold{G}$.

######  Theorem 2.8.

For any $\beta>0$, for the distribution
$\mu_{\mathbold{G},{\mathbold{J}},\beta}$ defined as in (11), we have that
$d_{\rm recon}(\beta)=d_{\rm cond}(\beta)$.

The above follows from Theorems 2.6, 2.5 and [12, Corollary 1.5].

#### Notation

For the graph $G=(V,E)$ and the Gibbs distribution $\mu$ on the set of
configurations $\\{\pm 1\\}^{V}$. For a configuration $\sigma$, we let
$\sigma(\Lambda)$ denote the configuration that $\sigma$ specifies on the set
of vertices $\Lambda$. We let $\mu_{\Lambda}$ denote the marginal of $\mu$ at
the set $\Lambda$. We let $\mu(\cdot\ |\ \Lambda,\sigma)$, denote the
distribution $\mu$ conditional on the configuration at $\Lambda$ being
$\sigma$. Also, we interpret the conditional marginal $\mu_{\Lambda}(\cdot\ |\
\Lambda^{\prime},\sigma)$, for $\Lambda^{\prime}\subseteq V$, in the natural
way.

##  3\. Approach

A major challenge in our setting is that we have to deal with multiple levels
of randomness, i.e., we have two levels of randomness in the case of the
$\Delta$-ary tree, while the levels increase with the Galton-Watson trees or
$\mathbold{G}(n,d/n)$. To circumvent this problem, we follow an analysis that
allows us to disentangle the different sources of randomness in our models. In
this section, we provide a high-level description of our approach. We restrict
our discussion on the $\Delta$-ary tree.

### Non-reconstruction

Consider the $\Delta$-ary tree $T=(V,E)$ rooted at $r$. Suppose that we have a
distribution $\mu$ as in (9) on $T$, while assume that each edge $e\in E$ has
its own coupling parameter $J_{e}$. Assume, for the moment, that the coupling
parameters at the edges are fixed, e.g. the reader may assume that are
arbitrary real numbers. That is, each $J_{e}$ can be either positive, or
negative. Hence, one might consider the aforementioned distribution as a non-
homogenous Ising model which involves both ferromagnetic and anti-
ferromagnetic interactions. Let us focus on non-reconstruction. We derive an
upper bound on

$\left|\left|\mu_{h}(\cdot\ |\ {\mathbold{\sigma}}(r)=+1)-\mu_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=-1)\right|\right|_{\rm TV}\enspace,$

which is expressed in terms of the influence between neighbouring vertices.
The notion of influence between vertices is the same as the one developed in
the context of Spectral Independence technique for establishing rapid mixing
of Glauber dynamics [3, 9]. These influences are used in the context of the
so-called down-up coupling to establish non-reconstruction. This is a coupling
approach from [6], which also relies on ideas in [29].

Let us be more specific. For the probability measure $\mu$ we consider, let
$R_{r}$ be the ratio of Gibbs marginals at the root $r$ defined by

$R_{r}=\frac{\mu_{r}(+1)}{\mu_{r}(-1)}\enspace.$ (12)

Recall that $\mu_{r}(\cdot)$ denotes the marginal of the Gibbs distribution
$\mu(\cdot)$ at the root $r$.

For a vertex $u\in V$, we let $T_{u}$ be the subtree of $T$ that includes $u$,
and all its descendants. Also, we let $R_{u}$ be the ratio of marginals at
vertex $u$, where the Gibbs distribution is, now, with respect to the subtree
$T_{u}$.

Suppose that the vertices $w_{1},\ldots,w_{\Delta}$ are the children of the
root $r$. Our focus is on expressing $\log R_{r}$ recursively, as a function
of $\log R_{w_{1}},\ldots,\log R_{w_{\Delta}}$. Note that we study the
logarithm of the ratios involved, which can be viewed as applying the
potential function $\log(\cdot)$ to the tree recursions. We have that
$\log\left(R_{r}\right)=H\left(\log R_{w_{1}},\ldots,\log
R_{w_{\Delta}}\right)$ where

$H(x_{1},x_{2},\ldots,x_{\Delta})=\sum^{\Delta}_{i=1}\log\left(\frac{\exp\left(x_{i}+\beta
J_{\\{r,w_{i}\\}}\right)+1}{\exp(x_{i})+\exp\left(\beta
J_{\\{r,w_{i}\\}}\right)}\right)\enspace.$ (13)

Note that $J_{\\{r,w_{i}\\}}$ is the coupling parameter that corresponds to
the edge between the root $r$ with its child $w_{i}$.

All the above extends naturally in the case where we impose boundary
conditions. That is, for a region $K\subseteq V$, and $\tau\in\\{\pm
1\\}^{K}$, we define the ratio of marginals $R^{K,\tau}_{r}$ at the root,
where now the ratio is between the conditional marginals $\mu_{r}(+1\ |\
K,\tau)$ and $\mu_{r}(-1\ |\ K,\tau)$. The recursive function $H$ for the
conditional ratios is exactly the same as the one above.

Our interest is on the gradient of the function $H$. Specifically, for every
$i\in[\Delta]$, we let

$\Gamma_{\\{r,w_{i}\\}}=\sup_{x_{1},\ldots,x_{\Delta}}\left|\frac{\partial}{\partial
x_{i}}H(x_{1},x_{2},\ldots,x_{\Delta})\right|\enspace.$ (14)

It turns out that, in our case, $\Gamma_{\\{r,w_{i}\\}}$ has a simple form

$\Gamma_{\\{r,w_{i}\\}}=\frac{\left|1-\exp\left(\beta
J_{\\{r,w\\}}\right)\right|}{1+\exp\left(\beta
J_{\\{r,w_{i}\\}}\right)}\enspace.$

Utilising the idea of down-up coupling from [6], we prove the following:

$\left|\left|\mu_{h}(\cdot\ |\ {\mathbold{\sigma}}(r)=+1)-\mu_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=-1)\right|\right|_{\rm
TV}\leq\sqrt{\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\Gamma_{e}^{2}}\enspace,$
(15)

where $\Lambda=\Lambda(h)$ denotes the set of vertices at distance $h$ from
the root $r$. Note that the above provides a bound for the total variation
distance of the the marginals for fixed, i.e., non-random, couplings
$\\{J_{e}\\}_{e\in E}$. Inequality (15), extends naturally when we study
reconstruction for the distribution $\mathbold{\mu}$ defined in (9), i.e.,
when the coupling parameters ${\mathbold{J}}_{e}$ are i.i.d. samples from a
distribution $\phi$. Indeed, averaging yields

$\mathbb{E}\left[\left(\left|\left|\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=+1)-\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=-1)\right|\right|_{\rm
TV}\right)^{2}\right]\leq\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\mathbb{E}\left[\mathbold{\Gamma}_{e}^{2}\right]\enspace,$
(16)

where we have
$\mathbold{\Gamma}_{e}=\frac{\left|1-\exp\left(\beta{\mathbold{J}}_{e}\right)\right|}{1+\exp\left(\beta{\mathbold{J}}_{e}\right)}$,
for each $e\in E$. Note that the above holds, since each
$\mathbold{\Gamma}_{e}$ depends only on ${\mathbold{J}}_{e}$, while the
coupling parameters ${\mathbold{J}}_{e}$ are assumed to be independent with
each other.

At this point, and since the ${\mathbold{J}}_{e}$’s are identically
distributed, we further observe that for any $e\in E$, we have that

$\Delta_{\rm
KS}(\beta,\phi)=\left(\mathbb{E}\left[\mathbold{\Gamma}_{e}^{2}\right]\right)^{-1}\enspace.$

Since the underlying tree $T$ is $\Delta$-ary, it is immediate to see that for
$\Delta<\Delta_{\rm KS}(\beta,\phi)$, the r.h.s. of (16) tends to zero as
$h\to\infty$. From this point on, it is standard to prove non-reconstruction.

Our analysis allows to deal with the randomness of the spin-glass measure
$\mathbold{\mu}$ by utilising the bound in (15). That is, the upper bound on
the total variation distance has a nice product form of the quantities
$\Gamma_{e}$, which, in turn, expresses the dependence of the total variation
distance on the edge couplings $\\{J_{e}\\}_{e\in E}$. This product form of
the bound, behaves rather nicely when we need to take averages over the
randomness of the coupling parameters $\\{{\mathbold{J}}_{e}\\}_{e\in E}$ of
the the spin-glass measure $\mathbold{\mu}$.

### Reconstruction

In the reconstruction regime, the configuration at the root has a non-
vanishing effect on the configuration of the vertices at distance $h$,
regardless of the height $h$. Specifically, the corresponding leaf
configurations from the measure conditioned on root’s spin being $+1$, and
$-1$, are so different with each other, that any discrepancies cannot be
attributed to random fluctuations. Therefore, a question that naturally arises
is how can we take advantage of the discrepancies so that we infer the spin of
the root.

For the standard ferromagnetic Ising, several approaches have been developed
to establish reconstruction (see [18], [8], [23]). Here, we build on an
elegant argument in [18]. The authors in this work, show that a simple
majority vote of the leaf spins, conveys information sufficient to reconstruct
root’s spin, The majority vote on the leaves is defined by

$M_{h}=\sum_{u\in\Lambda}\sigma(u)\enspace.$ (17)

The estimation rule is to infer that the spin at the root is ${\rm
sgn}\\{M_{h}\\}$, i.e., the sign of $M_{h}$. Impressively, it turns out that
this estimator is optimal, i.e., it coincides with the maximum likelihood one.
For the $\Delta$-ary tree, one establishes reconstruction for the
ferromagnetic Ising model by employing a second moment argument on the
estimator $M_{h}$.

For the distributions we consider here, the above estimator is far from
sufficient. This is due to various facts. Firstly, we allow for mixed
couplings on the edges, i.e., certain edges can be ferromagnetic, and others
can be anti-ferromagnetic. Secondly, the strength of the interaction, i.e.,
the magnitude of ${\mathbold{J}}_{e}$’s, is expected to vary from one edge to
the other. To this end, we introduce a new estimator, and we establish
reconstruction by building on the second moment argument from [18]. The
starting point towards deriving this estimator, comes from just considering
the standard anti-antiferromagnetic Ising. The statistic from (17), clearly
does not work for this distribution. However, there is an easy remedy, by
taking into account the parity of the height $h$, i.e., if $h$ is an even, or
an odd number. We infer that the spin at the root is equal to ${\rm
sgn}\left\\{\widehat{M}_{h}\right\\}$, where

$\widehat{M}_{h}=(-1)^{h}\sum_{u\in\Lambda}\sigma(u)\enspace.$

For the spin-glass distributions we consider here, we need to get the above
idea even further. Firstly, in order to accommodate the mixed ferromagnetic
and anti-ferromagnetic couplings on the edges of the tree. It seems meaningful
to use the estimator ${\rm sgn}\left\\{\widetilde{M}_{h}\right\\}$ for the
root configuration, where

$\widetilde{M}_{h}=\sum_{u\in\Lambda}\sigma(u)\prod_{e\in{\rm path}(r,u)}{\rm
sign}\\{{\mathbold{J}}_{e}\\}\enspace,$

with ${\rm path}(r,u)$ denoting the set of edges along the unique path
connecting $r$ to $u$. So that in $\widetilde{M}_{h}$, for each leaf we
essentially examine the parity of the number of antiferromagnetic couplings
along the path that connects it to the root. Unfortunately, for the above
estimator, our second moment argument does not seem to work all that well.

The estimator we end up using, is a reweighted version of $\widetilde{M}_{h}$,
which we call the “flip majority” vote, and is defined by

${F}_{h}=\sum_{u\in\Lambda}\sigma(u)\prod_{e\in{\rm
path}(r,u)}{\textstyle\frac{1-\exp\left(\beta{\mathbold{J}}_{e}\right)}{1+\exp\left(\beta{\mathbold{J}}_{e}\right)}}\enspace.$

Note that the absolute value of the weight for the edge $e$, above, coincides
with the quantity $\mathbold{\Gamma}_{e}$ in (16). Naturally, the estimation
rule is to infer that the root spin is ${\rm sgn}\left\\{F_{h}\right\\}$.

##  4\. Tree recursions and Influences

What follows applies to any kind of tree. For the sake of simplicity, in this
section, we consider the $\Delta$–ary tree $T=(V,E)$ rooted at $r$. Suppose
that we are given the number $\beta\geq 0$, while each edge $e\in E$ has its
own coupling parameter, $J_{e}$. Assume, for the moment, that the coupling
parameters at the edges are fixed, i.e., they are arbitrary real numbers.
Given $\beta$ and $\\{J_{e}\\}_{e\in E}$, we consider the Gibbs distribution
$\mu=\mu_{\beta,\\{J_{e}\\}}$ similarly to the one we have in (9). That is,
every $\sigma\in\\{\pm 1\\}^{V}$ gets a probability mass defined by

$\displaystyle\mu(\sigma)$
$\displaystyle\propto\textstyle\exp\left(\beta\cdot\sum_{\\{w,u\\}\in E}{\bf
1}\\{\sigma(u)=\sigma(w)\\}\cdot J_{\\{u,w\\}}\right)\enspace.$ (18)

For a region $K\subseteq V\setminus\\{r\\}$ and $\tau\in\\{\pm 1\\}^{K}$, we
consider the ratio of marginals at the root $R^{K,\tau}_{r}$ such that

$\displaystyle R^{K,\tau}_{r}=\frac{\mu_{r}(+1\ |\ K,\tau)}{\mu_{r}(-1\ |\
K,\tau)}\enspace.$ (19)

Recall that $\mu_{r}(\cdot\ |\ K,\tau)$ denotes the marginal of the Gibbs
distribution $\mu(\cdot\ |\ K,\tau)$ at the root $r$. Also, note that the
above allows for $R^{K,\tau}_{r}=\infty$, when $\mu_{r}(-1\ |\ K,\tau)=0$.

For a vertex $u\in V$, we let $T_{u}$ be the subtree of $T$ that includes $u$,
and all its descendants. We always assume that the root of $T_{u}$ is the
vertex $u$. With a slight abuse of notation, we let $R^{K,\tau}_{u}$ denote
the ratio of marginals at the root for the subtree $T_{u}$, where the Gibbs
distribution is, now, with respect to $T_{u}$.

Suppose that the root $r$ is of degree $\Delta>0$, while let the vertices
$w_{1},\ldots,w_{\Delta}$ be its children. We express $R^{K,\tau}_{r}$ it
terms of $R^{K,\tau}_{w_{i}}$’s by having
$R^{K,\tau}_{r}=F_{\Delta}(R^{K,\tau}_{w_{1}},R^{K,\tau}_{w_{2}},\ldots,R^{K,\tau}_{w_{\Delta}})$,
for

$\displaystyle F_{\Delta}:[0,+\infty]^{\Delta}\to[0,+\infty]$ such that
$\displaystyle(x_{1},\ldots,x_{\Delta})\mapsto\prod^{\Delta}_{i=1}\frac{\exp(\beta
J_{\\{r,w_{i}\\}}){x}_{i}+1}{{x}_{i}+\exp(\beta J_{\\{r,w_{i}\\}})}\enspace.$

For the analysis that follows, we get cleaner results by equivalently working
with log-ratios rather than ratios of Gibbs marginals. Let
$H_{\Delta}=\log\circ F_{\Delta}\circ\exp$, which means that
$H_{\Delta}:[-\infty,+\infty]^{\Delta}\to[-\infty,+\infty]$ is such that

$\displaystyle\textstyle(x_{1},\ldots,x_{\Delta})\mapsto\sum^{\Delta}_{i=1}\log\left(\frac{\exp(\beta
J_{\\{r,w_{i}\\}}+x_{i})+1}{\exp(x_{i})+\exp(\beta
J_{\\{r,w_{i}\\}})}\right)\enspace.$

From the above, it is elementary to verify that $\log
R^{K,\tau}_{r}=H_{\Delta}(\log R^{K,\tau}_{w_{1}},\ldots,\log
R^{K,\tau}_{w_{\Delta}})$. The above transformation is standard in the
literature, and can be viewed as applying the potential function $\log(\cdot)$
in the tree recursion. For every $i\in[\Delta]$, we let

$\displaystyle\Gamma_{\\{r,w_{i}\\}}$
$\displaystyle=\sup_{x_{1},\ldots,x_{\Delta}}\left|\frac{\partial}{\partial
x_{i}}H(x_{1},x_{2},\ldots,x_{\Delta})\right|\enspace.$ (20)

The quantities $\\{\Gamma_{e}\\}_{e\in E}$ arise naturally in various settings
in our analysis. Specifically, we use the theorem below, which follows as
corollary from results in [3, 9].

######  Theorem 4.1.

For $\beta>0$, consider the tree $T=(V,E)$ and $\\{J_{e}\\}_{e\in E}$ for
fixed $J_{e}\in\mathbb{R}$. Let the Gibbs distribution
$\mu=\mu_{\beta,\\{J_{e}\\}}$ on $T$, defined as in (18).

For any two vertices $u,w\in V$, for any $M\subseteq V\setminus\\{u,w\\}$, and
any $\tau\in\\{\pm 1\\}^{M}$ the following holds:

$\displaystyle\left|\left|\mu_{w}(\cdot\ |\ (M,\tau),(u,+1))-\mu_{w}(\cdot\ |\
(M,\tau),(u,-1))\right|\right|_{\rm TV}$
$\displaystyle\leq\prod_{e\in\mathrm{path}(u,w)}\Gamma_{e}\enspace,$ (21)

where $\mathrm{path}(u,w)$ is the set of edges along the path from $u$ to $w$
in $T$, while $\Gamma_{e}$’s are defined in (20).

Specifically, Theorem 4.1 is a direct consequence of Lemma B.2 in [3], and
Lemma 15 in [9]. For the distributions we consider in this work, it turns out,
that the quantities $\Gamma_{\\{r,w_{i}\\}}$ have a simple form which,
somehow, is a reminiscent of the quantity $\Delta_{\rm KS}$ in (10).

######  Claim 4.2.

For $e=\\{r,w_{i}\\}\in E$, consider the quantity $\Gamma_{e}$ defined in
(20). We have that

$\displaystyle\Gamma_{e}=\frac{\left|1-\exp\left(\beta
J_{e}\right)\right|}{1+\exp\left(\beta J_{e}\right)}\enspace.$ (22)

###### Proof of Claim 4.2.

The derivations below are standard and we present them for the sake of our
work being self-contained. For $i\in[\Delta]$ and $e=\\{r,w_{i}\\}$, let
$h_{i}:[-\infty,+\infty]\to\mathbb{R}$ be the function

$\displaystyle x\mapsto-\frac{(1-\exp(2\beta J_{e}))\cdot\exp(x)}{(\exp(\beta
J_{e}+x)+1)(\exp(x)+\exp(\beta J_{e}))}\enspace.$

It is easy to verify that $\frac{\partial}{\partial
x_{i}}H_{\Delta}(x_{1},\ldots,x_{\Delta})=h_{i}(x_{i})$. It is also
straightforward to see that for any real function $f$ we have

$\sup_{x}|f(x)|=\textstyle\max\left\\{\left|\sup_{x}f(x)\right|,\left|\inf_{x}f(x)\right|\right\\}\enspace,$

so that

$\Gamma_{e}=\sup_{x_{1},\ldots,x_{d}}\left|\frac{\partial}{\partial
x_{i}}H(x_{1},x_{2},\ldots,x_{d})\right|=\sup_{x}|h_{i}(x)|=\max\left\\{\left|\sup_{x}h_{i}(x)\right|,\left|\inf_{x}h_{i}(x)\right|\right\\}\enspace.$
(23)

Now let also $b_{i}=\exp(\beta J_{e})>0$, so that

$h_{i}(x)=-\frac{{\mathrm{e}}^{x}\left(1-b_{i}^{2}\right)}{\left({\mathrm{e}}^{x}b_{i}+1\right)\left({\mathrm{e}}^{x}+b_{i}\right)}\enspace,$

and notice that we want to show

$\Gamma_{e}=\frac{\left|1-b_{i}\right|}{1+b_{i}}\enspace.$

First, if $b_{i}=1$, then (23) gives

$\Gamma_{e}=\sup_{x}|h_{i}(x)|=0=\frac{\left|1-b_{i}\right|}{1+b_{i}}\enspace.$

Assume now $b_{i}\neq 1$. Differentiating $h_{i}$ gives

$h^{\prime}_{i}(x)=-\frac{{\mathrm{e}}^{x}\left(b_{i}^{2}-1\right)b_{i}\left({\mathrm{e}}^{2x}-1\right)}{\left({\mathrm{e}}^{x}b_{i}+1\right)^{2}\left({\mathrm{e}}^{x}+b_{i}\right)^{2}}\enspace.$

Since $b_{i}>0$, and $b_{i}\neq 1$, we observe that $h^{\prime}_{i}$ vanishes
only at $x=0$, and in particular, $x=0$ must be the only sign alternation
point of $h^{\prime}_{i}$. Finally, it is elementary to check that

$\lim_{x\to\infty}h_{i}(x)=\lim_{x\to-\infty}h_{i}(x)=0\enspace.$

Therefore, $0$ and $h_{i}(0)$ must be the global optima of $h_{i}$. Hence,
(23) yields

$\Gamma_{e}=\max\left\\{\left|\sup_{x}h_{i}(x)\right|,\
\left|\inf_{x}h_{i}(x)\right|\right\\}=|h_{i}(0)|=\frac{\left|1-b_{i}^{2}\right|}{\left(b_{i}+1\right)\left(1+b_{i}\right)}=\frac{\left|1-b_{i}\right|}{1+b_{i}}\enspace,$

as desired. ∎

##  5\. Theorem 2.1 \- Proof of non-reconstruction.

In order to prove Theorem 2.1, first consider the distribution we define in
(18), in Section 4. That is, for a tree $T=(V,E)$ rooted at $r$, assume that
we are given the parameters $\beta>0$ and $\\{J_{e}\\}_{e\in E}$, such that
$J_{e}\in\mathbb{R}$. Note that $J_{e}$ are fixed real constants, i.e., they
are not random numbers.

We define the Gibbs distribution $\mu=\mu_{\beta,\\{J_{e}\\}}$ on the tree $T$
such that each $\sigma\in\\{\pm 1\\}^{V}$ is assigned probability measure
$\mu(\sigma)$ such that

$\displaystyle\mu(\sigma)$
$\displaystyle\propto\textstyle\exp\left(\beta\sum_{\\{w,u\\}\in E}{\bf
1}\\{\sigma(u)=\sigma(w)\\}\cdot J_{\\{u,w\\}}\right)\enspace.$ (24)

For two vertices $u,w$ in $T$, write $\mathrm{path}(u,w)$ for the set of edges
in the unique path from $u$ to $w$. Building on Theorem 4.1, for the
aforementioned distribution we have the following result:

######  Theorem 5.1.

For integer $h>0$, $\beta>0$, and $\\{J_{e}\\}_{e\in E}$ such that
$J_{e}\in\mathbb{R}$, let $T=(V,E)$ be an arbitrary tree of height $h$, rooted
at vertex $r$, and let the Gibbs distribution $\mu=\mu_{\beta,\\{J_{e}\\}}$ on
$T$ be defined as in (24).

We have that

$\displaystyle\left|\left|\mu_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=+1)-\mu_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=-1)\right|\right|_{\rm TV}$
$\displaystyle\leq\sqrt{\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\Gamma_{e}^{2}}\enspace,$
(25)

where $\Gamma_{e}$ is the influence of edge $e$ defined in (22), and $\Lambda$
is the set of vertices at distance $h$ from the root.

For the above, recall that $\mu_{h}$ is the marginal of $\mu$ on the set of
vertices at distance $h$ from the root, i.e., the set $\Lambda$. In light of
Theorem 5.1, the non-reconstruction part of Theorem 2.1 follows as a
corollary.

###### Proof of Theorem 2.1 \- Non-Reconstruction.

Consider the Gibbs distribution $\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$
on the $\Delta$-ary tree $T=(V,E)$, and let $\Delta_{\rm KS}=\Delta_{\rm
KS}(\beta,\phi)$ be defined as in (10). We need to show that for
$\Delta<\Delta_{\rm KS}$ we have

$\limsup_{h\to\infty}\mathbb{E}\left[\left|\left|\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=+1)-\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=-1)\right|\right|_{\rm TV}\right]=0\enspace.$ (26)

Given the $\sigma$-algebra generated by the coupling parameters
$\\{{\mathbold{J}}_{e}\\}_{e\in E}$, from Theorem 5.1, we have that

$\displaystyle\left(\left|\left|\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=+1)-\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=-1)\right|\right|_{\rm TV}\right)^{2}$
$\displaystyle\leq\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\mathbold{\Gamma}_{e}^{2}\enspace,$
(27)

where recall that $\Lambda$ is the set of vertices at distance $h$ from the
root $r$, while for every $e\in E$ we have that

$\textstyle\mathbold{\Gamma}_{e}=\frac{\left|1-\exp\left(\beta{\mathbold{J}}_{e}\right)\right|}{1+\exp\left(\beta{\mathbold{J}}_{e}\right)}\enspace.$

For the sake of brevity, we let

$\displaystyle\mathbold{\mu}^{+}(\cdot)$ $\displaystyle=\mathbold{\mu}(\cdot\
|\ {\mathbold{\sigma}}(r)=+1)\enspace,$ and
$\displaystyle\mathbold{\mu}^{-}(\cdot)$ $\displaystyle=\mathbold{\mu}(\cdot\
|\ {\mathbold{\sigma}}(r)=-1)\enspace.$ (28)

Then, from (27) we have that

$\mathbb{E}\left[\left(\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\right)^{2}\right]\leq\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\mathbb{E}\left[\mathbold{\Gamma}_{e}^{2}\right]\enspace,$
(29)

where the expectation is with respect to random variable ${\mathbold{J}}_{e}$.
We derive the r.h.s. of the equation above using the observation that each
$\mathbold{\Gamma}_{e}$ depends only on ${\mathbold{J}}_{e}$, and the coupling
parameters $\\{{\mathbold{J}}_{e}\\}$, are assumed to be independent with each
other.

Furthermore, our assumption that $\Delta<\Delta_{\rm KS}$, corresponds to
having that $\mathbb{E}\left[\mathbold{\Gamma}_{e}^{2}\right]<\Delta^{-1}$.
Hence, there exists $\varepsilon\in(0,1]$ such that

$\displaystyle\mathbb{E}\left[\mathbold{\Gamma}_{e}^{2}\right]=\frac{1-\varepsilon}{\Delta}\enspace.$

Using the above, (29), and the fact that $T$ is $\Delta$-ary, and hence, the
size of $\Lambda$ is $\Delta^{h}$, we get that

$\displaystyle\mathbb{E}\left[\left(\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\right)^{2}\right]\leq(1-\varepsilon)^{h}\enspace.$

Invoking Markov’s inequality we further get that

$\Pr\left[\left(\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\right)^{2}\geq(1-\varepsilon)^{h/2}\right]\leq(1-\varepsilon)^{h/2}\enspace,$

or, since
$\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\geq 0$, we equivalently have that

$\Pr\left[\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\geq(1-\varepsilon)^{h/4}\right]\leq(1-\varepsilon)^{h/2}\enspace.$

Furthermore, since $\
\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\leq 1$ and
$\Pr\left[\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}<(1-\varepsilon)^{h/4}\right]\leq 1$, we have

$\displaystyle\mathbb{E}\left[\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\right]$
$\displaystyle\leq(1-\varepsilon)^{h/4}\Pr\left[\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}<(1-\varepsilon)^{h/4}\right]+\Pr\left[\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\geq(1-\varepsilon)^{h/4}\right]$
$\displaystyle\leq(1-\varepsilon)^{{h}/{4}}+(1-\varepsilon)^{{h}/{2}}\leq
2(1-\varepsilon)^{{h}/{4}}.$

The above implies (26), and concludes the non-reconstruction part of Theorem
2.1. ∎

##  6\. Proof of Theorem 5.1

Recall that we are dealing with the Gibbs distribution
$\mu=\mu_{\beta,\\{J_{e}\\}}$ on the tree $T$ of height $h$. With respect to
$\mu$ and every edge $e$ of the tree, we obtain the influence $\Gamma_{e}$ in
the standard way.

To prove Theorem 5.1, we use the idea of down-up coupling from [6], which also
relies on ideas in [29]. To this end, let us introduce a few notions. For
$s\in\\{\pm 1\\}$, we let $\mu_{\downarrow\uparrow}^{s}$ be the distribution
on the configuration at the root $r$ of the tree $T=(V,E)$ that is induced by
the following experiment. Recall that $\Lambda$ is the set of vertices at
distance $h$ from the root. First, we obtain the configuration
${\mathbold{\sigma}}\in\\{\pm 1\\}^{V}$ on the tree from the measure
$\mu^{s}(\cdot)$, where

$\displaystyle\mu^{s}(\cdot)$ $\displaystyle=\mu(\cdot\ |\
{\mathbold{\sigma}}(r)=s)\enspace.$

Next, we erase all the assignments apart from those at the vertices in
$\Lambda$. Then, we obtain a new configuration, ${\mathbold{\tau}}$, from the
distribution $\mu^{\Lambda,{\mathbold{\sigma}}}$, i.e., the distribution $\mu$
conditional on the configuration of set $\Lambda$ be as in
${\mathbold{\sigma}}$. With the measure $\mu_{\downarrow\uparrow}^{s}$ we
denote the distribution of ${\mathbold{\tau}}(r)$, i.e., the assingment of
${\mathbold{\tau}}$ at the root $r$.

Recall now that for $s\in\\{\pm 1\\}$, we write $\mu^{s}_{h}(\cdot)$ for the
marginal of $\mu$ at the vertices at distance $h$ from the root, conditioned
on ${\mathbold{\sigma}}(r)=s$. The following lemma was essentially proved for
standard Gibbs distributions in [6]. For the sake of completeness, we present
our own proof for the spin-glasses in the Appendix C.

######  Lemma 6.1 ([6] ).

For integer $h>0$, let $T=(V,E)$ be an arbitrary tree of height $h$, rooted at
vertex $r$. For any $\beta>0$, for any $\\{J_{e}\\}_{e\in E}$ with
$J_{e}\in\mathbb{R}$, let the Gibbs distribution $\mu=\mu_{\beta,\\{J_{e}\\}}$
on $T$ be defined as in (24). Then,

$\displaystyle\left|\left|\mu^{+}_{h}(\cdot)-\mu_{h}^{-}(\cdot)\right|\right|_{\rm
TV}$
$\displaystyle\leq\sqrt{\left|\left|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right|\right|_{\rm
TV}}\enspace.$ (30)

We prove the upper bound in (25) be means of the Lemma 6.1, i.e., by bounding
appropriately the quantity on the r.h.s. of (30). Specifically, we use the
bound obtained in the following proposition.

######  Proposition 6.2.

For integer $h>0$, let $T=(V,E)$ be an arbitrary tree of height $h$, rooted at
vertex $r$, and write $\Lambda$ for the set of vertices at distance $h$ from
the root. For each $e\in E$, let $\Gamma_{e}$ be the influence of edge $e$,
given by (22). Then,

$\displaystyle\left|\left|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right|\right|_{\rm
TV}$
$\displaystyle\leq\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\Gamma_{e}^{2}\enspace,$
(31)

where $\mu_{\downarrow\uparrow}^{+}$, $\mu_{\downarrow\uparrow}^{-}$ are as in
Lemma 6.1.

The proof of Proposition 6.2 appears in Section 7. Now, Theorem 5.1 follows by
plugging (31) into (30), i.e., we have that

$\displaystyle\left|\left|\mu^{+}_{h}(\cdot)-\mu^{-}_{h}(\cdot)\right|\right|_{\rm
TV}$
$\displaystyle\leq\sqrt{\left|\left|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right|\right|_{\rm
TV}}\leq\sqrt{\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\Gamma_{e}^{2}}\enspace.$

##  7\. Proof of Proposition 6.2

For $s\in\\{\pm 1\\}$, recall that $\mu^{s}_{\Lambda}(\cdot)$ be the marginal
of $\mu$ on $\Lambda$, conditional on the configuration at $r$ being $s$. For
any configuration $\tau\in\\{\pm 1\\}^{\Lambda}$, also recall that
$\mu^{\Lambda,\tau}_{r}$ is the marginal of $\mu$ at the root $r$, conditional
on the configuration at $\Lambda$ being $\tau$. In order to prove Proposition
6.2 we use the following result.

######  Lemma 7.1.

For integer $h>0$, let $T=(V,E)$ be an arbitrary tree of height $h$ rooted at
vertex $r$, and write $\Lambda$ for the vertices at distance $h$ from the
root. For any $\beta>0$, for any $\\{J_{e}\\}_{e\in E}$ such that
$J_{e}\in\mathbb{R}$, let the Gibbs distribution $\mu=\mu_{\beta,\\{J_{e}\\}}$
on $T$ be defined as in (24).

Then, for any distribution $\nu:\\{\pm 1\\}^{\Lambda}\times\\{\pm
1\\}^{\Lambda}$, coupling of the marginals $\mu^{+}_{\Lambda}(\cdot)$ and
$\mu^{-}_{\Lambda}(\cdot)$, we have

$\displaystyle\left|\left|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right|\right|_{\rm
TV}$
$\displaystyle\leq\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}\left[\left\|\mu^{\Lambda,{\mathbold{\sigma}}}_{r}(\cdot)-\mu^{\Lambda,{\mathbold{\tau}}}_{r}(\cdot)\right\|_{\rm
TV}\right]\enspace.$ (32)

###### Proof.

We have that

$\displaystyle\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}\left[\left\|\mu^{\Lambda,{\mathbold{\sigma}}}_{r}(\cdot)-\mu^{\Lambda,{\mathbold{\tau}}}_{r}(\cdot)\right\|_{\rm
TV}\right]$ $\displaystyle=\sum_{\sigma,\tau\in\\{\pm
1\\}^{\Lambda}}\left|\mu^{\Lambda,\sigma}_{r}(+1)-\mu^{\Lambda,\tau}_{r}(+1)\right|\cdot\nu(\sigma,\tau)$
$\displaystyle\geq\left|\sum_{\sigma,\tau\in\\{\pm
1\\}^{\Lambda}}\left(\mu^{\Lambda,\sigma}_{r}(+1)-\mu^{\Lambda,\tau}_{r}(+1)\right)\cdot\nu(\sigma,\tau)\right|$
$\displaystyle=\left|\left(\sum_{\sigma\in\\{\pm
1\\}^{\Lambda}}\mu^{\Lambda,\sigma}_{r}(+1)\cdot\mu^{+}_{\Lambda}(\sigma)\right)-\left(\sum_{\tau\in\\{\pm
1\\}^{\Lambda}}\mu^{\Lambda,\tau}_{r}(+1)\mu^{-}_{\Lambda}(\tau)\right)\right|\enspace.$
(33)

The second derivation is due the triangle inequality, while last equality
holds since $\nu(\cdot,\cdot)$ is a coupling of $\mu^{+}_{\Lambda}(\cdot)$ and
$\mu^{-}_{\Lambda}(\cdot)$, and thus for any $\sigma\in\\{\pm 1\\}^{\Lambda}$
we have that

$\displaystyle\sum_{\tau\in\\{\pm 1\\}^{\Lambda}}\nu(\sigma,\tau)$
$\displaystyle=\mu^{+}_{\Lambda}(\sigma)\enspace,$ and
$\displaystyle\sum_{\tau\in\\{\pm 1\\}^{\Lambda}}\nu(\tau,\sigma)$
$\displaystyle=\mu^{-}_{\Lambda}(\sigma)\enspace.$

Furthermore, note that for any $s,t\in\\{\pm 1\\}$, we have that

$\displaystyle\mu^{s}_{\downarrow\uparrow}(t)$
$\displaystyle=\sum_{\sigma\in\\{\pm\\}^{\Lambda}}\mu^{\Lambda,\sigma}_{r}(t)\cdot\mu_{\Lambda}^{s}(\sigma)\enspace.$
(34)

The above follows from the definition of $\mu^{s}_{\downarrow\uparrow}$, and
the law of total probability. Plugging (34) into (33), we get that

$\displaystyle\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}\left[\left\|\mu^{\Lambda,{\mathbold{\sigma}}}_{r}(\cdot)-\mu^{\Lambda,{\mathbold{\tau}}}_{r}(\cdot)\right\|_{\rm
TV}\right]$
$\displaystyle\geq\left|\mu^{+}_{\downarrow\uparrow}(+)-\mu^{-}_{\downarrow\uparrow}(+)\right|=\|\mu^{+}_{\downarrow\uparrow}(\cdot)-\mu^{-}_{\downarrow\uparrow}(\cdot)\|_{\rm
TV}\enspace.$

The above concludes the proof of Lemma 7.1. ∎

Lemma 7.1 implies the following technical result, which we prove in Subsection
7.1 below.

######  Proposition 7.2.

For any distribution $\nu:\\{\pm 1\\}^{\Lambda}\times\\{\pm 1\\}^{\Lambda}$,
coupling of the marginals $\mu^{+}_{\Lambda}(\cdot)$ and
$\mu^{-}_{\Lambda}(\cdot)$, the following is true:

$\displaystyle\left|\left|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right|\right|_{\rm
TV}$
$\displaystyle\leq\sum_{u\in\Lambda}\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}[{\bf
1}\\{{\mathbold{\sigma}}(u)\neq{\mathbold{\tau}}(u)\\}]\cdot\max_{\eta\in\\{\pm
1\\}^{\Lambda}}\left\|\mu^{\Lambda,\eta}_{r}(\cdot)-\mu^{\Lambda,\eta_{u}}_{r}(\cdot)\right\|_{\rm
TV},$ (35)

where $\eta_{u}\in\\{\pm 1\\}^{\Lambda}$ is obtained by $\eta$ by changing the
configuration at $u$, from $\eta(u)$ to its opposite.

Proposition 6.2 follows by bounding appropriately the r.h.s. of the inequality
above. Specifically, from Theorem 4.1 we have that

$\displaystyle\max_{\eta\in\\{\pm
1\\}^{\Lambda}}\left\|\mu^{\Lambda,\eta}_{r}(\cdot)-\mu^{\Lambda,\eta_{u}}_{r}(\cdot)\right\|_{\rm
TV}$ $\displaystyle\leq\prod_{e\in\mathrm{path}(r,u)}\Gamma_{e}\enspace,$ (36)

where recall that $\mathrm{path}(r,u)$ denotes the set of edges on the path
from the root $r$ to the vertex $u\in\Lambda$.

Moreover, we show that for any $u\in\Lambda$ we have

$\displaystyle\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}[{\bf
1}\\{{\mathbold{\sigma}}(u)\neq{\mathbold{\tau}}(u)\\}]$
$\displaystyle\leq\prod_{e\in\mathrm{path}(r,u)}\Gamma_{e}\enspace.$ (37)

It is immediate that Proposition 6.2 follows from Proposition 7.2 and (36),
(37).

We prove (37) by explicitly describing a coupling $\nu$ that achieves the
aforementioned bound. We call this coupling the “Down Coupling”.

### Down Coupling

Recall that we want to couple the distributions $\mu^{+}_{\Lambda}$ and
$\mu^{-}_{\Lambda}$. Instead, we couple $\mu^{+}$ and $\mu^{-}$, i.e., rather
than coupling the conditional Gibbs marginals at $\Lambda$, we couple the
conditional measure. The coupling of $\mu^{+}$ and $\mu^{-}$, trivially,
specifies a coupling for their marginals at $\Lambda$.

Write $\zeta:\\{\pm 1\\}^{V}\times\\{\pm 1\\}^{V}\to[0,1]$ for the coupling of
$\mu^{+}$ and $\mu^{-}$ we wish to define. We specify $\zeta$ by describing
how we generate two configurations
$({\mathbold{\sigma}},{\mathbold{\tau}})\in\\{\pm 1\\}^{V}\times\\{\pm
1\\}^{V}$ which are distributed as in $\zeta$. We generate the two
configurations inductively. In order to specify the configurations for the
vertices at level $i$ of the tree, we use the configurations at level $i-1$.
Suppose that we need to decide the configuration for vertex $w$, while we
already have the configurations for vertex $v$, the parent of $w$, i.e., we
have both ${\mathbold{\sigma}}(v)$ and ${\mathbold{\tau}}(v)$. Then, we use
maximal coupling for the configuration at vertex $w$, i.e., couple the
distributions $\mu_{w}(\cdot\ |\ {\mathbold{\sigma}}(v))$ and $\mu_{w}(\cdot\
|\ {\mathbold{\tau}}(v))$ so that
$\Pr[{\mathbold{\sigma}}(w)\neq{\mathbold{\tau}}(w)\ |\
{\mathbold{\sigma}}(v),{\mathbold{\tau}}(v)]$ is minimized. This implies that

$\displaystyle\Pr[{\mathbold{\sigma}}(w)\neq{\mathbold{\tau}}(w)\ |\
{\mathbold{\sigma}}(v),{\mathbold{\tau}}(v)]$
$\displaystyle=\left|\left|\mu_{w}(\cdot\mid{\mathbold{\sigma}}(v))-\mu_{w}(\cdot\mid{\mathbold{\tau}}(v))\right|\right|_{\rm
TV}\enspace.$

With the above coupling, we need to find an upper bound for
$\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}[{\bf
1}\\{{\mathbold{\sigma}}(u)\neq{\mathbold{\tau}}(u)\\}]$, where $u\in\Lambda$.
Ideally, we would like to get the one in (37).

For two vertices in the tree, $v$ and $w$, such that $v$ is the parent of $w$,
we have the following: Given ${\mathbold{\sigma}}(v),{\mathbold{\tau}}(v)$,
then in the above coupling we have that

$\displaystyle\Pr[{\mathbold{\sigma}}(w)\neq{\mathbold{\tau}}(w)\ |\
{\mathbold{\sigma}}(v),{\mathbold{\tau}}(v)]$
$\displaystyle=\left\\{\begin{array}[]{ccl}\left|\left|\mu_{w}(\cdot\mid{\mathbold{\sigma}}(v)=+1)-\mu_{w}(\cdot\mid{\mathbold{\tau}}(v)=-1)\right|\right|_{\rm
TV}&&\textrm{ if ${\mathbold{\sigma}}(v)\neq{\mathbold{\tau}}(v)$}\\\
0&&\textrm{ if
${\mathbold{\sigma}}(v)={\mathbold{\tau}}(v)$}\end{array}\right.,$

whereas,

$\displaystyle\left|\left|\mu_{w}(\cdot\mid{\mathbold{\sigma}}(v)=+1)-\mu_{w}(\cdot\mid{\mathbold{\tau}}(v)=-1)\right|\right|_{\rm
TV}$
$\displaystyle=\left|\mu_{w}(-1\mid{\mathbold{\sigma}}(v)=+1)-\mu_{w}(-1\mid{\mathbold{\tau}}(v)=-1)\right|$
$\displaystyle=\left|\frac{1}{1+\exp(J_{\\{w,v\\}})}-\frac{\exp(J_{\\{w,v\\}})}{1+\exp(J_{\\{w,v\\}})}\right|$
$\displaystyle=\Gamma_{\\{w,v\\}}\enspace,$

where the last equality is due to Claim 4.2. All the above imply that if the
coupling generates a disagreement at vertex $v$, i.e.,
${\mathbold{\sigma}}(v)\neq{\mathbold{\tau}}(v)$, then the disagreement
propagates at $w$ with probability $\Gamma_{\\{w,v\\}}$. From this point on,
it is elementary to verify that (37) is true, concluding the proof of
Proposition 6.2.

###  7.1. Proof of Proposition 7.2

Recall that $\Lambda$ is the set of vertices at distance $h$ from the root.
Consider an enumeration of the vertices in $\Lambda$, e.g., we have
$w_{1},\ldots,w_{\ell}$, where $\ell=|\Lambda|$. For any two configurations
$\sigma,\tau\in\\{\pm 1\\}^{\Lambda}$, and any $i\in\\{1,\ldots,\ell\\}$, we
define the interpolating sequence
$\mathcal{I}(\sigma,\tau)=\\{\xi_{i}\\}_{i=0,\ldots,\ell}$ as follows: for any
$i=0,\ldots,\ell$ we have $\xi_{i}\in\\{\pm 1\\}^{\Lambda}$ such that

$\displaystyle\xi_{i}(w_{j})=\sigma(w_{j})$ $\displaystyle\quad\textrm{, for
all }j>i,$ and $\displaystyle\xi_{i}(w_{j})=\tau(w_{j})$
$\displaystyle\quad\textrm{, for all }j\leq i\enspace.$

Note that $\xi_{0}=\sigma$, while $\xi_{\ell}=\tau$. Also note that any two
$\xi_{i}$ and $\xi_{i+1}$ may be equal.

######  Lemma 7.3.

For any distribution $\nu:\\{\pm 1\\}^{\Lambda}\times\\{\pm 1\\}^{\Lambda}$,
coupling of the marginals $\mu^{+}_{\Lambda}(\cdot)$ and
$\mu^{-}_{\Lambda}(\cdot)$, the following is true:

Consider $({\mathbold{\sigma}},{\mathbold{\tau}})$ distributed as in $\nu$,
and consider also the interpolating sequence

$\displaystyle\mathcal{I}({\mathbold{\sigma}},{\mathbold{\tau}})=\\{\mathbold{\xi}_{i}\\}_{i=0,\ldots,\ell}\enspace,$
(38)

that is induced by ${\mathbold{\sigma}}$, ${\mathbold{\tau}}$. We have that

$\displaystyle\left|\left|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right|\right|_{\rm
TV}$ $\displaystyle\leq\sum^{\ell}_{i=1}\mathbb{E}\left[{\bf
1}\\{\mathbold{\xi}_{i-1}\neq\mathbold{\xi}_{i}\\}\cdot\left\|\mu^{\Lambda,\mathbold{\xi}_{i-1}}_{r}(\cdot)-\mu^{\Lambda,\mathbold{\xi}_{i}}_{r}(\cdot)\right\|_{\rm
TV}\right]\enspace,$ (39)

where the expectation is with respect to $\mathbold{\xi}_{i}$ and
$\mathbold{\xi}_{i-1}$ of the interpolating sequence
${\mathcal{I}}({\mathbold{\sigma}},{\mathbold{\tau}})$.

###### Proof.

From Lemma 7.1, we have that

$\displaystyle\left|\left|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right|\right|_{\rm
TV}$
$\displaystyle\leq\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}\left[\left\|\mu^{\Lambda,{\mathbold{\sigma}}}_{r}(\cdot)-\mu^{\Lambda,{\mathbold{\tau}}}_{r}(\cdot)\right\|_{\rm
TV}\right]$
$\displaystyle=\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}\left[\left\|\sum^{\ell}_{i=1}\mu^{\Lambda,\mathbold{\xi}_{i-1}}_{r}(\cdot)-\mu^{\Lambda,\mathbold{\xi}_{i}}_{r}(\cdot)\right\|_{\rm
TV}\right]$
$\displaystyle\leq\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}\left[\sum^{\ell}_{i=1}\left\|\mu^{\Lambda,\mathbold{\xi}_{i-1}}_{r}(\cdot)-\mu^{\Lambda,\mathbold{\xi}_{i}}_{r}(\cdot)\right\|_{\rm
TV}\right]\enspace.$

The last inequality above follows from triangle inequality. Furthermore, the
last inequality is equivalent to the following one:

$\displaystyle\left|\left|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right|\right|_{\rm
TV}$
$\displaystyle\leq\mathbb{E}_{({\mathbold{\sigma}},{\mathbold{\tau}})\sim\nu}\left[\sum^{\ell}_{i=1}{\bf
1}\\{\mathbold{\xi}_{i-1}\neq\mathbold{\xi}_{i}\\}\left\|\mu^{\Lambda,\mathbold{\xi}_{i-1}}_{r}(\cdot)-\mu^{\Lambda,\mathbold{\xi}_{i}}_{r}(\cdot)\right\|_{\rm
TV}\right].$

The lemma follows by applying the linearity of expectation on the inequality
above. ∎

From Lemma 7.3 we get the following:

$\displaystyle\left|\left|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right|\right|_{\rm
TV}$ $\displaystyle\leq\sum^{\ell}_{i=1}\mathbb{E}\left[{\bf
1}\\{\mathbold{\xi}_{i-1}\neq\mathbold{\xi}_{i}\\}\left\|\mu^{\Lambda,\mathbold{\xi}_{i-1}}_{r}(\cdot)-\mu^{\Lambda,\mathbold{\xi}_{i}}_{r}(\cdot)\right\|_{\rm
TV}\right]$ $\displaystyle\leq\sum^{\ell}_{i=1}\mathbb{E}\left[{\bf
1}\\{\mathbold{\xi}_{i-1}\neq\mathbold{\xi}_{i}\\}\right]\cdot\max_{\eta\in\\{\pm
1\\}^{\Lambda}}\left\|\mu^{\Lambda,\eta}_{r}(\cdot)-\mu^{\Lambda,\eta_{w_{i}}}_{r}(\cdot)\right\|_{\rm
TV}$ $\displaystyle=\sum^{\ell}_{i=1}\mathbb{E}\left[{\bf
1}\\{{\mathbold{\sigma}}(w_{i})\neq{\mathbold{\tau}}(w_{i})\\}\right]\cdot\max_{\eta\in\\{\pm
1\\}^{\Lambda}}\left\|\mu^{\Lambda,\eta}_{r}(\cdot)-\mu^{\Lambda,\eta_{w_{i}}}_{r}(\cdot)\right\|_{\rm
TV}.$

The last derivation follows by noting that
$\mathbold{\xi}_{i-1}\neq\mathbold{\xi}_{i}$, if and only if, we have
${\mathbold{\sigma}}(w_{i})\neq{\mathbold{\tau}}(w_{i})$. All the above
conclude the proof of Proposition 7.2.

##  8\. Proof of Theorem 2.4 \- Proof of Non-Reconstruction for Galton-Watson

First, let us briefly recall what we want to prove. For any real numbers
$d>0$, and $\beta>0$, for any distribution $\phi$ on $\mathbb{R}$ let
$\Delta_{\rm KS}=\Delta_{\rm KS}(\beta,\phi)$ be defined as in (10). For any
offspring distribution $\zeta$ (on $\mathbb{Z}_{\geq 0}$), with expectation
$d$ and bounded second moment, let $\mathbold{T}$ be the Galton-Watson tree
with offspring distribution $\zeta$, and let the Gibbs distribution
$\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$ be defined as in (9) , on the
tree $\mathbold{T}$.

We want to show that if $d<\Delta_{\rm KS}$, then $\mathbold{\mu}$ exhibits
non-reconstruction i.e.,

$\displaystyle\limsup_{h\to\infty}\mathbb{E}_{\mathbold{T}}\left[\
\mathbb{E}_{\mathbold{\mu}}\left[\left|\left|\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=+1)-\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=-1)\right|\right|_{\rm TV}\ |\ \mathbold{T}\right]\
\right]=0\enspace.$

Using Theorem 5.1, which holds for arbitrary trees and taking expectations we
have that

$\displaystyle\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left(\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\right)^{2}\right]$
$\displaystyle\leq\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}{\mathbold\Gamma}_{e}^{2}\right]\enspace,$
(40)

where $\Lambda$ denotes the set of vertices at distance $h$ from the root.
Working out the r.h.s. of (40), using the law of total expectation, while
conditioning on $\mathbold{T}$, we get

$\displaystyle\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}{\mathbold\Gamma}_{e}^{2}\right]=\mathbb{E}_{\mathbold{T}}\left[\mathbb{E}_{\mathbold{\mu}}\left[\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}{\mathbold\Gamma}_{e}^{2}\middle|\mathbold{T}\right]\right]=\mathbb{E}_{\mathbold{T}}\left[|\Lambda|\cdot\left(\mathbb{E}_{\mathbold{\mu}}\left[\;{\mathbold\Gamma}_{e}^{2}\right]\right)^{h}\right]\enspace,$
(41)

since for fixed $\mathbold{T}$, the influences ${\mathbold\Gamma}_{e}$ are
independent, and identically distributed. Recalling now that $\Delta_{\rm
KS}=\left(\mathbb{E}_{\mu}[{\mathbold\Gamma}_{e}^{2}]\right)^{-1}$, (notice
that $\Delta_{\rm KS}$ does not depend on $\mathbold{T}$), and that the
offspring distributions of the vertices of $\mathbold{T}$ is $\zeta$ with
expectation $d$, we can rewrite (41) as

$\displaystyle\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}{\mathbold\Gamma}_{e}^{2}\right]=\mathbb{E}_{\mathbold{T}}\left[|\Lambda|\cdot\left(\Delta_{\rm
KS}\right)^{-h}\right]=\Delta_{\rm KS}^{-h}\cdot d^{h}\enspace.$

Per our assumption $\Delta_{\rm KS}>d$, there exists $\varepsilon\in(0,1]$
such that $(1-\varepsilon)\cdot\Delta_{\rm KS}=d$. Combining the above with
(40) we get that

$\displaystyle\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left(\left|\left|\mathbold{\mu}^{+}_{h}(\cdot)-\mathbold{\mu}^{-}_{h}(\cdot)\right|\right|_{\rm
TV}\right)^{2}\right]\leq\Delta_{\rm KS}^{-h}\cdot
d^{h}\leq(1-\varepsilon)^{h}\enspace.$

Invoking Markov’s inequality, similarly to the proof of the non-reconstruction
claim of Theorem 2.1 in Section 5, we get that

$\mathbb{E}_{\mathbold{T}}\left[\
\mathbb{E}_{\mathbold{\mu}}\left[\left|\left|\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=+1)-\mathbold{\mu}_{h}(\cdot\ |\
{\mathbold{\sigma}}(r)=-1)\right|\right|_{\rm TV}\ |\ \mathbold{T}\right]\
\right]\leq 2(1-\varepsilon)^{\frac{h}{4}}\enspace,$

so that taking limits as $h$ goes to infinity, gives the desired result.

##  9\. Theorem 2.1 \- Proof of reconstruction.

Here we prove the reconstruction part of Theorem 2.1. Before we delve into the
proof, let us recall our setup. For an integer $\Delta>0$, let $T=(V,E)$ be
the $\Delta$-ary tree rooted at $r$. Let also $\phi$ be a distribution on
$\mathbb{R}$, and let $\\{{\mathbold{J}}_{e}\\}_{e\in E}$ be i.i.d. random
variables, each distributed as in $\phi$. For a real number $\beta\geq 0$,
recall that the probability measure
$\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}(\sigma)$ on $\\{\pm 1\\}^{V}$ is
defined by

$\displaystyle\mathbold{\mu}_{\beta,\phi}(\sigma)$
$\displaystyle\propto\textstyle\exp\left(\beta\sum_{\\{u,w\\}\in E}{\bf
1}\\{\sigma(u)=\sigma(w)\\}\cdot{\mathbold{J}}_{\\{u,w\\}}\right)\enspace.$
(42)

In this setting, for ${\mathbold{J}}$ distributed as in $\phi$ we define

$\displaystyle\Delta_{\rm KS}(\beta,\phi)$
$\displaystyle=\textstyle\left(\mathbb{E}\left[\left(\frac{1-\exp(\beta{\mathbold{J}})}{1+\exp(\beta{\mathbold{J}})}\right)^{2}\right]\right)^{-1}\enspace,$
(43)

where the expectation is over the random variable ${\mathbold{J}}$. For an
integer $h>0$, we write $\Lambda$ for the set of vertices at distance $h$ from
the root $r$. We also write $\mathbold{\mu}_{\Lambda}^{+}$, and
$\mathbold{\mu}_{\Lambda}^{-}$ for the marginal of
$\mathbold{\mu}_{\beta,\phi}$ on the set $\Lambda$ conditioned on root being
$+1$ and $-1$, respectively. We want to prove that if $\Delta>\Delta_{\rm
KS}$, then $\mathbold{\mu}_{\beta,\phi}$ exhibits reconstruction, i.e.,

$\displaystyle\limsup_{h\to\infty}\mathbb{E}\left[\;\left|\left|\mathbold{\mu}_{\Lambda}^{+}(\cdot)-\mathbold{\mu}_{\Lambda}^{-}(\cdot)\right|\right|_{\rm
TV}\;\right]>0\enspace.$ (44)

To distinguish between the two layers of randomness considered here (spin
configurations are random having distribution $\mathbold{\mu}$, and
$\mathbold{\mu}$ itself is random as ${\mathbold{J}}$ is a random variable),
we use $\left\langle\cdot\right\rangle$ to denote expectation with respect to
the measure $\mathbold{\mu}$, and reserve $\mathbb{E}[\cdot]$ for expectations
taken with respect to the random variable of the couplings
$\\{{\mathbold{J}}_{e}\\}$.

In the same spirit as in [18], we show that in order to establish (44), it is
sufficient to find a real function on $\\{\pm 1\\}^{\Lambda}$ whose expected
values with respect to measures $\mathbold{\mu}_{\Lambda}^{+}$, and
$\mathbold{\mu}_{\Lambda}^{-}$, differ significantly, while its second moment
with respect to $\mathbold{\mu}$ is not much larger than the square of the
first moment. In particular, we show the following technical result.

######  Theorem 9.1.

For integer $h>0$, let $T=(V,E)$ be an arbitrary tree of height $h$, rooted at
vertex $r$, and let $\Lambda$ be the set of vertices at distance $h$ from $r$.
For any $\beta>0$, for any distribution $\phi$ on $\mathbb{R}$, let the Gibbs
distribution $\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$ on $T$ be defined as
in (42).

Then, for any real function $G:\\{\pm 1\\}^{\Lambda}\mapsto\mathbb{R}$ defined
on spin configurations of $\Lambda$, we have that

$\mathbb{E}\left[\left|\left|\mathbold{\mu}_{\Lambda}^{+}(\cdot)-\mathbold{\mu}_{\Lambda}^{-}(\cdot)\right|\right|_{\rm
TV}\right]\geq\frac{\left(\mathbb{E}\left[\left\langle
G\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
G\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]\right)^{2}}{4\mathbb{E}\left[\left\langle
G^{2}\right\rangle_{\mathbold{\mu}}\right]}\enspace,$ (45)

where $\mathbb{E}$ is with respect to the couplings $\\{{\mathbold{J}}_{e}\\}$
on the edges of $T$, induced the measure $\mathbold{\mu}$.

The proof of Theorem 9.1 appears in Section 10. We now wish to define a real
function $F_{h}$ on spin configurations of $\Lambda$, whose ratio in the
r.h.s. of (45) is bounded away from zero. To this end, we define the “signed
influence” of an edge $e\in E$ to be

$\textstyle\widehat{{\mathbold\Gamma}_{e}}=\frac{\exp(\beta{\mathbold{J}}_{e})-1}{1+\exp(\beta{\mathbold{J}}_{e})}\enspace.$
(46)

Observe that due to Claim 4.2, we have that the relationship between
$\widehat{{\mathbold\Gamma}_{e}}$, defined in above, and
${\mathbold\Gamma}_{e}$, defined by (14) in Section 4, is simply

$\textstyle\left|\widehat{{\mathbold\Gamma}_{e}}\right|={{\mathbold\Gamma}_{e}}\enspace.$
(47)

######  Definition 9.2.

For integer $h>0$, let $T=(V,E)$ be an arbitrary tree, rooted at vertex $r$,
and let $\Lambda$ be the set of vertices of $T$ at distance $h$ from the root.
For any $\beta\geq 0$, for any distribution $\phi$ on $\mathbb{R}$, let the
Gibbs distribution $\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$ on $T$ be
defined as in (42).

The _flipped majority vote_ is the function $F_{h}:\\{\pm
1\\}^{\Lambda}\to\mathbb{R}$ with

$F_{h}(\tau)=\sum_{u\in\Lambda}\tau(u)\times\prod_{e\in\mathrm{path}(r,u)}\widehat{{\mathbold\Gamma}_{e}}\enspace,$
(48)

where $\widehat{{\mathbold\Gamma}_{e}}$ be defined as in (46).

The following proposition expresses the enumerator and denominator of ratio in
the r.h.s. of (45) for the flipped majority vote, $F_{h}$, defined above, in
terms of the edge influences ${\mathbold\Gamma}_{e}$. For two vertices $u,v$
of $T$, write $\mathrm{path}(u,v)$ for the set of edges along the unique path
between $u$ and $v$, and write $u\wedge v$ for the common ancestor of $u$ and
$v$ farthest from the root $r$.

######  Proposition 9.3.

For integer $h>0$, let $T=(V,E)$ be an arbitrary tree of height $h$, rooted at
vertex $r$, and let $\Lambda$ be the set of vertices at distance $h$ from the
root of $T$. For any $\beta>0$, for any distribution $\phi$ on $\mathbb{R}$,
let the Gibbs distribution $\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$ on $T$
be defined as in (42).

Then,

$\mathbb{E}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]=2{\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\mathbb{E}\left[{\mathbold\Gamma}^{2}_{e}\right]}\enspace,$
(49)

and

${\mathbb{E}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}={\displaystyle\sum_{u,v\in\Lambda}\;\left(\prod_{e\in\mathrm{path}(u,v)}\mathbb{E}\left[{\mathbold\Gamma}_{e}^{2}\right]\right)\left(\prod_{e^{\prime}\in\mathrm{path}(r,u\wedge
v)}\mathbb{E}\left[{\mathbold\Gamma}_{e^{\prime}}^{2}\right]\right)}\enspace,$
(50)

where ${\mathbold\Gamma}_{e}$ is the influence of edge $e$ defined in (22).

The proof of Proposition 9.3 appears in Section 11. Finally, for the case of
$\Delta$-ary tree, and using Proposition 9.3, we have the following lemma

######  Lemma 9.4.

For integers $\Delta,h>0$, let $T=(V,E)$ be the $\Delta$-ary tree of height
$h$, rooted at vertex $r$, and let $\Lambda$ be the set of vertices at
distance $h$ from the root of $T$. For any $\beta>0$, for any distribution
$\phi$ on $\mathbb{R}$, let the Gibbs distribution
$\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$ on $T$ be defined as in (42).

Let also $\Delta_{\rm KS}(\beta,\phi)=\Delta_{\rm KS}$ be defined as in (43),
and let $F_{h}$ be the flipped majority vote defined in (48). Suppose that
$\Delta>\Delta_{\rm KS}$. Then, we have that

$\frac{\left(\mathbb{E}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]\right)^{2}}{4\mathbb{E}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}\geq\frac{\delta}{1+\delta}\enspace,$
(51)

where $\delta>0$ is defined by $1+\delta=\Delta/\Delta_{\rm KS}$.

We prove Lemma 9.4 in Section 12. The reconstruction claim of Theorem 2.1,
follows now readily from Theorem 9.1 and Lemma 9.4.

###### Proof of Theorem 2.1 \- Reconstruction..

Consider the Gibbs distribution $\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$
defined as in (42), on the $\Delta$-ary tree $T=(V,E)$. We need to show that
for $\Delta>\Delta_{\rm KS}$, where $\Delta_{\rm KS}=\Delta_{\rm
KS}(\beta,\phi)$ is defined as in (43), we have that

$\limsup_{h\to\infty}\mathbb{E}\left[\left|\left|\mathbold{\mu}_{\Lambda}^{+}-\mathbold{\mu}_{\Lambda}^{-}\right|\right|_{\rm
TV}\right]>0\enspace,$ (52)

where $\mathbb{E}$ is taken with respect to the random variables
$\\{{\mathbold{J}}_{e}\\}$. Let now $F_{h}:\\{\pm 1\\}^{\Lambda}\to\mathbb{R}$
be the flipped majority vote defined as in (48). Applying Theorem 9.1, which
holds for any real function on $\\{\pm 1\\}^{\Lambda}$, on $F_{h}$, gives

$\mathbb{E}\left[\left|\left|\mathbold{\mu}_{\Lambda}^{+}(\cdot)-\mathbold{\mu}_{\Lambda}^{-}(\cdot)\right|\right|_{\rm
TV}\right]\geq\frac{\left(\mathbb{E}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]\right)^{2}}{4\mathbb{E}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}\enspace.$

Since $\Delta>\Delta_{\rm KS}$, there exist a $\delta>0$ such that
$\Delta=(1+\delta)\Delta_{\rm KS}$. Applying Lemma 9.4 on the r.h.s. of the
above gives further that

$\mathbb{E}\left[\left|\left|\mathbold{\mu}_{\Lambda}^{+}(\cdot)-\mathbold{\mu}_{\Lambda}^{-}(\cdot)\right|\right|_{\rm
TV}\right]\geq\frac{\delta}{1+\delta}\enspace.$

Taking limits, yields trivially

$\limsup_{h\to\infty}\mathbb{E}\left[\left|\left|\mathbold{\mu}_{\Lambda}^{+}(\cdot)-\mathbold{\mu}_{\Lambda}^{-}(\cdot)\right|\right|_{\rm
TV}\right]\geq\frac{\delta}{1+\delta}>0\enspace,$

as desired, concluding the proof of the reconstruction claim of Theorem 2.1. ∎

##  10\. Proof Of Theorem 9.1

Let us first introduce some additional notation. For integer $h>0$, let
$T=(V,E)$ be an arbitrary tree of height $h$ rooted at vertex $r$, and let
$\Lambda$ be the set of vertices at distance $h$ from the root of $T$. Given a
function $G:\\{\pm 1\\}^{\Lambda}\mapsto\mathbb{R}$ defined on the spin
configurations of $\Lambda$, write $\mathrm{im}(G)\subseteq\mathbb{R}$ for the
range of $G$. For $t\in\mathrm{im}(G)$, and $s\in\\{\pm 1\\}$, let us define

$\displaystyle{\mathbold{\mu}_{r}(s\mid\\{G=t\\})=\mathbold{\mu}({\mathbold{\sigma}}(r)=s\mid\\{G=t\\})}\;,$
and
$\displaystyle{\mathbold{\mu}^{s}(\\{G=t\\})=\mathbold{\mu}(\\{G=t\\}\mid{\mathbold{\sigma}}(r)=s)}\enspace,$
(53)

where we used the notation $\\{G=t\\}=\left\\{\tau\in\\{\pm
1\\}^{\Lambda}:G(\tau)=t\right\\}$.

Recall also that $\mathbold{\mu}_{r}$ denotes the marginal of $\mathbold{\mu}$
at the root $r$, while $\mathbold{\mu}_{\Lambda}^{+}$ and
$\mathbold{\mu}_{\Lambda}^{-}$ denote the marginals of $\mathbold{\mu}$ at
$\Lambda$ conditioned on ${\mathbold{\sigma}}(r)=+1$ and
${\mathbold{\sigma}}(r)=-1$, respectively.

######  Lemma 10.1.

For integer $h>0$, let $T=(V,E)$ be arbitrary tree of height $h$ rooted at
vertex $r$, and let $\Lambda$ be the set of vertices at distance $h$ from the
root of $T$. For any $\beta\geq 0$, for any distribution $\phi$ on
$\mathbb{R}$, let the Gibbs distribution
$\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$ on $T$ be defined as in (42).

Then, for any $G:\\{\pm 1\\}^{\Lambda}\mapsto\mathbb{R}$, we have that

$\left\langle\left|\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right|\right\rangle_{t\sim\mathbold{\mu}}\leq\left|\left|\mathbold{\mu}_{\Lambda}^{+}(\cdot)-\mathbold{\mu}_{\Lambda}^{-}(\cdot)\right|\right|_{\rm
TV}\enspace.$ (54)

###### Proof.

First, we observe that the l.h.s. of (54) can be expressed as total variation
distance. In particular, we have that

$\left\langle\left|\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right|\right\rangle_{t\sim\mathbold{\mu}}=\left|\left|\mathbold{\mu}^{+}(\\{G=\cdot\\})-\mathbold{\mu}^{-}(\\{G=\cdot\\})\right|\right|_{\rm
TV}\enspace,$ (55)

where recall that $\mathbold{\mu}_{r}$ is the marginal of $\mathbold{\mu}$ at
the root $r$, while $\mathbold{\mu}^{+}$ and $\mathbold{\mu}^{-}$ denote the
measure $\mathbold{\mu}$ conditional on ${\mathbold{\sigma}}(r)=+1$ and
${\mathbold{\sigma}}(r)=-1$, respectively. Indeed, we have

$\displaystyle\left\langle\left|\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right|\right\rangle_{t\sim\mathbold{\mu}}$
$\displaystyle=\sum_{t\in\mathrm{im}(G)}\left|\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right|\cdot{\mathbold{\mu}(\\{G=t\\})}$
$\displaystyle=\sum_{t\in\mathrm{im}(G)}\left|\mathbold{\mu}_{r}(+1\mid\\{G=t\\}){\mathbold{\mu}(\\{G=t\\})}-\mathbold{\mu}_{r}(-1\mid\\{G=t\\}){\mathbold{\mu}(\\{G=t\\})}\right|$
$\displaystyle=\frac{1}{2}\sum_{t\in\mathrm{im}(G)}\left|\mathbold{\mu}_{r}(+1\mid\\{G=t\\})\frac{\mathbold{\mu}(\\{G=t\\})}{\mathbold{\mu}({\mathbold{\sigma}}(r)=+1)}-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\frac{\mathbold{\mu}(\\{G=t\\})}{\mathbold{\mu}({\mathbold{\sigma}}(r)=-1)}\right|$
(56)
$\displaystyle=\frac{1}{2}\sum_{t\in\mathrm{im}(G)}\left|\mathbold{\mu}^{+}(\\{G=t\\})-\mathbold{\mu}^{-}(\\{G=t\\})\right|$
(57)
$\displaystyle=\left|\left|\mathbold{\mu}^{+}(\\{G=\cdot\\})-\mathbold{\mu}^{-}(\\{G=\cdot\\})\right|\right|_{\rm
TV}\enspace,$

where (56) and (57) follow from Bayes’ rule, and the fact that
${\mathbold{\mu}({\mathbold{\sigma}}(r)=-1)=\mathbold{\mu}({\mathbold{\sigma}}(r)=+1)={1}/{2}}$.

Recall now that the total variation distance of two measures $p$ and $q$,
defined on the same probability space $(\Omega,\mathcal{F})$, can be
equivalently defined as

$\left|\left|p-q\right|\right|_{\rm
TV}=\sup_{A\in\mathcal{F}}|p(A)-q(A)|\enspace.$

Given a subalgebra $\mathcal{G}\subseteq\mathcal{F}$, let $p^{\prime}$ and
$q^{\prime}$ denote the restrictions of $p$ and $q$ on $\mathcal{G}$,
respectively. Then

$\left|\left|p^{\prime}-q^{\prime}\right|\right|_{\rm
TV}=\sup_{A\in\mathcal{G}}|p^{\prime}(A)-q^{\prime}(A)|\leq\sup_{A\in\mathcal{F}}|p(A)-q(A)|=\left|\left|p-q\right|\right|_{\rm
TV}\enspace.$

Observe now that $\mathbold{\mu}^{+}(\\{G=\cdot\\})$ and
$\mathbold{\mu}^{-}(\\{G=\cdot\\})$ are precisely the restrictions of
$\mathbold{\mu}_{\Lambda}^{+}(\cdot)$ and
$\mathbold{\mu}_{\Lambda}^{-}(\cdot)$ on the $\sigma$-algebra generated by the
function $G$, respectively. Hence, per the above and (55), we have that

$\left\langle\left|\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right|\right\rangle_{t\sim\mathbold{\mu}}\\\
=\left|\left|\mathbold{\mu}^{+}(\\{G=\cdot\\})-\mathbold{\mu}^{-}(\\{G=\cdot\\})\right|\right|_{\rm
TV}\leq\left|\left|\mathbold{\mu}_{\Lambda}^{+}(\cdot)-\mathbold{\mu}_{\Lambda}^{-}(\cdot)\right|\right|_{\rm
TV}\enspace.$

The above concludes the proof of Lemma 10.1. ∎

As usual, it is easier to handle squares than absolute values. Observing that

$0\leq\left\langle\left|\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right|\right\rangle_{t\sim\mathbold{\mu}}\leq
1\enspace,$

we have that

$\left\langle\left(\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right)^{2}\right\rangle_{t\sim\mathbold{\mu}}\leq\left\langle\left|\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right|\right\rangle_{t\sim\mathbold{\mu}}\enspace,$

which further implies

$\left\langle\left(\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right)^{2}\right\rangle_{t\sim\mathbold{\mu}}\leq\left|\left|\mathbold{\mu}_{\Lambda}^{+}(\cdot)-\mathbold{\mu}_{\Lambda}^{-}(\cdot)\right|\right|_{\rm
TV}\enspace.$ (58)

Finally, we need to prove the following lemma.

######  Lemma 10.2.

For integer $h>0$, let $T=(V,E)$ be arbitrary tree of height $h$ rooted at
vertex $r$, and let $\Lambda$ be the set of vertices at distance $h$ from the
root of $T$. For any $\beta>0$, for any distribution $\phi$ on $\mathbb{R}$,
let the Gibbs distribution $\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$ on $T$
be defined as in (42).

Then, for any $G:\\{\pm 1\\}^{\Lambda}\mapsto\mathbb{R}$, we have that

$\displaystyle\mathbb{E}\left[\left\langle\left(\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right)^{2}\right\rangle_{t\sim\mu}\right]\geq\frac{\left(\mathbb{E}\left[\left\langle
G\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
G\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]\right)^{2}}{4\mathbb{E}\left[\left\langle
G^{2}\right\rangle_{\mathbold{\mu}}\right]}\enspace.$ (59)

Recall that the expectation is taken w.r.t. the coupling parameters in
$\mathbold{\mu}$.

###### Proof.

Expanding the enumerator of the fraction in the right hand side of (59) gives

$\displaystyle\mathbb{E}^{2}$ $\displaystyle\left[\left\langle
G\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
G\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]$
$\displaystyle=\mathbb{E}^{2}\left[\sum_{t\in\mathrm{im}(G)}t\cdot\mathbold{\mu}^{+}(\\{G=t\\})-\sum_{t\in\mathrm{im}(G)}t\cdot\mathbold{\mu}^{-}(\\{G=t\\})\right]$
$\displaystyle=\left(\int\sum_{t\in\mathrm{im}(G)}t\cdot\left[\mathbold{\mu}^{+}(\\{G=t\\})-\mathbold{\mu}^{-}(\\{G=t\\})\right]d{\phi}\right)^{2}$
$\displaystyle=\left(2\int\sum_{t\in\mathrm{im}(G)}t\cdot\left[\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right]\cdot\mathbold{\mu}\left(\\{G=t\\}\right)d{\phi}\right)^{2}\enspace,$
(60)

where the last equality follows from Bayes’ rule. Applying now the Cauchy-
Schwartz inequality with factors

$\displaystyle\left[\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right]\cdot\sqrt{\mathbold{\mu}\left(\\{G=t\\}\right)}\;,$
and $\displaystyle t\cdot\sqrt{\mathbold{\mu}\left(\\{G=t\\}\right)}\enspace,$

we further get that

$\displaystyle\mathbb{E}^{2}\left[\left\langle
G\right\rangle_{\mu_{\Lambda}^{+}}-\left\langle
G\right\rangle_{\mu_{\Lambda}^{-}}\right]$ $\displaystyle\leq
4\left(\int\sum_{t\in\mathrm{im}(G)}t^{2}\mathbold{\mu}\left(\\{G=t\\}\right)d{\phi}\right)\cdot\int\sum_{t\in\mathrm{im}(G)}\left[\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right]^{2}\mathbold{\mu}\left(\\{G=t\\}\right)d{\phi}$
$\displaystyle=4\cdot\mathbb{E}\left[\left\langle
G^{2}\right\rangle_{\mathbold}{\mu}\right]\cdot\mathbb{E}\left[\left\langle\left(\mathbold{\mu}_{r}(+1\mid\\{G=t\\})-\mathbold{\mu}_{r}(-1\mid\\{G=t\\})\right)^{2}\right\rangle_{t\sim\mathbold{\mu}}\right]\enspace.$

The above concludes the proof of Lemma 10.2. ∎

Theorem 9.1 now follows from (58) and Lemma 10.2.

##  11\. Proof of Proposition 9.3

Let $T=(V,E)$ be an arbitrary tree rooted at $r$. Let also $\phi$ be a
distribution on $\mathbb{R}$, and let $\\{{\mathbold{J}}_{e}\\}_{e\in E}$ be
i.i.d. random variables, each ${\mathbold{J}}_{e}$ distributed as in $\phi$.
For a real number $\beta\geq 0$, recall that the probability measure
$\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}(\sigma)$ on $\\{\pm 1\\}^{V}$ is
defined by

$\displaystyle\mathbold{\mu}_{\beta,\phi}(\sigma)$
$\displaystyle\propto\textstyle\exp\left(\beta\sum_{\\{w,u\\}\in E}{\bf
1}\\{\sigma(u)=\sigma(w)\\}\cdot{\mathbold{J}}_{\\{u,w\\}}\right)\enspace.$
(61)

Recall also that for each $e\in E$ we have defined

$\textstyle\widehat{{\mathbold\Gamma}_{e}}=\frac{\exp(\beta{\mathbold{J}}_{e})-1}{1+\exp(\beta{\mathbold{J}}_{e})}\enspace,$
(62)

and we use $\mathrm{path}(u,v)$ to denote the set of edges along the unique
path between $u$ and $v$. Finally, recall that $\mathbold{\mu}^{u,s}$ denotes
the measure $\mathbold{\mu}$ conditional on ${\mathbold{\sigma}}(u)=s$, for
$s\in\\{\pm 1\\}$. We now have the following lemma.

######  Lemma 11.1.

Let $T=(V,E)$ be an arbitrary tree, and let $\mathbold{\mu}$ be the Gibbs
measure on $T$ defined as in (61), and $\widehat{{\mathbold\Gamma}_{e}}$ be as
in (62). Then, for any two vertices $u,w$ of $T$, and $s\in\\{\pm 1\\}$ we
have

$\left\langle{\mathbold{\sigma}}(w)\right\rangle_{\mathbold{\mu}^{u,s}}=s\prod_{e\in\mathrm{path}(u,w)}\widehat{{\mathbold\Gamma}_{e}}\enspace.$
(63)

###### Proof.

Let $(u,q_{1},\ldots,q_{t},w)$ be the unique path from $u$ to $w$, and write
$P=\\{q_{1},\ldots,q_{t},w\\}$ for the set of vertices along that path, apart
from $u$. We now see that for any $s\in\\{\pm 1\\}$ we have that

$\left\langle{\mathbold{\sigma}}(w)\right\rangle_{\mathbold{\mu}^{u,s}}=\sum_{\tau\in\\{\pm
1\\}^{P}}\tau(v)\cdot\mathbold{\mu}({\mathbold{\sigma}}(P)=\tau\mid{\mathbold{\sigma}}(u)=s)\enspace.$
(64)

We now prove (63) by induction on the distance between $u$ and $v$. For the
base case, corresponds to $w$ and $u$ being adjacent vertices. Then, for any
$s\in\\{\pm 1\\}$, equation (64) becomes

$\displaystyle\left\langle{\mathbold{\sigma}}(w)\right\rangle_{\mathbold{\mu}^{u,s}}$
$\displaystyle=\mathbold{\mu}({\mathbold{\sigma}}(w)=+1\mid{\mathbold{\sigma}}(u)=s)-\mathbold{\mu}({\mathbold{\sigma}}(w)=-1\mid{\mathbold{\sigma}}(u)=s)$
$\displaystyle=\begin{cases}\frac{\exp(\beta{\mathbold{J}}_{\\{u,w\\}})-1}{1+\exp(\beta{\mathbold{J}}_{\\{u,w\\}})}=\widehat{{\mathbold\Gamma}}_{\\{u,w\\}}&\text{
if }s=+1\\\\[6.0pt]
\frac{1-\exp(\beta{\mathbold{J}}_{\\{u,w\\}})}{1+\exp(\beta{\mathbold{J}}_{\\{u,w\\}})}=-\widehat{{\mathbold\Gamma}}_{\\{u,w\\}}&\text{
if }s=-1\/\end{cases}\enspace,$

as desired.

Assume now (63) holds for any pair of vertices whose distance is at most $t$.
Let $u$, $w$ be a pair of vertices of distance $t+1$. In particular, let
$(u,q_{1},\dots,q_{t},w)$ be the (unique) path from $u$ to $w$, and write
$P=\\{q_{1},\ldots,q_{t},w\\}$, and $P^{\prime}=P\setminus\\{q_{1}\\}$. From
(64) we have that for $s\in\\{\pm 1\\}$

$\displaystyle\left\langle{\mathbold{\sigma}}(w)\right\rangle_{\mathbold{\mu}^{u,s}}$
$\displaystyle=\sum_{\tau\in\\{\pm
1\\}^{P}}\tau(w)\cdot\mathbold{\mu}({\mathbold{\sigma}}(P)=\tau\mid{\mathbold{\sigma}}(u)=s)$
$\displaystyle=\sum_{\xi\in\\{\pm 1\\}}\sum_{\tau\in\\{\pm
1\\}^{P^{\prime}}}\tau(w)\cdot\mathbold{\mu}\left({\mathbold{\sigma}}(q_{1})=\xi\mid{\mathbold{\sigma}}(u)=s\right)\cdot\mathbold{\mu}\left({\mathbold{\sigma}}(P^{\prime})=\tau\mid{\mathbold{\sigma}}(q_{1})=\xi,\
{\mathbold{\sigma}}(u)=s\right)$ $\displaystyle=\sum_{\xi\in\\{\pm
1\\}}\sum_{\tau\in\\{\pm
1\\}^{P^{\prime}}}\tau(w)\cdot\mathbold{\mu}\left({\mathbold{\sigma}}(q_{1})=\xi\mid{\mathbold{\sigma}}(u)=s\right)\cdot\mathbold{\mu}\left({\mathbold{\sigma}}(P^{\prime})=\tau\mid{\mathbold{\sigma}}(q_{1})=\xi\right)\enspace,$

where the last equality follows from the Markov property of the model. Pushing
now forward the sum over the configurations of $P^{\prime}$ we further get

$\displaystyle\left\langle{\mathbold{\sigma}}(w)\right\rangle_{\mathbold{\mu}^{u,s}}$
$\displaystyle=\sum_{\xi\in\\{\pm
1\\}}\mathbold{\mu}\left({\mathbold{\sigma}}(q_{1})=\xi\mid{\mathbold{\sigma}}(u)=s\right)\cdot\left(\sum_{\tau\in\\{\pm
1\\}^{P^{\prime}}}\tau(w)\cdot\mathbold{\mu}\left({\mathbold{\sigma}}(P^{\prime})=\tau\mid{\mathbold{\sigma}}(q_{1})=\xi\right)\right)$
$\displaystyle=\sum_{\xi\in\\{\pm
s\\}}\mathbold{\mu}\left({\mathbold{\sigma}}(q_{1})=\xi\mid{\mathbold{\sigma}}(u)=s\right)\cdot\left\langle{\mathbold{\sigma}}(w)\right\rangle_{\mathbold{\mu}^{q_{1},\xi}}\enspace,$

where $\mathbold{\mu}^{q_{1},\xi}$ denotes the measure $\mathbold{\mu}$
conditional on ${\mathbold{\sigma}}(q_{1})=\xi$, and we get the last equality
from (64). Expanding now the sum over $\xi\in\\{\pm s\\}$, we further get

$\displaystyle\left\langle{\mathbold{\sigma}}(w)\right\rangle_{\mathbold{\mu}^{u,s}}$
$\displaystyle=\frac{\exp(\beta J_{\\{u,w\\}})}{1+\exp(\beta
J_{\\{u,w\\}})}\cdot\left\langle{\mathbold{\sigma}}(w)\right\rangle_{\mathbold{\mu}^{q_{1},s}}+\frac{1}{1+\exp(\beta
J_{\\{u,w\\}})}\cdot\left\langle{\mathbold{\sigma}}(w)\right\rangle_{\mathbold{\mu}^{q_{1},(-s)}}$
$\displaystyle=\left({\textstyle\frac{\exp(\beta J_{\\{u,w\\}})}{1+\exp(\beta
J_{\\{u,w\\}})}}\cdot
s\cdot\prod_{e\in\mathrm{path}(q_{1},w)}\widehat{{\mathbold\Gamma}_{e}}\right)+\left({\textstyle\frac{1}{1+\exp(\beta
J_{\\{u,w\\}})}}\cdot(-s)\cdot\prod_{e\in\mathrm{path}(q_{1},w)}\widehat{{\mathbold\Gamma}_{e}}\right)$
(65)
$\displaystyle=\left(s\cdot\prod_{e\in\mathrm{path}(q_{1},w)}\widehat{{\mathbold\Gamma}_{e}}\right)\cdot\left(\frac{\exp(\beta
J_{\\{u,w\\}})-1}{1+\exp(\beta J_{\\{u,w\\}})}\right)$
$\displaystyle=s\cdot\prod_{e\in\mathrm{path}(u,w)}\widehat{{\mathbold\Gamma}_{e}}\enspace,$
(66)

where (65) follows from the inductive hypothesis applied on vertices $q_{1}$
and $w$, while (66) follows from the definition of
$\widehat{{\mathbold\Gamma}_{e}}$ in (62). ∎

Using Lemma 11.1, we now prove the following lemma about pairwise spin
correlations.

######  Lemma 11.2.

Let $T=(V,E)$ be any finite tree, and let $\mathbold{\mu}$ be the Gibbs
measure on $T$ defined as in (61), and $\widehat{{\mathbold\Gamma}_{e}}$ be as
in (62). Then, for any two vertices $u,v$ of $T$, we have

$\left\langle{\mathbold{\sigma}}(u)\cdot{\mathbold{\sigma}}(v)\right\rangle_{\mathbold{\mu}}=\prod_{e\in\mathrm{path}(u,v)}\widehat{{\mathbold\Gamma}_{e}}\enspace.$

###### Proof.

Indeed,

$\displaystyle\left\langle{\mathbold{\sigma}}(u)\cdot{\mathbold{\sigma}}(v)\right\rangle_{\mathbold{\mu}}$
$\displaystyle=\sum_{\tau\in\\{\pm\\}^{V}}\tau(u)\cdot\tau(v)\cdot\mathbold{\mu}(\tau)$
$\displaystyle=\frac{1}{2}\sum_{\tau\in\\{\pm\\}^{V\setminus\\{u\\}}}\tau(v)\cdot\mathbold{\mu}^{u,+}(\tau)-\frac{1}{2}\sum_{\tau\in\\{\pm\\}^{V\setminus\\{u\\}}}\tau(v)\cdot\mathbold{\mu}^{u,-}(\tau)$
(67)
$\displaystyle=\frac{1}{2}\left(\left\langle{\mathbold{\sigma}}(v)\right\rangle_{\mathbold{\mu}^{u,+}}\right)-\frac{1}{2}\left(\left\langle{\mathbold{\sigma}}(v)\right\rangle_{\mathbold{\mu}^{u,-}}\right)$
$\displaystyle=\frac{1}{2}\left(\prod_{e\in\mathrm{path}(u,v)}\widehat{{\mathbold\Gamma}_{e}}\right)-\frac{1}{2}\left((-1)\prod_{e\in\mathrm{path}(u,v)}\widehat{{\mathbold\Gamma}_{e}}\right)=\prod_{e\in\mathrm{path}(u,v)}\widehat{{\mathbold\Gamma}_{e}}\enspace,$
(68)

where $\mathbold{\mu}^{u,+}$, $\mathbold{\mu}^{u,-}$ denote measure
$\mathbold{\mu}$ conditional on $u$ being $+1$ and $-1$, respectively. We get
(67) by the law of total probability, i.e., we condition on the spin of $u$,
and use the fact that
$\mathbold{\mu}({\mathbold{\sigma}}(r)=-)=\mathbold{\mu}({\mathbold{\sigma}}(r)=+)={1}/{2}$.
Also, (68) follows from Lemma 11.1. All the above conclude the proof of Lemma
11.2. ∎

Recall that $\mathbold{\mu}_{\Lambda}^{+}$, and $\mathbold{\mu}_{\Lambda}^{-}$
denote the marginals of $\mathbold{\mu}$ on $\Lambda$, conditioned on
${\mathbold{\sigma}}(r)=+1$, and ${\mathbold{\sigma}}(r)=-1$, respectively.
Finally, let $\widehat{{\mathbold\Gamma}_{e}}$ be the signed influence of edge
$e$, defined as in (62), and $F_{h}$ be the flipped majority vote introduced
in Definition 9.2.

We start by applying Lemmas 11.1, and 11.2, to calculate the first moments of
$F_{h}$ with respect to the measures $\mathbold{\mu}_{\Lambda}^{+}$, and
$\mathbold{\mu}_{\Lambda}^{-}$. We have that

$\displaystyle\left\langle
F_{h}\right\rangle_{\mathbold{\mu}^{+}_{\Lambda}}=\sum_{v\in\Lambda}\left\langle{\mathbold{\sigma}}(v)\right\rangle_{\mathbold{\mu}^{+}_{\Lambda}}\;\cdot\prod_{e\in\mathrm{path}(r,v)}\widehat{{\mathbold\Gamma}_{e}}=\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\left(\widehat{{\mathbold\Gamma}_{e}}\right)^{2}=\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}{\mathbold\Gamma}_{e}^{2}\enspace,$
(69)

where the first equality follows from linearity of expectation, the second
equality by applying Lemma 11.1, and the last equality is due to (47).
Similarly,

$\displaystyle\left\langle
F_{h}\right\rangle_{\mathbold{\mu}^{-}_{\Lambda}}=\sum_{v\in\Lambda}\left\langle{\mathbold{\sigma}}(v)\right\rangle_{\mathbold{\mu}^{-}_{\Lambda}}\;\cdot\prod_{e\in\mathrm{path}(r,v)}\widehat{{\mathbold\Gamma}_{e}}=-\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\left(\widehat{{\mathbold\Gamma}_{e}}\right)^{2}=-\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}{\mathbold\Gamma}_{e}^{2}\enspace.$
(70)

It is now easy to derive (49) as

$\displaystyle{\mathbb{E}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]}={\mathbb{E}\left[2\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}{\mathbold\Gamma}_{e}^{2}\right]}=2\sum_{v\in\Lambda}\;\prod_{e\in\mathrm{path}(r,v)}\mathbb{E}\left[{\mathbold\Gamma}_{e}^{2}\right]\enspace,$

where the first equality follows from (69) and (70). To get the last equality,
we use the linearity of expectation, and the fact that the couplings
$\\{{\mathbold{J}}_{e}\\}_{e\in E}$, (and thus, also
$\\{{\mathbold\Gamma}_{e}\\}_{e\in E}$), are independent.

We now use Lemma 11.2 to calculate the second moment of $F_{h}$ with respect
to $\mathbold{\mu}_{\Lambda}$. Expanding $F_{h}^{2}$, we have that

$\displaystyle\left\langle F_{h}^{2}\right\rangle_{\mathbold{\mu}}$
$\displaystyle=\sum_{u\in\Lambda}\left\langle{\mathbold{\sigma}}^{2}(u)\right\rangle_{\mathbold{\mu}}\cdot\prod_{e\in\mathrm{path}(r,u)}\left(\widehat{{\mathbold\Gamma}_{e}}\right)^{2}+\sum_{\begin{subarray}{c}u,v\in\Lambda\\\
u\neq
v\end{subarray}}\left\langle{\mathbold{\sigma}}(u){\mathbold{\sigma}}(v)\right\rangle_{\mathbold{\mu}}\cdot\prod_{e\in\mathrm{path}(r,u)}\widehat{{\mathbold\Gamma}_{e}}\cdot\prod_{{e^{\prime}}\in\mathrm{path}(r,v)}\widehat{{\mathbold\Gamma}_{e^{\prime}}}$
$\displaystyle=\sum_{u\in\Lambda}\;\prod_{e\in\mathrm{path}(r,u)}{\mathbold\Gamma}^{2}_{e}+\sum_{\begin{subarray}{c}u,v\in\Lambda\\\
u\neq
v\end{subarray}}\;\prod_{e\in\mathrm{path}(u,v)}\widehat{{\mathbold\Gamma}_{e}}\cdot\prod_{e\in\mathrm{path}(r,u)}\widehat{{\mathbold\Gamma}_{e}}\cdot\prod_{e^{\prime}\in\mathrm{path}(r,v)}\widehat{{\mathbold\Gamma}_{e^{\prime}}}\enspace,$

where the first equality follows from the linearity of expectation, while the
second equality follows from Lemma 11.2. Recalling that $u\wedge v$ denotes
the common ancestor of $u$ and $v$ farthest from the root $r$, we can rewrite
the above as

$\displaystyle\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}=\sum_{u,v\in\Lambda}\;\prod_{e\in\mathrm{path}(u,v)}{\mathbold\Gamma}_{e}^{2}\cdot\prod_{{e^{\prime}}\in\mathrm{path}(r,u\wedge
v)}{\mathbold\Gamma}_{e^{\prime}}^{2}\enspace.$ (71)

We are now ready to prove (50). Per (71) we have that

$\displaystyle{\mathbb{E}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}$
$\displaystyle={\displaystyle\mathbb{E}\left[\sum_{u,v\in\Lambda}\;\left(\prod_{e\in\mathrm{path}(u,v)}{\mathbold\Gamma}_{e}^{2}\right)\left(\prod_{e^{\prime}\in\mathrm{path}(r,u\wedge
v)}{\mathbold\Gamma}_{e^{\prime}}^{2}\right)\right]}$
$\displaystyle={\displaystyle\sum_{u,v\in\Lambda}\mathbb{E}\left[\;\left(\prod_{e\in\mathrm{path}(u,v)}{\mathbold\Gamma}_{e}^{2}\right)\left(\prod_{e^{\prime}\in\mathrm{path}(r,u\wedge
v)}{\mathbold\Gamma}_{e^{\prime}}^{2}\right)\right]}$
$\displaystyle={\displaystyle\sum_{u,v\in\Lambda}\;\left(\prod_{e\in\mathrm{path}(u,v)}\mathbb{E}\left[{\mathbold\Gamma}_{e}^{2}\right]\right)\left(\prod_{e^{\prime}\in\mathrm{path}(r,u\wedge
v)}\mathbb{E}\left[{\mathbold\Gamma}_{e^{\prime}}^{2}\right]\right)}\enspace,$

where the first equality follows from the linearity of expectation, and the
second from the fact that the couplings $\\{{\mathbold{J}}_{e}\\}_{e\in E}$,
(and thus, also $\\{{\mathbold\Gamma}_{e}\\}_{e\in E}$), are independent. This
concludes the proof of Proposition 9.3.

##  12\. Proof of Lemma 9.4

For integers $\Delta,h>0$, let now $T=(V,E)$ be the $\Delta$-ary tree rooted
at $r$, and $\mathbold{\mu}_{\beta,\phi}(\sigma)$ be the Gibbs measure on $T$
defined as in (61). Let also $\Lambda$ be the set of vertices at distance $h$
from the root $r$. By Proposition 9.3 we have that

$\frac{\left(\mathbb{E}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]\right)^{2}}{4\mathbb{E}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}=\frac{\displaystyle\left(\sum_{v\in\Lambda}\prod_{e\in\mathrm{path}(r,v)}\mathbb{E}\left[{\mathbold\Gamma}^{2}_{e}\right]\right)^{2}}{\displaystyle\sum_{u,v\in\Lambda}\;\left(\prod_{e\in\mathrm{path}(u,v)}\mathbb{E}\left[{\mathbold\Gamma}_{e}^{2}\right]\right)\left(\prod_{e^{\prime}\in\mathrm{path}(r,u\wedge
v)}\mathbb{E}\left[{\mathbold\Gamma}_{e^{\prime}}^{2}\right]\right)}\enspace.$

Recalling that $\textstyle\Delta_{\rm KS}=\Delta_{\rm
KS}(\beta,\phi)=\left(\mathbb{E}\left[\left(\frac{1-\exp(\beta{\mathbold{J}})}{1+\exp(\beta{\mathbold{J}})}\right)^{2}\right]\right)^{-1}=\left(\mathbb{E}\left[{\mathbold\Gamma}_{e}^{2}\right]\right)^{-1}$,
we have that

$\displaystyle\frac{\left(\mathbb{E}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]\right)^{2}}{4\mathbb{E}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}$
$\displaystyle=\frac{\displaystyle\left(\sum_{v\in\Lambda}\prod_{e\in\mathrm{path}(r,v)}\Delta_{\rm
KS}^{-1}\right)^{2}}{\displaystyle\sum_{u,v\in\Lambda}\;\left(\prod_{e\in\mathrm{path}(u,v)}\Delta_{\rm
KS}^{-1}\right)\left(\prod_{e^{\prime}\in\mathrm{path}(r,u\wedge
v)}\Delta_{\rm KS}^{-1}\right)}$
$\displaystyle=\frac{\displaystyle\left(\sum_{v\in\Lambda}\Delta_{\rm
KS}^{-|\mathrm{path}(r,v)|}\right)^{2}}{\displaystyle\sum_{u,v\in\Lambda}\;\left(\Delta_{\rm
KS}^{-|\mathrm{path}(u,v)|}\right)\left(\Delta_{\rm
KS}^{-|\mathrm{path}(r,u\wedge v)|}\right)}$
$\displaystyle=\frac{\displaystyle\Delta^{2h}\cdot\Delta_{\rm
KS}^{-2h}}{\displaystyle\sum_{u,v\in\Lambda}\;\Delta_{\rm
KS}^{|\mathrm{path}(r,u\wedge
v)|-2h}}=\frac{\displaystyle\Delta^{2h}}{\displaystyle\sum_{u,v\in\Lambda}\;\Delta_{\rm
KS}^{|\mathrm{path}(r,u\wedge v)|}}\enspace,$ (72)

where to get the first equality of (72) we observe that
$|\mathrm{path}(u,v)|=2|\mathrm{path}(r,u\wedge v)|$. Writing now
$\Lambda(\ell)$ for the vertices of $T$ at distance $0\leq\ell\leq h$ from the
root $r$, and reorganising the sum in the denominator of (72) with respect to
the common ancestor $z=u\wedge v$, we get that

$\displaystyle\sum_{u,v\in\Lambda}\;\Delta_{\rm KS}^{|\mathrm{path}(r,u\wedge
v)|}$
$\displaystyle=\sum_{\ell=0}^{h}\;\sum_{z\in\Lambda(\ell)}\;\sum_{\begin{subarray}{c}\;u,v\in\Lambda(h)\\\
u\wedge v=z\end{subarray}}\;\Delta_{\rm KS}^{\ell}$
$\displaystyle=\sum_{\ell=0}^{h}\;\Delta_{\rm
KS}^{\ell}\sum_{z\in\Lambda(\ell)}\;\sum_{\begin{subarray}{c}\;u,v\in\Lambda(h)\\\
u\wedge v=z\end{subarray}}\;1$ $\displaystyle=\sum_{\ell=0}^{h}\;\Delta_{\rm
KS}^{\ell}\left[\Delta^{\ell}\cdot\left(\Delta^{h-\ell}-1\right)\cdot\Delta^{h-\ell}\right]$
$\displaystyle\leq\sum_{\ell=0}^{h}\;\Delta_{\rm
KS}^{\ell}\cdot\Delta^{\ell}\cdot{\Delta^{2(h-\ell)}}\ =\
\Delta^{2h}\sum_{\ell=0}^{h}\;\left(\frac{\Delta_{\rm
KS}}{\Delta}\right)^{\ell}\enspace,$

which, due to our assumption that $\Delta=(1+\delta)\Delta_{\rm KS}$, for some
$\delta>0$, further simplifies to

$\displaystyle\sum_{u,v\in\Lambda}\;\Delta_{\rm KS}^{|\mathrm{path}(r,u\wedge
v)|}\leq\Delta^{2h}\left(1-\frac{\Delta_{\rm
KS}}{\Delta}\right)^{-1}=\Delta^{2h}\left(\frac{\delta}{1+\delta}\right)^{-1}\enspace.$

Plugging now the above into (72) we finally get

$\displaystyle\frac{\left(\mathbb{E}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\Lambda}^{-}}\right]\right)^{2}}{4\mathbb{E}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}\geq\frac{\Delta^{2h}}{\Delta^{2h}\left(\frac{\delta}{1+\delta}\right)^{-1}}=\frac{\delta}{1+\delta}\enspace.$

All the above complete the proof of Lemma 9.4.

##  13\. Proof of Theorem 2.4 \- reconstruction for the Galton-Watson Tree

Let us briefly recall our setup. For any real number $d>0$, for $\beta>0$, for
any distribution $\phi$ on $\mathbb{R}$, and any offspring distribution
$\zeta:\mathbb{Z}_{\geq 0}\to[0,1]$ with expectation $d$ and bounded second
moment, let $\Delta_{\rm KS}=\Delta_{\rm KS}(\beta,\phi)$ be defined as in
(10). Let $\mathbold{T}$ be the Galton-Watson tree with offspring distribution
$\zeta$, while let the Gibbs distribution
$\mathbold{\mu}=\mathbold{\mu}_{\beta,\phi}$, defined as in (9) , on the tree
$\mathbold{T}$. For an integer $h>0$, write $\boldsymbol{\Lambda}$ for the set
of vertices at distance $h$ from the root of $\mathbold{T}$ (notice that
$\boldsymbol{\Lambda}$ is a random variable here). We also write
$\mathbold{\mu}_{\boldsymbol{\Lambda}}^{+}$ and
$\mathbold{\mu}_{\boldsymbol{\Lambda}}^{-}$ for the marginal of measure
$\mathbold{\mu}$ on the set $\boldsymbol{\Lambda}$, conditioned on the root of
$\mathbold{T}$ being $+$ and $-$, respectively.

We want to show that if $d>\Delta_{\rm KS}$, the distribution
$\mathbold{\mu}_{\beta,\phi}$ exhibits reconstruction, i.e.,

$\displaystyle\limsup_{h\to\infty}\mathbb{E}_{\mathbold{T}}\left[\
\mathbb{E}_{\mathbold{\mu}}\left[\left|\left|\mathbold{\mu}_{\boldsymbol{\Lambda}}^{+}(\cdot)-\mathbold{\mu}_{\boldsymbol{\Lambda}}^{-}(\cdot)\right|\right|_{\rm
TV}\ |\ \mathbold{T}\right]\ \right]>0\enspace.$

We start by noticing that Theorem 9.1 can be extended to Galton-Watson trees.
That is, we have that for any real function $G:\\{\pm
1\\}^{\boldsymbol{\Lambda}}\mapsto\mathbb{R}$ defined on spin configurations
of $\boldsymbol{\Lambda}$, we have that

$\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left|\left|\mathbold{\mu}_{\boldsymbol{\Lambda}}^{+}(\cdot)-\mathbold{\mu}_{\boldsymbol{\Lambda}}^{-}(\cdot)\right|\right|_{\rm
TV}\right]\geq\frac{\left(\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
G\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{+}}-\left\langle
G\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{-}}\right]\right)^{2}}{4\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
G^{2}\right\rangle_{\mathbold{\mu}}\right]}\enspace,$ (73)

In fact, the proof (73) is almost identical to that of Theorem 9.1, the only
difference being that at the very last step of the proof, we apply Cauchy-
Schwartz to an expression with an additional sum (due to
$\mathbb{E}_{\mathbold{T}}$). Hence, all it remains to do is to lower bound
the rhs of (73) away from zero.

From Proposition 9.3 and conditioning over the random tree $\mathbold{T}$, we
get that

$\displaystyle\frac{\left(\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{-}}\right]\right)^{2}}{4\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}$
$\displaystyle=\frac{\displaystyle\left(\mathbb{E}_{\mathbold{T}}\left[\mathbb{E}_{\mathbold{\mu}}\left[\sum_{v\in{\boldsymbol{\Lambda}}}\;\prod_{e\in\mathrm{path}(r,v)}{\mathbold\Gamma}^{2}_{e}\;\middle|\
\mathbold{T}\right]\right]\right)^{2}}{\displaystyle\mathbb{E}_{\mathbold{T}}\left[\mathbb{E}_{\mathbold{\mu}}\left[\sum_{u,v\in{\boldsymbol{\Lambda}}}\left(\prod_{e\in\mathrm{path}(u,v)}{\mathbold\Gamma}_{e}^{2}\right)\left(\prod_{e^{\prime}\in\mathrm{path}(r,u\wedge
v)}{\mathbold\Gamma}_{e^{\prime}}^{2}\right)\middle|\mathbold{T}\right]\right]}\enspace.$

Given a random tree $\mathbold{T}$, the influences, ${\mathbold\Gamma}_{e}$,
are independent. Moreover, recalling that $\Delta_{\rm
KS}=\left(\mathbb{E}_{\mu}[{\mathbold\Gamma}_{e}^{2}]\right)^{-1}$, (notice
that $\Delta_{\rm KS}$ does not depend on $\mathbold{T}$), we can further
simplify the above as follows:

$\displaystyle\frac{\left(\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{-}}\right]\right)^{2}}{4\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}$
$\displaystyle=\frac{\displaystyle\left(\mathbb{E}_{\mathbold{T}}\left[\sum_{v\in{\boldsymbol{\Lambda}}(h)}\;\Delta_{\rm
KS}^{-h}\right]\right)^{2}}{\displaystyle\mathbb{E}_{\mathbold{T}}\left[\sum_{u,v\in{\boldsymbol{\Lambda}}(h)}\;\Delta_{\rm
KS}^{|\mathrm{path}(r,u\wedge
v)|-2h}\right]}=\frac{\displaystyle\left(\mathbb{E}_{\mathbold{T}}\left[\;|{\boldsymbol{\Lambda}}(h)|\;\right]\right)^{2}}{\displaystyle\mathbb{E}_{\mathbold{T}}\left[\sum_{u,v\in{\boldsymbol{\Lambda}}(h)}\;\Delta_{\rm
KS}^{|\mathrm{path}(r,u\wedge v)|}\right]}\enspace.$

Since from this point on we are left only with expectations with respect to
$\mathbold{T}$, we drop the subscript in $\mathbb{E}$. Reorganising the sum of
in the denominator in the last equation above, similarly to the proof of Lemma
9.4, and writing ${\boldsymbol{\Lambda}}_{z}(\ell)$ for the descendants of $z$
at distance $\ell$ (${\boldsymbol{\Lambda}}$ without subscript refers to
descendants of the root $r$), we get that

$\displaystyle\mathbb{E}\left[\sum_{u,v\in{\boldsymbol{\Lambda}}(h)}\Delta_{\rm
KS}^{|\mathrm{path}(r,u\wedge v)|}\right]$
$\displaystyle=\sum_{\ell=0}^{h}\Delta_{\rm
KS}^{\ell}\cdot{\mathbb{E}\left[\sum_{z\in{\boldsymbol{\Lambda}}(\ell)}\sum_{w,q\in{\boldsymbol{\Lambda}}_{z}(1)}|{\boldsymbol{\Lambda}}_{w}(h-\ell-1)|\cdot|{\boldsymbol{\Lambda}}_{q}(h-\ell-1)|\right]}\enspace.$
(74)

Let us now focus on the expectation in the r.h.s. of the above equation. In
particular, we invoke the law of total expectation conditioning on the set
${\boldsymbol{\Lambda}}(\ell)$, comprised of the vertices at distance $\ell$
from the root

$\displaystyle{\mathbb{E}\left[\sum_{z\in{\boldsymbol{\Lambda}}(\ell)}\sum_{w,q\in{\boldsymbol{\Lambda}}_{z}(1)}|{\boldsymbol{\Lambda}}_{w}(h-\ell-1)|\cdot|{\boldsymbol{\Lambda}}_{q}(h-\ell-1)|\right]}$
$\displaystyle=\mathbb{E}\left[{\mathbb{E}\left[\sum_{z\in{\boldsymbol{\Lambda}}(\ell)}\sum_{w,q\in{\boldsymbol{\Lambda}}_{z}(1)}|{\boldsymbol{\Lambda}}_{w}(h-\ell-1)|\cdot|{\boldsymbol{\Lambda}}_{q}(h-\ell-1)|\middle|{\boldsymbol{\Lambda}}(\ell)\right]}\right]$
$\displaystyle=\mathbb{E}\left[|{\boldsymbol{\Lambda}}(\ell)|\cdot{\mathbb{E}\left[\sum_{w,q\in{\boldsymbol{\Lambda}}(1)}|{\boldsymbol{\Lambda}}_{w}(h-\ell-1)|\cdot|{\boldsymbol{\Lambda}}_{q}(h-\ell-1)|\right]}\right]\enspace,$
(75)

where (75) follows from the linearity of expectation, and the fact that the
offsprings of each vertex are identically distributed (and hence, the random
variable ${\boldsymbol{\Lambda}}_{z}(1)$ coincides with
${\boldsymbol{\Lambda}}(1)$, for all vertices $z$). We now estimate the inner
expectation of (75) conditioning on ${\boldsymbol{\Lambda}}(1)$.

$\displaystyle\mathbb{E}\left[\sum_{w,q\in{\boldsymbol{\Lambda}}(1)}|{\boldsymbol{\Lambda}}_{w}(h-\ell-1)|\cdot|{\boldsymbol{\Lambda}}_{q}(h-\ell-1)|\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\sum_{w,q\in{\boldsymbol{\Lambda}}(1)}|{\boldsymbol{\Lambda}}_{w}(h-\ell-1)|\cdot|{\boldsymbol{\Lambda}}_{q}(h-\ell-1)|\middle|{\boldsymbol{\Lambda}}(1)\right]\right]$
$\displaystyle=\mathbb{E}\left[|{\boldsymbol{\Lambda}}(1)|\cdot(|{\boldsymbol{\Lambda}}(1)|-1)\cdot\left(\mathbb{E}\Big{[}|{\boldsymbol{\Lambda}}(h-\ell-1)|\Big{]}\right)^{2}\right]$
(76)
$\displaystyle\leq\mathbb{E}\left[|{\boldsymbol{\Lambda}}(1)|^{2}\right]\cdot\left(\mathbb{E}\Big{[}|{\boldsymbol{\Lambda}}(h-\ell-1)|\Big{]}\right)^{2}\enspace,$
(77)

where (76) follows from the linearity of expectation, and the fact that the
offsprings of each vertex are independent (and thus, the inner expectation of
products becomes the product of the corresponding expectations), and
identically distributed (and hence,
${\boldsymbol{\Lambda}}_{w}(h-\ell-1)={\boldsymbol{\Lambda}}_{q}(h-\ell-1)={\boldsymbol{\Lambda}}(h-\ell-1)$).

Putting them all together, we have that (74), (75),(76), and (77) yield

$\displaystyle\frac{\left(\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{-}}\right]\right)^{2}}{4\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}\geq\frac{\displaystyle\left(\mathbb{E}\left[\;|{\boldsymbol{\Lambda}}(h)|\;\right]\right)^{2}}{\displaystyle\sum_{\ell=0}^{h}\Delta_{\rm
KS}^{\ell}\cdot\mathbb{E}\Big{[}|{\boldsymbol{\Lambda}}(\ell)|\Big{]}\cdot\mathbb{E}\Big{[}|{\boldsymbol{\Lambda}}(1)|^{2}\Big{]}\cdot\left(\mathbb{E}\Big{[}|{\boldsymbol{\Lambda}}(h-\ell-1)|\Big{]}\right)^{2}}\enspace.$

Due to the fact that the offsprings of vertices in $\mathbold{T}$ are i.i.d.,
we observe that for any $\ell\geq 0$, we have that
$\mathbb{E}[|{\boldsymbol{\Lambda}}(\ell)|=(\mathbb{E}[\zeta])^{\ell}=d^{\ell}$,
and thus, we can further simplify the above as follows

$\displaystyle\frac{\left(\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{-}}\right]\right)^{2}}{4\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}$
$\displaystyle\geq\frac{\displaystyle\left(\mathbb{E}\left[\;|{\boldsymbol{\Lambda}}(h)|\;\right]\right)^{2}}{\displaystyle\sum_{\ell=0}^{h}\Delta_{\rm
KS}^{\ell}\cdot\mathbb{E}\Big{[}|{\boldsymbol{\Lambda}}(\ell)|\Big{]}\cdot\mathbb{E}\Big{[}|{\boldsymbol{\Lambda}}(1)|^{2}\Big{]}\cdot\left(\mathbb{E}\Big{[}|{\boldsymbol{\Lambda}}(h-\ell-1)|\Big{]}\right)^{2}}$
$\displaystyle=\frac{\left(\mathbb{E}\left[\zeta\right]\right)^{2h}}{\displaystyle\sum_{\ell=0}^{h}\Delta_{\rm
KS}^{\ell}\cdot\left(\mathbb{E}\left[\zeta\right]\right)^{\ell}\cdot\mathbb{E}\left[\zeta^{2}\right]\cdot\left(\mathbb{E}\left[\zeta\right]\right)^{2h-2\ell-2}}$
$\displaystyle=\frac{1}{\displaystyle\frac{\mathbb{E}\left[\zeta^{2}\right]}{d^{2}}\cdot\sum_{\ell=0}^{h}\left(\frac{\Delta_{\rm
KS}}{d}\right)^{\ell}}\enspace.$

Per our hypothesis, $\mathbb{E}\left[\zeta^{2}\right]<\infty$, and thus,
$\mathbb{E}\left[\zeta^{2}\right]\leq Md^{2}$, for some bounded number $M>0$.
Moreover, we have that $\Delta_{\rm KS}<d$, and thus, there exist a
$\delta>0$, such that $\Delta_{\rm KS}(1+\delta)=d$. With that in mind, we
further bound the above as

$\displaystyle\frac{\left(\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{+}}-\left\langle
F_{h}\right\rangle_{\mathbold{\mu}_{\boldsymbol{\Lambda}}^{-}}\right]\right)^{2}}{4\mathbb{E}_{\mathbold{T},\mathbold{\mu}}\left[\left\langle
F_{h}^{2}\right\rangle_{\mathbold{\mu}}\right]}$
$\displaystyle\geq\frac{1}{\displaystyle\frac{\mathbb{E}\left[\zeta^{2}\right]}{d^{2}}\cdot\sum_{\ell=0}^{h}\left(\frac{\Delta_{\rm
KS}}{d}\right)^{\ell}}\geq\frac{\delta}{M(1+\delta)}>0\enspace.$

This concludes the proof of the reconstruction claim of Theorem 2.4.

## References

  * [1] Dimitris Achlioptas and Amin Coja-Oghlan.  Algorithmic barriers from phase transitions.  In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 793–802. IEEE, 2008.
  * [2] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke.  Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 323–334. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00038.
  * [3] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.  Spectral independence in high-dimensional expanders and applications to the hardcore model.  SIAM Journal on Computing, 0(0):FOCS20–1–FOCS20–37, 2021.  doi:10.1137/20M1367696.
  * [4] Victor Bapst, Amin Coja-Oghlan, and Charilaos Efthymiou.  Planting colourings silently.  Combinatorics, probability and computing, 26(3):338–366, 2017.
  * [5] Nayantara Bhatnagar, Allan Sly, and Prasad Tetali.  Reconstruction threshold for the hardcore model.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pages 434–447. Springer, 2010.
  * [6] Nayantara Bhatnagar, Juan Vera, Eric Vigoda, and Dror Weitz.  Reconstruction for colorings on trees.  SIAM Journal on Discrete Mathematics, 25(2):809–826, 2011.
  * [7] Pavel M Bleher, Jean Ruiz, and Valentin A Zagrebnov.  On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.  Journal of Statistical Physics, 79:473–482, 1995.
  * [8] Christian Borgs, Jennifer Chayes, Elchanan Mossel, and Sébastien Roch.  The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 518–530. IEEE, 2006.
  * [9] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Rapid mixing of Glauber dynamics up to uniqueness via contraction.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1307–1318. IEEE, 2020.
  * [10] Amin Coja-Oghlan and Charilaos Efthymiou.  On independent sets in random graphs.  Random Structures & Algorithms, 47(3):436–486, 2015.
  * [11] Amin Coja-Oghlan, Charilaos Efthymiou, and Nor Jaafari.  Local convergence of random graph colorings.  Combinatorica, 38(2):341–380, 2018.
  * [12] Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, and Tobias Kapetanopoulos.  Charting the replica symmetric phase.  Communications in Mathematical Physics, 359:603–698, 2018.
  * [13] Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, and Eric Vigoda.  Metastability of the Potts Ferromagnet on Random Regular Graphs.  In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 45:1–45:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.ICALP.2022.45.
  * [14] Amin Coja-Oghlan, Tobias Kapetanopoulos, and Noela Müller.  The replica symmetric phase of random constraint satisfaction problems.  Combinatorics, Probability and Computing, 29(3):346–422, 2020.
  * [15] Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová.  Information-theoretic thresholds from the cavity method.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 146–157, 2017.
  * [16] Samuel Frederick Edwards and Phil W Anderson.  Theory of spin glasses.  Journal of Physics F: Metal Physics, 5(5):965, 1975.
  * [17] Charilaos Efthymiou.  On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs.  In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 57:1–57:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.ICALP.2022.57.
  * [18] William Evans, Claire Kenyon, Yuval Peres, and Leonard J Schulman.  Broadcasting on trees and the Ising model.  Annals of Applied Probability, pages 410–433, 2000.
  * [19] Silvio Franz, Michele Leone, Federico Ricci-Tersenghi, and Riccardo Zecchina.  Exact solutions for diluted spin glasses and optimization problems.  Physical review letters, 87(12):127209, 2001.
  * [20] Hans-Otto Georgii.  Gibbs measures and phase transitions, volume 9.  Walter de Gruyter, 2011.