# Efficient approximation of branching random walk Gibbs measures

Fu-Hsuan Ho  Institut de Mathématiques de Toulouse, CNRS UMR5219. Postal
address: Institut de Mathématiques de Toulouse, Université Toulouse 3 Paul
Sabatier, 118 Route de Narbonne, 31062 Toulouse Cedex 9, France. Email:fu-
hsuan.ho AT math.univ-toulouse.fr, pascal.maillard AT math.univ-toulouse.fr.
Supported in part by grants ANR-20-CE92-0010-01 and ANR-11-LABX-0040 (ANR
program “Investissements d’Avenir”).  Pascal Maillard11footnotemark: 1

###### Abstract

Disordered systems such as spin glasses have been used extensively as models
for high-dimensional random landscapes and studied from the perspective of
optimization algorithms. In a recent paper by L. Addario-Berry and the second
author, the _continuous random energy model (CREM)_ was proposed as a simple
toy model to study the efficiency of such algorithms. The following question
was raised in that paper: what is the threshold $\beta_{G}$, at which sampling
(approximately) from the Gibbs measure at inverse temperature $\beta$ becomes
algorithmically hard?

This paper is a first step towards answering this question. We consider the
branching random walk, a time-homogeneous version of the continuous random
energy model. We show that a simple greedy search on a renormalized tree
yields a linear-time algorithm which approximately samples from the Gibbs
measure, for every $\beta<\beta_{c}$, the (static) critical point. More
precisely, we show that for every $\varepsilon>0$, there exists such an
algorithm such that the specific relative entropy between the law sampled by
the algorithm and the Gibbs measure of inverse temperature $\beta$ is less
than $\varepsilon$ with high probability.

In the supercritical regime $\beta>\beta_{c}$, we provide the following
hardness result. Under a mild regularity condition, for every $\delta>0$,
there exists $z>0$ such that the running time of any given algorithm
approximating the Gibbs measure stochastically dominates a geometric random
variable with parameter $e^{-z\sqrt{N}}$ on an event with probability at least
$1-\delta$.

#### Keywords:

branching random walk ; Gibbs measure ; Kullback–Leibler divergence.

#### MSC2020 subject classifications:

68Q17, 82D30, 60K35, 60J80.

##  1 Introduction

We consider the following family of branching random walks. An initial
particle is located at the origin. It gives birth to $d$ child particles,
$d\geq 2$, scattering on the real line, and each of the child particles
produces $d$ child particles again, and so on. The displacement of each
particle is independent of the past of the process and of the displacements of
its siblings. The genealogy of the particles can be represented by a $d$-ary
tree $\mathbb{T}_{N}$, identifying particles with the vertices of the tree. We
denote by $X_{v}$ the location of a particle $v\in\mathbb{T}_{N}$.

Addario-Berry and Maillard [1] considered algorithms that, for a given $x>0$,
find a leaf $v$ of $\mathbb{T}_{N}$ such that $X_{v}\geq xN$ in the framework
of the continuous random energy model (CREM). This is a binary time-
inhomogeneous branching random walk with Gaussian displacements. More
precisely, the CREM is a Gaussian process whose covariance function is given
by

$\mathbb{E}\left[X_{v}X_{w}\right]=A\left(\frac{\absolutevalue{v\wedge
w}}{N}\right),\quad\forall v,w\in\mathbb{T}_{n}$

where $A:[0,1]\rightarrow[0,1]$ is an increasing function with $A(0)=0$ and
$A(1)=1$ and $\absolutevalue{v\wedge w}$ is the depth of the most recent
common ancestor of $v$ and $w$. The authors proved the existence of a
threshold $x_{*}$ such that the following holds: a) for every $x<x_{*}$, there
exists a polynomial-time algorithm that can accomplish the task with high
probability, b) for every $x>x_{*}$, every such algorithm has a running time
which is at least exponential in $N$ with high probability. The authors also
raised the question of the complexity of sampling a _typical_ vertex of value
roughly $xN$, which can be interpreted as sampling a vertex according to a
Gibbs measure with a certain parameter $\beta$ depending on $x$.

The present work attacks this problem in the simpler setting of the
(homogeneous) branching random walk, corresponding to the case $A(x)=x$ of the
CREM in the special case of Gaussian displacements. The Gibbs measure is a
probability measure on the leaves $v$ of $\mathbb{T}_{N}$ with weight
proportional to $e^{\beta X_{v}}$, where $\beta>0$ is a given parameter called
the _inverse temperature_. We show that there exists a threshold $\beta_{c}>0$
such that the following holds: a) in the subcritical regime $\beta<\beta_{c}$,
there exists a linear-time algorithm such that with high probability, the
specific relative entropy between the law sampled by the algorithm and the
Gibbs measure of inverse temperature $\beta$ is arbitrarily small, b) in the
supercritical regime $\beta>\beta_{c}$, under a mild regularity condition, we
show that with high probability, the running time of any given algorithm
approximating the Gibbs measure in this sense is at least stretched
exponential in $N$.

###  1.1 Notations and main results

Let $\mathbb{T}$ be a rooted $d$-ary tree, where $d\geq 2$. The depth of a
vertex $v\in\mathbb{T}$ is denoted by $\absolutevalue{v}$. We denote the root
by $\varnothing$, and any vertex $v$ with depth $n\geq 1$ is indexed by a
string $v_{1}\cdots v_{n}\in\\{1,\ldots,d\\}^{n}$. For any $v,w\in\mathbb{T}$,
we write $v\leq w$ if $v$ is a prefix of $w$ and write $v<w$ if $v$ is a
prefix of $w$ strictly shorter than $w$. We denote $\mathbb{T}_{n}$ to be the
subtree of $\mathbb{T}$ containing vertices of depth less or equal to $n$ and
$\partial\mathbb{T}_{n}$ to be the leaves of $\mathbb{T}_{n}$.

Let $\mathbf{Y}=(Y_{0},\ldots,Y_{d-1})$ be a $d$-dimensional random vector.
Let $(\mathbf{Y}^{v})_{v\in\mathbb{T}}$ be iid copies of $\mathbf{Y}$ where
$\mathbf{Y}^{v}=(Y_{v0},\ldots,Y_{v(d-1)})$ – this uniquely defines $Y_{u}$
for every $u\in\mathbb{T}\backslash\\{\varnothing\\}$. Define the process
$\mathbf{X}=(X_{v})_{v\in\mathbb{T}}$ by

$\displaystyle\begin{cases}X_{\varnothing}=0,&\\\\[6.0pt]
X_{v}=\sum_{\varnothing<w\leq v}Y_{w},&\absolutevalue{v}\geq 1.\end{cases}$

The process $\mathbf{X}$ is called the _branching random walk with increments
$\mathbf{Y}$_.

It is well-known that $\mathbf{X}$ has the branching property: let
$\mathscr{F}=(\mathscr{F}_{n})_{n\geq 0}$ be its natural filtration. For any
$v\in\mathbb{T}$ with $\absolutevalue{v}=n$, define

$\mathbf{X}^{v}=(X^{v}_{w})_{\absolutevalue{w}\geq
0}=(X_{vw}-X_{v})_{\absolutevalue{w}\geq 0}.$

Then $(\mathbf{X}^{v})_{|v|=n}$ are iid copies of $\mathbf{X}$ and independent
of $\mathscr{F}_{n}$.

#### Gibbs measures.

Define the following function

$\displaystyle\varphi(\beta)=\log\left(\mathbb{E}\left[\sum_{i=0}^{d-1}e^{\beta
Y_{i}}\right]\right)\in(-\infty,\infty],\quad\beta\in\mathbb{R},$

and set $\mathcal{D}(\varphi)=\\{\beta\in\mathbb{R}:\varphi(\beta)<\infty\\}$.
It is well known that $\varphi$ is convex and that it is smooth on
$\mathcal{D}(\varphi)^{\circ}$, the interior of $\mathcal{D}(\varphi)$.
Throughout the article, we assume the following.

######  Assumption 1.1.

$0\in\mathcal{D}(\varphi)^{\circ}$.

For $n\in\mathbb{N}$, define the following (normalized) partition functions

$\displaystyle W_{\beta,n}$ $\displaystyle=\sum_{\absolutevalue{v}=n}e^{\beta
X_{v}-\varphi(\beta)n},\quad n\geq 0,$ $\displaystyle W^{u}_{\beta,n}$
$\displaystyle=\sum_{\absolutevalue{w}=n}e^{\beta
X_{w}^{u}-\varphi(\beta)n},\quad u\in\mathbb{T}\text{ and }n\geq 0.$

Note that for every $m\leq n$,

$\displaystyle W_{\beta,n}=\sum_{\absolutevalue{u}=m}e^{\beta
X_{u}-\varphi(\beta)m}\cdot W^{u}_{\beta,n-m}.$ (1.1)

For $\beta\in\mathbb{R}$ and $n\in\mathbb{N}$, we now define the Gibbs measure
of parameter $\beta$ on $\mathbb{T}_{n}$ to be

$\displaystyle\mu_{\beta,n}(u)=e^{\beta
X_{u}-\varphi(\beta)m}\cdot\frac{W^{u}_{\beta,n-m}}{W_{\beta,n}},\quad\absolutevalue{u}=m\leq
n.$ (1.2)

Note that $\mu_{\beta,n}$ is usually defined on $\partial\mathbb{T}_{n}$ only,
but it will be helpful to define it on the whole tree $\mathbb{T}_{n}$. By
(1.1), for every $m\leq n$, the restriction of $\mu_{\beta,n}$ to
$\partial\mathbb{T}_{m}$ is a probability measure. Similarly, we can define

$\displaystyle\mu_{\beta,n}^{v}(u)=e^{\beta
X^{v}_{u}-\varphi(\beta)m}\cdot\frac{W^{vu}_{\beta,n-m}}{W^{v}_{\beta,n}},\quad
v\in\mathbb{T}\text{ and }\absolutevalue{u}=m\leq n.$ (1.3)

The free energy of the branching random walk has been calculated by Derrida
and Spohn [16] (and can also be deduced from Biggins [10])

$\lim_{n\to\infty}\frac{1}{\beta n}\log\sum_{\absolutevalue{v}=n}e^{\beta
X_{v}}=\begin{cases}\frac{1}{\beta}\varphi(\beta)&\text{if
$\beta\in(0,\beta_{c})$}\\\ \frac{1}{\beta_{c}}\varphi(\beta_{c})&\text{if
$\beta\geq\beta_{c}$},\end{cases}$

where the limit is meant to be in probability and where the critical inverse
temperature $\beta_{c}$ is defined by

$\beta_{c}=\sup\\{\beta\in\mathcal{D}(\varphi)^{\circ}\mid\beta\varphi^{\prime}(\beta)<\varphi(\beta)\\}\in(0,\infty].$

We will mostly be interested in the phase $\beta<\beta_{c}$. In this phase, we
recall the following result.

######  Fact 1.2 ([21, 11, 24]).

If $\beta<\beta_{c}$, then the martingale $(W_{\beta,n})_{n\geq 0}$ is
uniformly integrable. In fact, there exists a (strictly) positive random
variable $W_{\beta,\infty}$ with $\mathbb{E}[W_{\beta,\infty}]=1$ and such
that $W_{\beta,n}\to W_{\beta,\infty}$ almost surely and in $L^{1}$ as
$n\to\infty$.

#### Algorithms.

We define an algorithmic model similar to the ones in [28, 1]. Let
$N\in\mathbb{N}$. A random sequence $\mathrm{v}=(v(k))_{k\geq 0}$ taking
values in $\mathbb{T}_{N}$ is called a _(randomized) algorithm_ if
$v(0)=\varnothing$ and $v(k+1)$ is $\tilde{\mathscr{F}}_{k}$-measurable for
every $k\geq 0$. Here,

$\tilde{\mathscr{F}}_{k}=\sigma\left(v(1),\ldots,v(k);\,X_{v(1)},\ldots,X_{v(k)};\,U_{1},\ldots,U_{k+1}\right)$

where $(U_{k})_{k\geq 1}$ is a sequence of iid uniform random variables on
$[0,1]$, independent of the branching random walk $\mathbf{X}$. Roughly
speaking, the filtration $\tilde{\mathscr{F}}=(\tilde{\mathscr{F}}_{k})_{k\geq
0}$ contains all information about everything we have queried so far, as well
as the additional randomness needed to choose the next vertex. We further
suppose that there exists a stopping time $\tau$ with respect to the
filtration $\tilde{\mathscr{F}}$ and such that
$v(\tau)\in\partial\mathbb{T}_{N}$. We call $\tau$ the _running time_ and
$v(\tau)$ the _output_ of the algorithm. The _law of the output_ is the
(random) distribution of $v(\tau)$, conditioned on the branching random walk.

Often, we will consider a family of algorithms indexed by $N$, which we also
call an algorithm by abuse of notation. We say that the algorithm is a
polynomial-time algorithm if there exists a (deterministic) polynomial $P(N)$
such that $\tau\leq P(N)$ almost surely.

Fix $M\in\mathbb{N}$. Given a configuration of the branching random walk of
depth $N$, consider the following algorithm (See Figure 1):

set $v=\varnothing$;

while  _$\absolutevalue{v} <N$_ do

choose $w$ with $\absolutevalue{w}=M\wedge(N-\absolutevalue{v})$ according to
the Gibbs measure $\mu^{v}_{\beta,M\wedge(N-\absolutevalue{v})}$;

replace $v$ with $vw$;

output $v$

Algorithm 1 Recursive sampling on $M$-renormalized tree Figure 1: Schematic
illustration of Algorithm 1 with $N=5$ and $M=2$ on a given configuration of
the binary branching random walk. The squares are the vertices that the
algorithm chooses at each step, and the thick line is the path from the root
to the sampled vertex. The bar charts represent the Gibbs measures from which
the algorithm samples at each step, and the check mark indicates which vertex
is chosen. Note that the histograms are not drawn to scale.

######  Remark 1.3.

It is easy to see that Algorithm 1 can be formally written as a randomized
algorithm according to the above algorithmic model. Furthermore, its running
time is deterministic and bounded by $\lceil N/M\rceil 2^{M}$. The law of its
output is a random probability measure $\mu_{\beta,M,N}$ on
$\partial\mathbb{T}_{N}$ that can be recursively defined as follows:

$\begin{split}\mu_{\beta,M,0}(\varnothing)&=1\\\
\mu_{\beta,M,N\wedge(K+1)M}(vw)&=\mu_{\beta,M,KM}(v)\cdot\mu^{v}_{\beta,M\wedge(N-KM)}(w)\end{split}$
(1.4)

for all $\absolutevalue{v}=KM$, $\absolutevalue{w}=M\wedge(N-KM)$ and $0\leq
K\leq\left\lfloor\frac{N}{M}\right\rfloor$.

#### Approximation and threshold.

Given two probability measures $P$ and $Q$ defined on a discrete space
$\Omega$, the entropy of $Q$ and the Kullback–Leibler divergence from $Q$ to
$P$ are respectively defined by

$\displaystyle H(Q)$
$\displaystyle=\sum_{\omega\in\Omega}Q(\omega)\cdot\log\left(\frac{1}{Q(\omega)}\right)$
(1.5) $\displaystyle\mathbf{d}(P\;||\;Q)$
$\displaystyle=\sum_{\omega\in\Omega}P(\omega)\cdot\log\left(\frac{P(\omega)}{Q(\omega)}\right).$
(1.6)

Note that by Jensen’s inequality, the entropy and the Kullback–Leibler
divergence are non-negative. In what follows, we will often take $P$ and/or
$Q$ to be a Gibbs measure $\mu_{\beta,N}$ for some $N$. In that case, we set
$\Omega=\partial\mathbb{T}_{n}$, where $n$ is the largest number such that
both $P$ and $Q$ are defined on $\partial\mathbb{T}_{n}$.

The following lemma is folklore. For completeness, we provide a proof in
Section 6.

######  Lemma 1.4.

  1. 1.

If $\beta\in[0,\beta_{c})$, then $H(\mu_{\beta,N})/N$ converges in probability
to a positive constant as $N\to\infty$.

  2. 2.

If $\beta>\beta_{c}$ and if $\beta_{c}\in\mathcal{D}(\varphi)^{\circ}$, then
$H(\mu_{\beta,N})=O(1)$ in probability, as $N\to\infty$. In other words, the
sequence of random variables $(H(\mu_{\beta,N}))_{N\geq 1}$ is tight.

We are interested in the _algorithmically efficient approximation_ of the
Gibbs measure $\mu_{\beta,N}$. The notion of approximation we will use is the
following.

######  Definition 1.5.

Let $\beta\geq 0$. We say that a sequence of random probability measures
$(\tilde{\mu}_{\beta,N})_{N\geq 1}$ _approximates_ the Gibbs measure
$\mu_{\beta,N}$ if

$\frac{\mathbf{d}(\tilde{\mu}_{\beta,N}\;||\;\mu_{\beta,N})}{H(\mu_{\beta,N})}\to
0\;\;\text{in probability as $N\to\infty$}.$ (1.7)

######  Remark 1.6.

More generally, assume that we are given two sequences of probability measures
$(P_{N})_{N\geq 1}$ and $(Q_{N})_{N\geq 1}$ satisfying $H(Q_{N})/N\to
C\in(0,\infty)$ and

$\displaystyle\frac{1}{N}\mathbf{d}(P_{N}\;||\;Q_{N})\rightarrow
0\quad\text{as}\quad N\rightarrow\infty.$ (1.8)

This has been called _measure equivalence_ or _equivalence in the sense of
specific relative entropy_ in the physics literature [31]. Mathematically,
Equation (1.8) implies the following: if $(A_{N})_{N\geq 1}$ is a sequence of
sets such that $Q_{N}(A_{N})$ convergences to $0$ exponentially fast as
$N\rightarrow\infty$, then we also have $P_{N}(A_{N})\to 0$. Indeed, this is
an easy consequence of Birgé’s inequality (see e.g. Theorem 4.20 in [13]).

#### Main results.

We now state the main theorem of this paper.

######  Theorem 1.7 (Approximation bounds).

Let $N\in\mathbb{N}$, $M\in\llbracket 1,N\rrbracket$, and
$\beta\in[0,\beta_{c})$. Then for all $p\geq 1$, there exists a constant
$C_{1}(p)>0$ such that

$\displaystyle\norm{\mathbf{d}(\mu_{\beta,M,N}\;||\;\mu_{\beta,N})}_{p}\leq
C_{1}(p)\cdot\left\lfloor\frac{N}{M}\right\rfloor.$ (1.9)

Moreover, for all $p\geq 1$, there exists a constant $C_{1}(p)>0$ such that

$\displaystyle\norm{\mathbf{d}(\mu_{\beta,M,N}\;||\;\mu_{\beta,N})-\mathbb{E}\left[\mathbf{d}(\mu_{\beta,M,N}\;||\;\mu_{\beta,N})\right]}_{p}\leq
C_{1}(p).$ (1.10)

By Theorem 1.7, we can derive the following corollary which states the
existence of an algorithm that approximates the Gibbs measure $\mu_{\beta,N}$
efficiently.

######  Corollary 1.8 (Complexity upper bound).

If $\beta\in[0,\beta_{c})$, then there exists a polynomial-time algorithm such
that for every $p>1$, denoting by $\tilde{\mu}_{\beta,N}$ the law of its
output,

$\displaystyle\frac{1}{N}\norm{\mathbf{d}(\tilde{\mu}_{\beta,N}\;||\;\mu_{\beta,N})}_{p}\rightarrow
0$ (1.11)

as $N\rightarrow\infty$. In particular, $\tilde{\mu}_{\beta,N}$ approximates
the Gibbs measure $\mu_{\beta,N}$ in the sense of Definition 1.5.

###### Proof.

Let $M=M(N)$ be a sequence that goes to infinity as $N\rightarrow\infty$, and
set $\tilde{\mu}_{\beta,N}=\mu_{\beta,M,N}$. Equation (1.11) then follows from
(1.9) in Theorem 1.7. Assuming moreover that $M=O(\log N)$, Remark 1.3 implies
that $\tilde{\mu}_{\beta,N}$ can be computed by a polynomial-time algorithm.
The second statement follows from the first part of Lemma 1.4. ∎

Finally, we also provide a hardness result, assuming a mild regularity
condition.

######  Theorem 1.9 (Complexity lower bound).

Assume $\beta_{c}\in\mathcal{D}(\varphi)^{\circ}$ (in particular,
$\beta_{c}<\infty$). Let $\beta>\beta_{c}$. Let $v=(v(k))_{k\geq 0}$ be an
algorithm which outputs a vertex of law $\tilde{\mu}_{N}$ such that
$\tilde{\mu}_{N}$ approximates the Gibbs measure $\mu_{\beta,N}$ in the sense
of Definition 1.5. Let $\tau$ be the running time of the algorithm. Then for
every $\delta>0$, there exists $z>0$, such that for large enough $N$,

$\mathbb{P}\left(\tau\geq e^{z\sqrt{N}}\right)\geq 1-\delta.$

###  1.2 Related work

An early study on searching algorithms on the branching random walk can be
found in Karp and Pearl [22]. They considered the binary branching random walk
with Bernoulli increments $\text{Ber}(p)$, and they showed that for $p>1/2$
and $p=1/2$, they gave an algorithm that can find an exact maximal vertex in
linear and quadratic expected time, respectively. While for $p<1/2$, it is
possible to find an approximate maximal vertex in linear time with high
probability using a depth-first search on a renormalized tree. Aldous [5] gave
a different algorithm and, among other things, extended the result of Karp and
Pearl [22] to general increment distributions. A hardness result was obtained
by Pemantle [28]. Among other things, he showed for the binary branching
random walk with Bernoulli increments with mean $p<1/2$ that any search
algorithm which finds a vertex within a $(1-\varepsilon)$ factor of the
maximum with high probability needs at least
$N\times\exp(\Theta(\varepsilon^{-1/2}))$ with high probability.111To be
precise, this explicit bound relied on a conjecture on branching random walk
killed at a linear space-time barrier (Conjecture 1 in [28]), which was
subsequently proven to be true [9, 19].

As mentioned above, Addario-Berry and Maillard [1] considered this
optimization problem for the continuous random energy model (CREM), which is a
binary time-inhomogeneous branching random walk with Gaussian displacements,
proving the existence of an threshold $x_{*}$ such that the following holds:
a) for every $x<x_{*}$, there exists a polynomial-time algorithm that finds a
vertex with $X_{v}\geq xN$ with high probability, b) for every $x>x_{*}$,
every such algorithm has a running time which is at least exponential in $N$
with high probability.

The CREM, introduced by Bovier and Kurkova [14] based on previous work by
Derrida and Spohn [16], is a toy model of a disordered system in statistical
physics, i.e. a model where the Hamiltonian – the function that assigns
energies to the states of the system – is itself random. These systems have
recently seen a lot of interest in the mathematical literature with regards to
efficient algorithms for finding low-energy states. A key quantity of
importance in these models is the so-called _overlap_ between two states, a
measure of their correlation. In the case of the CREM, it is equal to the
depth of the most recent common ancestor of two vertices, divided by $N$.
Then, for a given $\beta>0$, the _overlap distribution_ is the limiting law
(as $N\to\infty$) of the overlap of two vertices sampled independently
according to the Gibbs measure with inverse temperature $\beta$. A picture
that has emerged is that the existence of a gap in the support of the overlap
distribution, the so-called “overlap gap property”, is an obstruction to the
existence of efficient algorithms finding approximate minimizers of the
Hamiltonian. This has been rigorously proven for a certain class of algorithms
by Gamarnik and Jagannath [18] in the case of the Ising $p$-spin model, with
$p\geq 4$. On the other hand, Montanari [26] showed that for $p=2$, the
Sherrington–Kirkpatrick model, there exists a quadratic time algorithm that
can find near optimal state with high probability, assuming a widely believed
conjecture that this model does not exhibit an overlap gap. A similar result
for spherical spin glass models (for which the overlap distribution is
explicitly known) has been obtained by Subag [30].

The question of efficient _sampling_ of the Gibbs measure of a disordered
system seems to have been considered mostly under the angle of Glauber or
Langevin dynamics. See e.g. [7, 20] for the spherical spin glass model. We
restrict ourselves here to the case of the Sherrington–Kirkpatrick model. For
this model, it has been recently obtained that fast mixing occurs for
$\beta<1/4$ [8, 17]. However, very recently, El Alaoui, Montanari and Sellke
[3] have provided another algorithm which yields fast mixing for $\beta<1/2$,
and they conjecture that this in fact holds for all $\beta<1$. They also
provide a hardness result for $\beta>1$ for a certain class of algorithms.
Their algorithm for the $\beta<1/2$ phase belongs to the class of _approximate
message passing_ algorithms, which is also the case for Montanari’s algorithm
for the optimization problem [26]. This illustrates the fact that Glauber or
Langevin dynamics may in general not be optimal sampling algorithms, and that
algorithms which exploit the underlying tree structure of the model may be
efficient in a wider range of the parameters. For a discussion of this
question in the context of statistical inference problems, see e.g. [6].
Altogether, this motivates the study of tree-based models as a toy problem,
such as the one from the present article.

#### Outline.

The paper is organized as follows. In Section 2, we prove that the
Kullback–Leibler divergence can be decomposed into a weighted sum of the
Kullback–Leibler divergences on subtrees. In Section 3, we give $L^{p}$ bounds
of the logarithm of Biggins’ martingales and $L^{p}$ bounds of the
Kullback–Leibler divergences between two Gibbs measures. Theorem 1.7 is proven
in Section 4 and Theorem 1.9 in Section 5. Section 6 provides the proof of
Lemma 1.4. Finally, we state in Section 7 some open questions that might
interest the readers.

##  2 Decomposition of the Kullback–Leibler divergence

The main goal of this section is to prove Theorem 2.2. Before proving the
theorem, we need the following lemma, which states that the weight of
$u_{1}u_{2}$ with respect to the Gibbs measure $\mu_{\beta,m}$ can be
decomposed into the product of the weights of $u_{1}$ and $u_{2}$ with respect
to another two Gibbs measures.

######  Lemma 2.1.

For any $\absolutevalue{u_{1}}=m_{1}$ and $\absolutevalue{u_{2}}=m_{2}$, we
have the decomposition

$\displaystyle\mu_{\beta,m}(u_{1}u_{2})=\mu_{\beta,m}(u_{1})\cdot\mu_{\beta,m-m_{1}}^{u_{1}}(u_{2})$

for all $m\geq m_{1}+m_{2}$.

###### Proof.

By computation, we have

$\displaystyle\mu_{\beta,m}(u_{1}u_{2})$ $\displaystyle=\frac{e^{\beta
X_{u_{1}u_{2}}-\varphi(\beta)m}\cdot
W_{\beta,m-m_{1}-m_{2}}^{u_{1}u_{2}}}{W_{\beta,m}}$
$\displaystyle=\frac{e^{\beta X_{u_{1}}-\varphi(\beta)m_{1}}\cdot
W_{\beta,m-m_{1}}^{u_{1}}}{W_{\beta,m}}\cdot\frac{e^{\beta
X_{u_{2}}^{u_{1}}-\varphi(\beta)(m-m_{1})}\cdot
W_{\beta,m-m_{1}-m_{2}}^{u_{1}u_{2}}}{W_{\beta,m-m_{1}}^{u_{1}}}$
$\displaystyle=\mu_{\beta,m}(u_{1})\cdot\mu_{\beta,m-m_{1}}^{u_{1}}(u_{2}),$

where the last equality is by (1.2) and (1.3). ∎

Now we can decompose the Kullback–Leibler divergence as follows.

######  Theorem 2.2.

For any two $M$ and $N$ integers such that $M\leq N$, we have

$\displaystyle\mathbf{d}(\mu_{\beta,M,N}\;||\;\mu_{\beta,N})=\sum_{K=0}^{\lfloor\frac{N}{M}\rfloor-1}\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)\cdot\mathbf{d}(\mu_{\beta,M}^{u}\;||\;\mu_{\beta,N-KM}^{u}).$
(2.1)

###### Proof.

Denote $N^{\prime}=\lfloor\frac{N}{M}\rfloor\cdot M$ for simplicity. By (1.4)
and Lemma 2.1, for all $\absolutevalue{u_{1}}=N^{\prime}$ and
$\absolutevalue{u_{2}}=N-N^{\prime}$, we have

$\displaystyle\log\left(\frac{\mu_{\beta,M,N}(u_{1}u_{2})}{\mu_{\beta,N}(u_{1}u_{2})}\right)=\log\left(\frac{\mu_{\beta,M,N^{\prime}}(u_{1})\cdot\mu_{\beta,N-N^{\prime}}^{u_{1}}(u_{2})}{\mu_{\beta,N}(u_{1})\cdot\mu_{\beta,N-N^{\prime}}^{u_{1}}(u_{2})}\right)=\log\left(\frac{\mu_{\beta,M,N^{\prime}}(u_{1})}{\mu_{\beta,M,N}(u_{1})}\right).$
(2.2)

Thus, the Kullback–Leibler divergence can be rewritten as

$\displaystyle\mathbf{d}(\mu_{\beta,M,N}\;||\;\mu_{\beta,N})$
$\displaystyle=\sum_{\absolutevalue{u}=N}\mu_{\beta,M,N}(u)\cdot\log\left(\frac{\mu_{\beta,M,N}(u)}{\mu_{\beta,N}(u)}\right)$
$\displaystyle=\sum_{\absolutevalue{u_{1}}=N^{\prime}}\sum_{\absolutevalue{u_{2}}=N-N^{\prime}}\mu_{\beta,M,N}(u_{1}u_{2})\cdot\log\left(\frac{\mu_{\beta,M,N}(u_{1}u_{2})}{\mu_{\beta,N}(u_{1}u_{2})}\right)$
$\displaystyle=\sum_{\absolutevalue{u_{1}}=N^{\prime}}\sum_{\absolutevalue{u_{2}}=N-N^{\prime}}\mu_{\beta,M,N^{\prime}}(u_{1})\cdot\mu_{\beta,N-N^{\prime}}^{u_{1}}(u_{2})\cdot\log\left(\frac{\mu_{\beta,M,N^{\prime}}(u_{1})}{\mu_{\beta,N}(u_{1})}\right)$
(by (1.4) and (2.2))
$\displaystyle=\sum_{\absolutevalue{u_{1}}=N^{\prime}}\mu_{\beta,M,N^{\prime}}(u_{1})\cdot\log\left(\frac{\mu_{\beta,M,N^{\prime}}(u_{1})}{\mu_{\beta,N}(u_{1})}\right)$
$\displaystyle=\mathbf{d}(\mu_{\beta,M,N^{\prime}}\;||\;\mu_{\beta,N}).$ (2.3)

Next, by (1.4) and Lemma 2.1, for all $\absolutevalue{u_{1}}=KM$,
$\absolutevalue{u_{2}}=M$ and $0\leq K\leq\lfloor\frac{N}{M}\rfloor-1$, we
have

$\displaystyle\log\left(\frac{\mu_{\beta,M,(K+1)M}(u_{1}u_{2})}{\mu_{\beta,N}(u_{1}u_{2})}\right)$
$\displaystyle=\log\left(\frac{\mu_{\beta,M,KM}(u_{1})\cdot\mu_{\beta,M}^{u_{1}}(u_{2})}{\mu_{\beta,N}(u_{1})\cdot\mu_{\beta,N-KM}^{u_{1}}(u_{2})}\right)$
$\displaystyle=\log\left(\frac{\mu_{\beta,M,KM}(u_{1})}{\mu_{\beta,N}(u_{1})}\right)+\log\left(\frac{\mu_{\beta,M}^{u_{1}}(u_{2})}{\mu_{\beta,N-KM}^{u_{1}}(u_{2})}\right).$
(2.4)

Thus,

$\displaystyle\mathbf{d}(\mu_{\beta,M,(K+1)M}\;||\;\mu_{\beta,N})$
$\displaystyle=\sum_{\absolutevalue{u}=(K+1)M}\mu_{\beta,M,(K+1)M}(u)\cdot\log\left(\frac{\mu_{\beta,M,(K+1)M}(u)}{\mu_{\beta,N}(u)}\right)$
$\displaystyle=\sum_{\absolutevalue{u_{1}}=KM}\sum_{\absolutevalue{u_{2}}=M}\mu_{\beta,M,KM}(u_{1})$
$\displaystyle\qquad\cdot\mu_{\beta,M}^{u_{1}}(u_{2})\cdot\left[\log\left(\frac{\mu_{\beta,M,KM}(u_{1})}{\mu_{\beta,N}(u_{1})}\right)+\log\left(\frac{\mu_{\beta,M}^{u_{1}}(u_{2})}{\mu_{\beta,N-KM}^{u_{1}}(u_{2})}\right)\right]$
(by (1.4) and (2.4))
$\displaystyle=\mathbf{d}(\mu_{\beta,M,KM}\;||\;\mu_{\beta,N})+\sum_{\absolutevalue{u_{1}}=KM}\mu_{\beta,M,KM}(u_{1})\cdot\mathbf{d}(\mu_{\beta,M}^{u_{1}}\;||\;\mu_{\beta,N-KM}^{u_{1}}).$
(2.5)

Finally, by (2.3), (2.5) and the fact that
$\mathbf{d}(\mu_{\beta,M,0}\;||\;\mu_{\beta,N})=0$, we derive (2.1). ∎

Next, we show that the Kullback–Leibler divergence between two Gibbs measures
can be written in terms of the logarithms of the partition functions.

######  Proposition 2.3.

For any two $M$ and $N$ integers such that $M\leq N$, we have

$\displaystyle\mathbf{d}(\mu_{\beta,M}\;||\;\mu_{\beta,N})=\log
W_{\beta,N}-\log
W_{\beta,M}-\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)\cdot\log
W^{u}_{\beta,N-M}.$ (2.6)

###### Proof.

For any $\absolutevalue{u}=M$, we have

$\displaystyle\frac{\mu_{\beta,M}(u)}{\mu_{\beta,N}(u)}=\frac{e^{\beta
X_{u}-\varphi(\beta)M}\cdot\frac{1}{W_{\beta,M}}}{e^{\beta
X_{u}-\varphi(\beta)M}\cdot\frac{W_{\beta,N-M}^{u}}{W_{\beta,N}}}=\frac{W_{\beta,N}}{W_{\beta,M}\cdot
W^{u}_{\beta,N-M}}.$

Thus,

$\displaystyle\mathbf{d}(\mu_{\beta,M}\;||\;\mu_{\beta,N})$
$\displaystyle=\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)\cdot\log\left(\frac{\mu_{\beta,M}(u)}{\mu_{\beta,N}(u)}\right)$
$\displaystyle=\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)\cdot\left(\log
W_{\beta,N}-\log W_{\beta,M}-\log W_{\beta,N-M}^{u}\right)$
$\displaystyle=\log W_{\beta,N}-\log
W_{\beta,M}-\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)\cdot\log
W^{u}_{\beta,N-M}.$

This completes the proof. ∎

##  3 Some $L^{p}$ bounds

We first show that whenever $\beta\in[0,\beta_{c})$, $(\log
W_{\beta,n})_{n\geq 0}$ is bounded in $L^{p}$ for all $p>1$.

######  Lemma 3.1.

Let $\beta\in[0,\beta_{c})$. Then $(\log W_{\beta,n})_{n\geq 0}$ is a
supermartingale such that

$\sup_{n\geq 0}\norm{\log W_{\beta,n}}_{p}<\infty,\quad p\geq 1.$

###### Proof.

The supermartingale property of $(\log W_{\beta,n})_{n\geq 0}$ follows from
the fact that $(W_{\beta,n})_{n\geq 0}$ is a martingale and $x\mapsto\log x$
is a concave function.

Now let $p\geq 1$. Since $\beta<\beta_{c}$, by Fact 1.2, we derive that

$\sup_{n\geq 0}\norm{W_{\beta,n}}_{1}<\infty$

Furthermore, using Assumption 1.1 and Liu [23, Theorem 2.4], we have for some
$s>0$,

$\sup_{n\geq 0}\|W_{\beta,n}^{-s}\|_{1}<\infty.$

Then by the fact that

$\displaystyle\absolutevalue{\log x}^{p}\leq
C\left(\absolutevalue{x}+\absolutevalue{x}^{-s}\right)$

for some constant $C>0$, we have

$\displaystyle\sup_{n\geq 0}\norm{\log W_{\beta,n}}_{p}^{p}\leq
C\cdot\sup_{n\geq
0}\left(\norm{W_{\beta,n}}_{1}+\|W_{\beta,n}^{-s}\|_{1}\right)<\infty.$

This proves the lemma. ∎

Lemma 3.1 implies the following proposition about the boundedness of the
Kullback–Leibler divergence between two Gibbs measures.

######  Proposition 3.2.

For any $p>1$, for any two integers $M$ and $N$ such that $M\leq N$, there
exists a constant $C(p)>0$ such that

$\norm{\mathbf{d}(\mu_{\beta,M}\;||\;\mu_{\beta,N})}_{p}\leq C(p).$

###### Proof.

By Minkowski’s inequality and Proposition 2.3, we have

$\displaystyle\norm{\mathbf{d}(\mu_{\beta,M}\;||\;\mu_{\beta,N})}_{p}\leq\norm{\log
W_{\beta,N}}_{p}+\norm{\log
W_{\beta,M}}_{p}+\norm{\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)\cdot\log
W^{u}_{\beta,N-M}}_{p}.$

Since the first and the second term above are bounded by Lemma 3.1, it
suffices to prove that the third term above is bounded. By the branching
property and Jensen’s inequality, we have

$\displaystyle\mathbb{E}\left[\absolutevalue{\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)\cdot\log
W^{u}_{\beta,M}}^{p}\,\middle|\,\mathscr{F}_{M}\right]$
$\displaystyle\leq\mathbb{E}\left[\absolutevalue{\log
W_{\beta,N-M}}^{p}\right].$ (3.1)

Therefore, by (3.1),

$\displaystyle\norm{\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)\cdot\log
W^{u}_{\beta,N-M}}_{p}\leq\norm{\log W_{\beta,N-M}}_{p}.$ (3.2)

Finally, we conclude by (3.2) and Lemma 3.1 that

$\displaystyle\norm{\mathbf{d}(\mu_{\beta,M}\;||\;\mu_{\beta,N})}_{p}\leq
3\cdot\sup_{n\geq 0}\norm{\log W_{\beta,n}}_{p}<\infty,$

and the proof is completed. ∎

##  4 Proof of Theorem 1.7

In this section, we prove (1.9) and (1.10) of Theorem 1.7. The proof of (1.9)
relies essentially on the decomposition theorem of the Kullback–Leibler
divergence (Theorem 2.2) and Proposition 3.2. The proof of (1.10) needs more
precise moment estimates.

###  4.1 Proof of (1.9)

Let $p\geq 1$. By Theorem 2.2 and Minkowski’s inequality, we have

$\displaystyle\norm{\mathbf{d}(\mu_{\beta,M,N}\;||\;\mu_{\beta,N})}_{p}$
$\displaystyle=\norm{\sum_{K=0}^{\lfloor\frac{N}{M}\rfloor-1}\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)\cdot\mathbf{d}(\mu_{\beta,M}^{u}\;||\;\mu_{\beta,N-KM}^{u})}_{p}$
$\displaystyle\leq\sum_{K=0}^{\lfloor\frac{N}{M}\rfloor-1}\norm{\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)\cdot\mathbf{d}(\mu_{\beta,M}^{u}\;||\;\mu_{\beta,N-KM}^{u})}_{p}.$
(4.1)

Let $K\leq\lfloor N/M\rfloor-1$. Applying Jensen’s inequality to
$\mu_{\beta,M,KM}$, we have

$\displaystyle\mathbb{E}\left[\absolutevalue{\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)\cdot\mathbf{d}(\mu_{\beta,M}^{u}\;||\;\mu_{\beta,N-KM}^{u})}^{p}\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)\cdot\absolutevalue{\mathbf{d}(\mu_{\beta,M}^{u}\;||\;\mu_{\beta,N-KM}^{u})}^{p}\right].$
(4.2)

Then by the law of iterated expectation and the branching property, (4.2) is
equal to

$\displaystyle\mathbb{E}\left[\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)\cdot\mathbb{E}\left[\absolutevalue{\mathbf{d}(\mu_{\beta,M}^{u}\;||\;\mu_{\beta,N-KM}^{u})}^{p}\,\middle|\,\mathscr{F}_{KM}\right]\right]$
$\displaystyle=\mathbb{E}\left[\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)\right]\cdot\mathbb{E}\left[\absolutevalue{\mathbf{d}(\mu_{\beta,M}\;||\;\mu_{\beta,N-KM})}^{p}\right]=\mathbb{E}\left[\absolutevalue{\mathbf{d}(\mu_{\beta,M}\;||\;\mu_{\beta,N-KM})}^{p}\right].$
(4.3)

Combining (4.1), (4.3) and Proposition 3.2, we conclude that

$\displaystyle\norm{\mathbf{d}(\mu_{\beta,M,N}\;||\;\mu_{\beta,N})}_{p}\leq\left\lfloor\frac{N}{M}\right\rfloor\cdot
C(p).$

###  4.2 Proof of (1.10)

In this section, we prove (1.10) which gives a tighter control on the
Kullback–Leibler divergence between $\mu_{\beta,M,N}$ and the Gibbs measure
$\mu_{\beta,N}$. We start with the following simple lemma.

######  Lemma 4.1.

Let $\beta\in[0,\beta_{c})$. For all $M\in\mathbb{N}$, there exists
$r\in(0,1)$ independent of $M$ such that,

$\displaystyle\mathbb{E}\left[\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)^{2}\right]\leq
r$ (4.4)

Moreover, for all $K\in\mathbb{N}$,

$\displaystyle\mathbb{E}\left[\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\right]\leq
r^{K}.$ (4.5)

###### Proof of Lemma 4.1.

For $x\in(0,1)$, $x^{2}<x$. Thus, by the fact that $\mu_{\beta,M}(u)\in(0,1)$
for all $\absolutevalue{u}=M$, we derive that

$\displaystyle\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)^{2}<\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)=1,$

for every $M\in\mathbb{N}$. This shows that (4.4) holds for every fixed
$M\in\mathbb{N}$ and with $r<1$ possibly depending on $M$. Uniformity in $M$
follows as soon as we show that

$\limsup_{M\to\infty}\mathbb{E}\left[\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)^{2}\right]<1.$

To this end, recall that $W_{\beta,M}\to W_{\beta,\infty}$ almost surely as
$M\to\infty$ and that $\mathbb{E}[W_{\beta,\infty}]=1$. Hence, there exist
$a<1$ and $M_{0}\in\mathbb{N}$ such that

$\forall M\geq M_{0}:\mathbb{P}(W_{\beta,M}<1/2)\leq a.$ (4.6)

Now fix $p\in(1,2]$ such that $\varphi(p\beta)<p\varphi(\beta)$, which exists
because $\beta<\beta_{c}$. Then decompose:

$\displaystyle\mathbb{E}\left[\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)^{p}\right]$
$\displaystyle\leq\mathbb{E}\left[\left(\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)^{p}\right)\boldsymbol{1}_{W_{\beta,M}<1/2}\right]+\mathbb{E}\left[\left(\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)^{p}\right)\boldsymbol{1}_{W_{\beta,M}\geq
1/2}\right]$
$\displaystyle\leq\mathbb{P}(W_{\beta,M}<1/2)+2^{p}e^{(\varphi(p\beta)-p\varphi(\beta))M},$

using the definition of $\mu_{\beta,M}(u)$ for the last inequality. This shows
that

$\limsup_{M\to\infty}\mathbb{E}\left[\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)^{2}\right]\leq
a,$

which concludes the proof of (4.4).

We now show (4.5) by induction. The case $K=1$ follows directly from (1.4) and
(4.4). For $K>1$, by (1.4) and branching property, we obtain that

$\displaystyle\mathbb{E}\left[\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\,\middle|\,\mathscr{F}_{(K-1)M}\right]$
(4.7)
$\displaystyle=\mathbb{E}\left[\sum_{\absolutevalue{u_{1}}=(K-1)M}\sum_{\absolutevalue{u_{2}}=M}\mu_{\beta,M,(K-1)M}(u_{1})^{2}\cdot\mu_{\beta,M}^{u_{1}}(u_{2})^{2}\,\middle|\,\mathscr{F}_{(K-1)M}\right]$
$\displaystyle=\sum_{\absolutevalue{u_{1}}=(K-1)M}\mu_{\beta,M,(K-1)M}(u_{1})^{2}\cdot\mathbb{E}\left[\sum_{\absolutevalue{u_{2}}=M}\mu_{\beta,M}(u_{2})^{2}\right].$
(4.8)

Taking expectations, we derive that

$\displaystyle\mathbb{E}\left[\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\right]=\mathbb{E}\left[\sum_{\absolutevalue{u}=(K-1)M}\mu_{\beta,M,(K-1)M}(u)^{2}\right]\cdot\mathbb{E}\left[\sum_{\absolutevalue{u}=M}\mu_{\beta,M}(u)^{2}\right].$
(4.9)

The equation (4.5) then follows from the induction hypothesis. ∎

We now proceed with the proof of (1.10). Without loss of generality, using the
fact that $\|\cdot\|_{p}\leq\|\cdot\|_{2}$ for every $p\in[1,2]$, we assume
that $p\geq 2$. By Theorem 2.2 and Minkowski’s inequality, we have

$\displaystyle\norm{\mathbf{d}(\mu_{\beta,M,N}\;||\;\mu_{\beta,N})-\mathbb{E}\left[\mathbf{d}(\mu_{\beta,M,N}\;||\;\mu_{\beta,N})\right]}_{p}$
$\displaystyle\leq\sum_{K=0}^{\lfloor\frac{N}{M}\rfloor-1}\norm{\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)\cdot\left(\mathbf{d}(\mu_{\beta,M}^{u}\;||\;\mu_{\beta,N-KM}^{u})-\mathbb{E}\left[\mathbf{d}(\mu_{\beta,M}^{u}\;||\;\mu_{\beta,N-KM}^{u})\right]\right)}_{p}.$
(4.10)

We now introduce some notation. For all $0\leq
K\leq\lfloor\frac{N}{M}\rfloor-1$, denote

$\displaystyle
d_{K}^{u}=\mathbf{d}(\mu_{\beta,M}^{u}\;||\;\mu_{\beta,N-KM}^{u})\quad\text{and}\quad
d_{K}=\mathbf{d}(\mu_{\beta,M}\;||\;\mu_{\beta,N-KM})$

and

$\displaystyle
Z_{u}=\mu_{\beta,M,KM}(u)\cdot\left(d_{K}^{u}-\mathbb{E}\left[d_{K}^{u}\right]\right).$

We claim that for all $p\geq 1$, the sequence

$\displaystyle a_{K}=\norm{\sum_{\absolutevalue{u}=KM}Z_{u}}_{p}$ (4.11)

is summable, with a bound independent of $M$. This will imply that the right-
hand side of (4.10) is bounded by the same quantity, which completes proof. To
prove this, first observe that $(Z_{u})_{\absolutevalue{u}=KM}$ is a sequence
of iid random variables having zero mean and finite $p$-th moments, for any
$p\geq 1$, with respect to
$\mathbb{E}\left[\,\cdot\,\middle|\,\mathscr{F}_{KM}\right]$, by Proposition
3.2 and the branching property. Denote by $C_{1},C_{2},\ldots$ some constants
possibly depending on $p$ (and $\beta$ and the law of $\mathbf{Y}$). By
Rosenthal’s inequality [29, Theorem 3], we have

$\displaystyle\mathbb{E}\left[\absolutevalue{\sum_{\absolutevalue{u}=KM}Z_{u}}^{p}\,\middle|\,\mathscr{F}_{KM}\right]\leq
C_{1}\cdot\left\\{\left(\sum_{\absolutevalue{u}=KM}\mathbb{E}\left[\absolutevalue{Z_{u}}^{p}\,\middle|\,\mathscr{F}_{KM}\right]\right)+\left(\sum_{\absolutevalue{u}=KM}\mathbb{E}\left[\absolutevalue{Z_{u}}^{2}\,\middle|\,\mathscr{F}_{KM}\right]\right)^{p/2}\right\\}$
(4.12)

By the branching property and Proposition 3.2, the first term of (4.12) can be
bounded by

$\displaystyle\sum_{\absolutevalue{u}=KM}\mathbb{E}\left[\absolutevalue{Z_{u}}^{p}\,\middle|\,\mathscr{F}_{KM}\right]$
$\displaystyle=\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{p}\cdot\mathbb{E}\left[\absolutevalue{d_{K}-\mathbb{E}\left[d_{K}\right]}^{p}\right]$
$\displaystyle\leq\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{p}\cdot
C_{2}$
$\displaystyle\leq\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\cdot
C_{2},$ (4.13)

using that $p\geq 2$ in the last line. Taking expectations and applying Lemma
4.1, we get

$\displaystyle\mathbb{E}\left[\sum_{\absolutevalue{u}=KM}\mathbb{E}\left[\absolutevalue{Z_{u}}^{p}\,\middle|\,\mathscr{F}_{KM}\right]\right]\leq\mathbb{E}\left[\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\right]\cdot
C_{2}\leq r^{K}\cdot C_{2},$ (4.14)

with $r<1$ as in Lemma 4.1.

We now estimate the second term of (4.12). By the branching property and Lemma
3.1,

$\displaystyle\left(\sum_{\absolutevalue{u}=KM}\mathbb{E}\left[\absolutevalue{Z_{u}}^{2}\,\middle|\,\mathscr{F}_{KM}\right]\right)^{p/2}$
$\displaystyle=\left(\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\cdot\mathbb{E}\left[\absolutevalue{d_{K}-\mathbb{E}\left[d_{K}\right]}^{2}\right]\right)^{p/2}$
$\displaystyle\leq\left(\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\right)^{p/2}\cdot
C_{3}$
$\displaystyle\leq\left(\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\right)\cdot
C_{3}.$ (4.15)

The inequality (4.15) is because

$\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\in[0,1]$

and $x^{p/2}\leq x$, for all $x\in[0,1]$ and $p\geq 2$. Taking expectations
and applying Lemma 4.1, we get

$\displaystyle\mathbb{E}\left[\left(\sum_{\absolutevalue{u}=KM}\mathbb{E}\left[\absolutevalue{Z_{u}}^{2}\,\middle|\,\mathscr{F}_{KM}\right]\right)^{p/2}\right]\leq\mathbb{E}\left[\sum_{\absolutevalue{u}=KM}\mu_{\beta,M,KM}(u)^{2}\right]\cdot
C_{3}\leq r^{K}\cdot C_{3}.$ (4.16)

Combining (4.12), (4.14) and (4.16), we conclude that

$\displaystyle\norm{\sum_{\absolutevalue{u}=KM}Z_{u}}_{p}\leq
C_{1}(C_{2}+C_{3})\cdot r^{K}.$

This implies that (4.11) is summable and finishes the proof.

##  5 Proof of hardness result (Theorem 1.9)

In this section, we prove Theorem 1.9. To do this, we recall two results of
asymptotic behaviors of the maximal particle of a branching random walk.

Under the assumption of the theorem, it is known in Corollary (3.4) of [10]
that

$\frac{\max_{|u|=N}X_{u}}{N}\to
m\coloneqq\varphi^{\prime}(\beta_{c}),\quad\text{a.s. as $N\to\infty$}.$ (5.1)

Furthermore, we have the following tail estimate, which easily follows from a
union bound together with Chernoff’s bound (see e.g. the proof of Theorem 2 in
[32]): there exists a constant $c>0$ such that

$\forall x\geq 0:\mathbb{P}\left(\max_{|u|=N}X_{u}\geq mN+x\right)\leq
e^{-cx}.$ (5.2)

The key to Theorem 1.9 is the following observation:

######  Lemma 5.1.

Let $\beta>\beta_{c}$ and assume $\beta_{c}\in\mathcal{D}(\varphi)^{\circ}$.
Let $u$ be a particle sampled according to the Gibbs measure $\mu_{\beta,N}$
and let $w$ be its ancestor at generation $\lfloor N/2\rfloor$. Then there
exists a positive random variable $Z$ with continuous distribution function
such that

$\frac{X_{u}-X_{w}-mN/2}{\sqrt{N}}\to Z,\quad\text{in law as $N\to\infty$}.$

###### Proof.

This is a consequence of a result by Chen, Madaule and Mallein [15]. These
authors show the following fact: if $u$ is sampled according to the Gibbs
measure $\mu_{\beta,N}$, and $X_{u}(t)$ denotes the position of its ancestor
at generation $\lfloor tN\rfloor$, and if we define

$Z^{N}_{t}\coloneqq\frac{mtN-X_{u}(t)}{\sqrt{N}},\quad t\in[0,1],$

then $(Z^{N}_{t})_{t\in[0,1]}$ converges in law (w.r.t. Skorokhod’s topology)
to a multiple of a Brownian excursion as $N\to\infty$. Note that the
assumptions in their article are implied by our hypothesis that
$\beta_{c}\in\mathcal{D}(\varphi)^{\circ}$ and the fact that in our branching
random walk, the number of offspring of a particle is deterministic. Now, we
also have that $X_{u}-mN=O(\log N)$ in probability (see e.g. [2]), so that

$\frac{X_{u}-mN}{\sqrt{N}}\xrightarrow{\text{law}}0,\quad\text{as
$N\to\infty$}.$

Together, both results imply the lemma. ∎

###### Proof of Theorem 1.9.

Assume that we are given an algorithm $(v(k))_{k\geq 1}$ that samples a vertex
according to a random probability measure $\tilde{\mu}_{\beta,N}$
approximating the Gibbs measure $\mu_{\beta,N}$. By Lemma 1.4, it follows that
$\mathbf{d}(\tilde{\mu}_{\beta,N}\;||\;\mu_{\beta,N})\to 0$ in probability as
$N\to\infty$. Hence, by Pinsker’s inequality (see e.g. Theorem 4.19 in [13]),
the total variation distance between $\tilde{\mu}_{\beta,N}$ and
$\mu_{\beta,N}$ goes to 0 as well in probability, as $N\to\infty$. It follows
that Lemma 5.1 holds as well for $u$ sampled according to
$\tilde{\mu}_{\beta,N}$.

Let $\delta>0$. For $z>0$, call a vertex $w\in\partial\mathbb{T}_{\lfloor
N/2\rfloor}$ _$z$ -exceptional_ if it has a descendant
$u\in\partial\mathbb{T}_{N}$ such that $X_{u}-X_{w}-mN/2>z\sqrt{N}$. By the
preceding paragraph, there exists $z>0$ such that for large enough $N$, the
algorithm finds a vertex $u$ whose ancestor $w$ at generation $\lfloor
N/2\rfloor$ is $z$-exceptional with probability at least $1-\delta$. Hence, it
is enough to show that any algorithm which solves the simpler problem of
finding a $z$-exceptional vertex at generation $\lfloor N/2\rfloor$ has a
running time at least $e^{z^{\prime}\sqrt{N}}$ with probability $1-\delta$,
for some $z^{\prime}>0$. We will now show that the statement of the theorem
holds even for this simpler problem. For this, we use an argument similar to
the one in Section 3 of [1]. We first present the argument in an informal way.

Denote by $E_{w}$ the event that a given vertex
$w\in\partial\mathbb{T}_{\lfloor N/2\rfloor}$ is $z$-exceptional. Note that
this event only depends on the displacements of the descendants of $w$. Hence,
the events $(E_{w})_{w\in\partial\mathbb{T}_{\lfloor N/2\rfloor}}$ are
independent by the branching property. Furthermore, by (5.2), for each
$w\in\partial\mathbb{T}_{\lfloor N/2\rfloor}$, we have $\mathbb{P}(E_{w})\leq
e^{-cz\sqrt{N/2}}$ for some $c>0$. Finally, in order to determine whether a
vertex $w$ is $z$-exceptional, the algorithm has to explore at least one
vertex in the subtree of the vertex $w$. Hence, the running time of the
algorithm is bounded from below by the number of vertices $w$ that have to be
probed in order to find a $z$-exceptional vertex. But this quantity follows
the geometric distribution with success probability $\mathbb{P}(E_{w})\leq
e^{cz\sqrt{N/2}}$. Altogether, for any $z^{\prime}<cz/\sqrt{2}$ and for $N$
sufficiently large, this shows that the running time $\tau$ of any algorithm
solving the simpler problem is at least $e^{z^{\prime}\sqrt{N}}$ with
probability $1-\delta$. The statement readily follows.

We now make this argument formal. Recall that, by definition, an algorithm is
a stochastic process $(v(n))_{n\geq 0}$ previsible with respect to the
filtration $\tilde{\mathscr{F}}$, defined by

$\tilde{\mathscr{F}}_{k}=\sigma\left(v(1),\ldots,v(k);\,X_{v(1)},\ldots,X_{v(k)};\,U_{1},\ldots,U_{k+1}\right)$

where $(U_{k})_{k\geq 1}$ is a sequence of iid uniform random variables on
$[0,1]$, independent of the branching random walk $\mathbf{X}$. We now define
a larger filtration $\mathscr{G}$. For this, define for any
$v\in\mathbb{T}_{N}$ the following set of vertices:

$\mathcal{V}_{v}=\begin{cases}w\in\mathbb{T}_{N}:|v\wedge w|\geq\lfloor
N/2\rfloor,&\text{if $|v|\geq\lfloor N/2\rfloor$}\\\
v,&\text{otherwise}.\end{cases}$

Note that $v\in\mathcal{V}_{v}$ for every $v\in\mathbb{T}_{N}$. We then set

$\mathscr{G}_{k}=\sigma\left(v(1),\ldots,v(k);\,(X_{w})_{w\in\mathcal{V}_{v(1)}},\ldots,(X_{w})_{w\in\mathcal{V}_{v(k)}};\,U_{1},\ldots,U_{k+1}\right).$

Note that $\tilde{\mathscr{F}}_{k}\subset\mathscr{G}_{k}$ for all $k\geq 0$ —
heuristically, $\mathscr{G}_{k}$ adds to $\tilde{\mathscr{F}}_{k}$ the
information about the values in the branching random walk of all vertices
contained in $\mathcal{V}_{v(i)}$, $i=1,\ldots,k$. Note that trivially, the
stochastic process $v(n)_{n\geq 0}$ is still previsible with respect to this
larger filtration $\mathscr{G}$.

Now say that $\mathcal{V}_{v}$ is $z$-exceptional if $|v|\geq\lfloor
N/2\rfloor$ and the ancestor of $v$ at generation $\lfloor N/2\rfloor$ is
$z$-exceptional in the sense defined above — note that this definition does
not depend on the choice of $v$. Define

$\tau^{\prime}=\inf\\{k\geq 0:\mathcal{V}_{v(k)}\text{ is
$z$-exceptional}\\},$

and note that $\tau^{\prime}$ is a stopping time with respect to the
filtration $\mathscr{G}$. Now, by the equality of events

$\\{\tau^{\prime}=k\\}=\\{\text{$\mathcal{V}_{v(k)}$ is
$z$-exceptional}\\}\cap\\{\tau^{\prime}>k-1\\},$

and since $\\{\tau^{\prime}>k-1\\}\in\mathscr{G}_{k-1}$ and $v(k)$ is
$\mathscr{G}_{k-1}$-measurable, we have

$\mathbb{P}(\tau^{\prime}=k\,|\,\mathscr{G}_{k-1})=\sum_{v\in\mathbb{T}_{N}}\mathbb{P}(\text{$\mathcal{V}_{v}$
is $z$-exceptional}\,|\,\mathscr{G}_{k-1})\boldsymbol{1}_{(v(k)=v,\
\tau^{\prime}>k-1)}.$

Now, for any $v\in\mathbb{T}_{N}$, if $|v|<\lfloor N/2\rfloor$, or if
$v\in\bigcup_{i=0}^{k-1}\mathcal{V}_{v(i)}$, the above probability is zero,
because none of $\mathcal{V}_{v(i)}$, $i=0,\ldots,k-1$ are $z$-exceptional on
the event $\\{\tau^{\prime}>k-1\\}$. On the other hand, if
$v\not\in\bigcup_{i=0}^{k-1}\mathcal{V}_{v(i)}$, then, by the branching
property, the above conditional probability is equal to the unconditioned
probability that $\mathcal{V}_{v}$ is $z$-exceptional, which is bounded by
$e^{-cz\sqrt{N/2}}$ by (5.2). Hence, we get in total that

$\mathbb{P}(\tau^{\prime}=k|\,\tau^{\prime}>k-1)\leq e^{-cz\sqrt{N/2}},$

and $\tau^{\prime}$ is dominated from below by a geometric random variable
with success probability $e^{-cz\sqrt{N/2}}$. The proof now continues as
above. ∎

##  6 Proof of Lemma 1.4

We first consider the case $\beta\in[0,\beta_{c})$. Define

$D_{\beta,N}=\derivative{\beta}W_{\beta,N}=\sum_{|u|=n}(X_{u}-\varphi^{\prime}(\beta)N)e^{\beta
X_{u}-\varphi(\beta)N}.$

We express the entropy by

$\displaystyle H(\mu_{\beta,N})$
$\displaystyle=\frac{1}{W_{\beta,N}}\sum_{|u|=N}(\varphi(\beta)N-\beta
X_{u})e^{\beta X_{u}-\varphi(\beta)N}+\log W_{\beta,N}$
$\displaystyle=(\varphi(\beta)-\beta\varphi^{\prime}(\beta))N-\beta\frac{D_{\beta,N}}{W_{\beta,N}}+\log
W_{\beta,N}.$

By the assumption on $\beta$, we have
$\varphi(\beta)-\beta\varphi^{\prime}(\beta)>0$. Furthermore, $W_{\beta,N}$
converges almost surely to a positive random variable as $N\to\infty$ by Fact
1.2 and $D_{\beta,N}$ converges almost surely as well as $N\to\infty$, see
[12]. The first statement follows.

Now let $\beta>\beta_{c}$ and assume
$\beta_{c}\in\mathcal{D}(\varphi)^{\circ}$. Define

$\widetilde{W}_{\beta,N}=\sum_{|u|=N}e^{\beta(X_{u}-\varphi^{\prime}(\beta_{c})N-\frac{3}{2\beta_{c}}\log
N)}.$

We now write

$H(\mu_{\beta,N})=\frac{1}{\widetilde{W}_{\beta,N}}\sum_{|u|=N}\left(-\beta\left(X_{u}-\varphi^{\prime}(\beta_{c})N-\frac{3}{2\beta_{c}}\log
N\right)\right)e^{\beta(X_{u}-\varphi^{\prime}(\beta_{c})N-\frac{3}{2\beta_{c}}\log
N)}+\log\widetilde{W}_{\beta,N}.$

Fix $\beta^{\prime}\in(\beta_{c},\beta)$. Then there exists $C>0$, such that
$xe^{-\beta x}\leq Ce^{-\beta^{\prime}x}$ for every $x\in\mathbb{R}$. We have

$H(\mu_{\beta,N})\leq
C\frac{\widetilde{W}_{\beta^{\prime},N}}{\widetilde{W}_{\beta,N}}+\log\widetilde{W}_{\beta,N}.$

Now, $\widetilde{W}_{\beta,N}$ and $\widetilde{W}_{\beta^{\prime},N}$ converge
almost surely as $N\to\infty$ to positive random variables, see [25]. The
second statement follows.

##  7 Open questions and further directions

In this section, we state a few questions and further directions related to
the CREM and the branching random walks for future study.

  1. 1.

It was conjectured in [1] that for the CREM, there exists a threshold
$\beta_{G}\geq 0$ such that its Gibbs measure with parameter $\beta$ can be
efficiently approximated if $\beta<\beta_{G}$ and cannot if $\beta>\beta_{G}$.
A conjectured explicit expression222There is a typo in the expression of
$\beta_{G}$ in the case of the CREM in Item 1, Section 5 of [1]. The
definition of $t_{G}$ should be replaced by the following one:
$t_{G}=\sup\\{t\in[0,1]:A(s)=\hat{A}(s)\text{ for all }s\leq t\\}$. of
$\beta_{G}$ appears in Item 1, Section 5 of [1]. Our results confirm the
conjecture in the case where the CREM has correlation function $A(x)=x$, with
the notion of _approximation_ from Definition 1.5. Moreover, our results imply
that $\beta_{G}=\beta_{c}=\sqrt{2\log 2}$, the _(static) critical inverse
temperature_. One can check that $\beta_{c}$ equals the expression of
$\beta_{G}$ from [1]. Ongoing work of the authors is trying to generalize the
result to the CREM with a general correlation function.

  2. 2.

Back to the branching random walk, one might be interested in the near
critical regime to understand how the transition happens near $\beta_{c}$. To
do this, one can take a sequence $\beta(N)=\beta_{c}-N^{-\delta}$ for some
$\delta>0$. It might be interesting to study the time complexity of any
algorithm approximating the Gibbs measure $\mu_{\beta(N),N}$ in the sense of
Definition 1.5. One should expect a phase transition at $\delta=1/2$, in line
with a phase transition for the asymptotics of the partition function obtained
by Alberts and Ortgiese [4]. See also the introduction of Pain [27]. This
should be related to Pemantle’s [28] study of optimization algorithms
discussed in Section 1.2.

#### Acknowledgements.

We are grateful to an anonymous referee for several helpful suggestions
improving the presentation.

## References

  * [1] Louigi Addario-Berry and Pascal Maillard, _The algorithmic hardness threshold for continuous random energy models_ , Mathematical Statistics and Learning 2 (2020), 77–101.
  * [2] Elie Aïdékon, _Convergence in law of the minimum of a branching random walk_ , Annals of Probability 41 (2013), 1362–1426.
  * [3] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke, _Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization_ , arXiv:2203.05093 [cond-mat] (2022).
  * [4] Tom Alberts and Marcel Ortgiese, _The near-critical scaling window for directed polymers on disordered trees_ , Electronic Journal of Probability 18 (2013), 1–24.
  * [5] David Aldous, _Greedy Search on the Binary Tree with Random Edge-Weights_ , Combinatorics, Probability and Computing 1 (1992), 281–293.
  * [6] Fabrizio Antenucci, Silvio Franz, Pierfrancesco Urbani, and Lenka Zdeborová, _Glassy Nature of the Hard Phase in Inference Problems_ , Physical Review X 9 (2019), 011020.
  * [7] Gérard Ben Arous and Aukosh Jagannath, _Spectral gap estimates in mean field spin glasses_ , Communications in Mathematical Physics 361 (2018), 1–52.
  * [8] Roland Bauerschmidt and Thierry Bodineau, _Spectral gap critical exponent for Glauber dynamics of hierarchical spin models_ , Communications in Mathematical Physics 373 (2020), 1167–1206.
  * [9] Jean Bérard and Jean-Baptiste Gouéré, _Survival Probability of the Branching Random Walk Killed Below a Linear Boundary_ , Electronic Journal of Probability 16 (2011), 396–418.
  * [10] John D. Biggins, _Chernoff’s Theorem in the Branching Random Walk_ , Journal of Applied Probability 14 (1977), 630–636.
  * [11] , _Martingale Convergence in the Branching Random Walk_ , Journal of Applied Probability 14 (1977), 25–37.
  * [12] , _Uniform Convergence of Martingales in the Branching Random Walk_ , Annals of Probability 20 (1992), 137–151.
  * [13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, _Concentration Inequalities: A Nonasymptotic Theory of Independence_ , Oxford University Press, February 2013.
  * [14] Anton Bovier and Irina Kurkova, _Derrida’s Generalized Random Energy models 2: Models with continuous hierarchies_ , Annales de l’Institut Henri Poincare (B) Probability and Statistics 40 (2004), 481–495.
  * [15] Xinxin Chen, Thomas Madaule, and Bastien Mallein, _On the trajectory of an individual chosen according to supercritical Gibbs measure in the branching random walk_ , Stochastic Processes and their Applications 129 (2019), 3821–3858.
  * [16] Bernard Derrida and Herbert Spohn, _Polymers on disordered trees, spin glasses, and traveling waves_ , Journal of Statistical Physics 51 (1988), 817–840.
  * [17] Ronen Eldan, Frederic Koehler, and Ofer Zeitouni, _A Spectral Condition for Spectral Gap: Fast Mixing in High-Temperature Ising Models_ , arXiv:2007.08200 [math-ph] (2021).
  * [18] David Gamarnik and Aukosh Jagannath, _The overlap gap property and approximate message passing algorithms for $p$-spin models_, The Annals of Probability 49 (2021), 180–205.
  * [19] Nina Gantert, Yueyun Hu, and Zhan Shi, _Asymptotics for the survival probability in a killed branching random walk_ , Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 47 (2011), 111–129.
  * [20] Reza Gheissari and Aukosh Jagannath, _On the spectral gap of spherical spin glass dynamics_ , Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 55 (2019), 756–776.
  * [21] Jean-Pierre Kahane and Jacques Peyrière, _Sur certaines martingales de Benoit Mandelbrot_ , Advances in Mathematics 22 (1976), 131–145.
  * [22] Richard M. Karp and Judea Pearl, _Searching for an optimal path in a tree with random costs_ , Artificial Intelligence 21 (1983), 99–116.
  * [23] Quansheng Liu, _Asymptotic properties and absolute continuity of laws stable by random weighted mean_ , Stochastic Processes and their Applications 95 (2001), 83–107.
  * [24] Russell Lyons, _A Simple Path to Biggins’ Martingale Convergence for Branching Random Walk_ , Classical and Modern Branching Processes (Krishna B. Athreya and Peter Jagers, eds.), The IMA Volumes in Mathematics and Its Applications, Springer, New York, NY, 1997, pp. 217–221.
  * [25] Thomas Madaule, _Convergence in Law for the Branching Random Walk Seen from Its Tip_ , Journal of Theoretical Probability 30 (2017), 27–63.
  * [26] Andrea Montanari, _Optimization of the Sherrington-Kirkpatrick Hamiltonian_ , 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), November 2019, pp. 1417–1433.
  * [27] Michel Pain, _The near-critical Gibbs measure of the branching random walk_ , Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 54 (2018), 1622–1666.
  * [28] Robin Pemantle, _Search cost for a nearly optimal path in a binary tree_ , Annals of Applied Probability 19 (2009), 1273–1291.
  * [29] Haskell P. Rosenthal, _On the subspaces of $L^{p}$ ($p>2$) spanned by sequences of independent random variables_, Israel Journal of Mathematics 8 (1970), 273–303.
  * [30] Eliran Subag, _Following the Ground States of Full-RSB Spherical Spin Glasses_ , Communications on Pure and Applied Mathematics 74 (2021), 1021–1044.
  * [31] Hugo Touchette, _Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels_ , Journal of Statistical Physics 159 (2015), 987–1016.
  * [32] Ofer Zeitouni, _Branching random walks and Gaussian fields_ , Probability and statistical physics in St. Petersburg 91 (2016), 437–471.