# Cellular Segmentation and Composition in Routine Histology Images using Deep
Learning

Muhammad Dawood  Department of Computer Science
University of Warwick
Coventry, United Kingdom
<EMAIL_ADDRESS>Raja Muhammad Saad Bashir  Department of
Computer Science
University of Warwick
Coventry, United Kingdom
<EMAIL_ADDRESS>Srijay Deshpande  Department of Computer Science
University of Warwick
Coventry, United Kingdom
<EMAIL_ADDRESS>Manahil Raza  Department of Computer Science
University of Warwick
Coventry, United Kingdom
<EMAIL_ADDRESS>Adam Shephard  Department of Computer Science
University of Warwick
Coventry, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

Identification and quantification of nuclei in colorectal cancer haematoxylin
& eosin (H&E) stained histology images is crucial to prognosis and patient
management. In computational pathology these tasks are referred to as nuclear
segmentation, classification and composition and are used to extract
meaningful interpretable cytological and architectural features for downstream
analysis. The CoNIC challenge poses the task of automated nuclei segmentation,
classification and composition into six different types of nuclei from the
largest publicly known nuclei dataset - Lizard. In this regard, we have
developed pipelines for the prediction of nuclei segmentation using HoVer-Net
and ALBRT for cellular composition. On testing on the preliminary test set,
HoVer-Net achieved a PQ of 0.58, a PQ+ of 0.58 and finally a mPQ+ of 0.35. For
the prediction of cellular composition with ALBRT on the preliminary test set,
we achieved an overall $R^{2}$ score of 0.53, consisting of 0.84 for
lymphocytes, 0.70 for epithelial cells, 0.70 for plasma and .060 for
eosinophils.

###### Index Terms:

Segmentation, Pathology, Deep Learning, Cellular Composition

##  I Introduction

Colorectal cancer starts from the colon/rectum that makes up the large
intestine in the digestive system. There are many types of colorectal cancers,
with the most common being adenocarcinomas, and others such as carcinoid
tumours being more rare. TNM (Tumor, Node and Metastasis) staging is used for
the detection and diagnosis of colorectal cancer ranging from 0 (earliest
stage) to IV (latest stage) [1]. The segmentation of malignant nuclei in the
colon wall may provide important predictive features for the correct staging
of colorectal cancers. Thus, the CoNIC [5] challenge was curated. This
challenge encourages contestants to develop algorithms to perform
segmentation, classification and counting of six different nuclei types using
the largest publicly available nuclei dataset - Lizard [4]. This import
processing step may enable future researchers to improve automated cancer
staging, whilst using interpretable features. In this regard, as part of the
CoNIC Challenge, we have performed two tasks as a part of the TIA Warwick
team: 1. Nuclear segmentation and classification using HoVer-Net [6] and 2.
Prediction of cellular composition, using a modified version of ALBRT [3]. We
describe our pipeline below.

##  II Nuclear Segmentation and Classification

We utilized the HoVer-Net [6] framework to perform simultaneous segmentation
and classification of nuclear instances on the histology images from the CoNIC
dataset. The classification task characterizes the detected nuclei into one of
the following cell types: epithelial, lymphocyte, plasma, eosinophil,
neutrophil or connective tissue cells.

HoVer-Net is a deep learning framework that consists of an encoder branch, and
three decoder branches. The encoder branch is based on the pre-activated
ResNet-50 [7]. The decoder branches then perform up-sampling to achieve
segmentation and classification. There are three decoder branches: the nuclear
pixel branch, the HoVer branch and the nuclear classification branch. The
first two branches aim to detect and segment nuclei, with the HoVer branch
improving segmentation quality in the presence of overlapping/touching nuclei.
Finally, the nuclear classification branch provides a pixel-wise nuclear
classification score. Following post-processing (see [6]), the maximum
argument from the nuclear classification branch is used to obtain the class
for each nuclear instance detected by the other two branches.

The available dataset [4] was already partitioned into patches of
256$\times$256 at 20$\times$ objective power by the challenge organisers,
which we then utilised in our experiments. We further split the dataset into
training and validation sets in a stratified manner (according to the centre
from which the image was scanned at). The encoder branch of the HoVer-Net
model was pre-trained on the ImageNet weights from the pre-activated ResNet-50
[7] model. We performed optimisation on the training/validation set, using
standard augmentation techniques. The following model hyper-parameters were
found through optimisation on the training/validation set: learning rate =
0.001, number of epochs = 50 and batch size of 5. On validation, HoVer-Net
achieved a PQ of 0.48 and mPQ+ of 0.40.

Following optimisation, HoVer-Net was then tested on the unseen data provided
by the organisers. For this we achieved a PQ of 0.58, a PQ+ of 0.58 and a mPQ+
of 0.35. We also obtained component-level PQ+s of 0.38 (connective tissue),
0.38 (eosinophils), 0.05 (epithelial cells), 0.55 (lymphocytes), 0.35
(neutrophils), 0.40 (plasma). The model performed well on the lymphocytes,
plasma, connective tissue etc., but didn’t perform as well on the epithelial
cells.

##  III Prediction of Cellular Composition

Table I: The mean (standard deviation) performance of the modified ALBRT for predicting the counts of different types of cells in term of Coefficient of determination ($R^{2}$), Mean Absolute Error (MAE), and Mean Arctangent Absolute Percentage Error (MAAPE).  Component | R2 | MAE | MAAPE
---|---|---|---
Neutrophil | 0.17 | 3.16 | 0.32
Epithelial | 0.70 | 10.15 | 0.25
Lymphocyte | 0.84 | 2.70 | 0.43
Plasma | 0.70 | 2.95 | 0.51
Connective tissue | 0.16 | 6.07 | 0.65
Eosinophil | 0.59 | 0.44 | 0.14
All | 0.53 | 4.24 | 0.38

For the second task, we used ALBRT [3], a framework for cellular composition
prediction in routine histology images. The original paper takes an input
image at 40$\times$ resolution and generates sub-patch level cellular counts.
However, in this work the input images are at 20$\times$ resolution. Computing
sub-patch level cellular counts, as used by the original ALBRT paper, at this
magnification may be noisy, owing to most of the nuclei lying at the center of
the patch. Therefore, we only used the backbone Xception network [2] of ALBRT
for predicting the counts of different types of cells. This branch takes the
full patch as input, and doesn’t use sub-patches, thus eliminating this noise
issue. We additionally changed the loss function from a ranking loss to Huber
loss [8] as the method aims to directly maximise the $R^{2}$ score. We used
patch level cellular counts information of six cell types (neuotropil,
epithelial, lymphocyte, plasma, eosinophil, connective tissue) using the
ground truth instance segmentation mask. During training we shift the image
randomly by 10 pixels so that the nuclei at the border of input patch are
ignored as the ground truth cellular counts were obtained by taking a window
of 224$\times$224 from the patch center.

Since there are very few eosinophils present in the dataset, we trained two
sets of models for this work. The first set of models predicted cell counts
for all cell types, excluding eosinophils. On 5-fold cross-validation we
achieved a R2 score of 0.36 (neutrophils), 0.94 (epithelial cells), 0.94
(lymphocytes), 0.74 (plasma) and 0.85 (connective tissue). We then
additionally trained a separate modified ALBRT model for predicting eosinophil
cell counts alone. On validation this achieved a R2 score of 0.76. For the
preliminary test set, we used the first set of trained networks to predict the
cell count for all cells types, excluding eosinophils. We then averaged their
prediction to generate final cell counts for these cell types. The same
process was used for the models trained to predict eosinophil counts alone. We
achieved an overall $R^{2}$ of 0.53. For all cell types, other than
neutrophils the model has shown good performance on the preliminary test set
as shown in Table I. This may be a result of there being very few neutrophils
present in the dataset.

##  IV Conclusion

In this challenge we have used HoVer-Net and ALBRT for the segmentation,
classification and composition of six different types of nuclei from the H&E
histology images. Both of them have shown competitive performances in the
challenge preliminary test sets by achieving position in top 10 positions. We
further plan to extend this to extensively test the performance of these
algorithms on the full test set released by the CoNIC challenge.

## References

  * [1] Colorectal cancer stages: Rectal cancer staging: Colon cancer staging.
  * [2] François Chollet.  Xception: Deep learning with depthwise separable convolutions.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1251–1258, 2017.
  * [3] Muhammad Dawood, Kim Branson, Nasir M Rajpoot, and Fayyaz Minhas.  Albrt: Cellular composition prediction in routine histology images.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 664–673, 2021.
  * [4] Simon Graham, Mostafa Jahanifar, Ayesha Azam, Mohammed Nimir, Yee-Wah Tsang, Katherine Dodd, Emily Hero, Harvir Sahota, Atisha Tank, Ksenija Benes, et al.  Lizard: A large-scale dataset for colonic nuclear instance segmentation and classification.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 684–693, 2021.
  * [5] Simon Graham, Mostafa Jahanifar, Quoc Dang Vu, Giorgos Hadjigeorghiou, Thomas Leech, David Snead, Shan E Ahmed Raza, Fayyaz Minhas, and Nasir Rajpoot.  Conic: Colon nuclei identification and counting challenge 2022.  arXiv preprint arXiv:2111.14485, 2021.
  * [6] Simon Graham, Quoc Dang Vu, Shan E Ahmed Raza, Ayesha Azam, Yee Wah Tsang, Jin Tae Kwak, and Nasir Rajpoot.  Hover-net: Simultaneous segmentation and classification of nuclei in multi-tissue histology images.  Medical Image Analysis, 58:101563, 2019.
  * [7] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In European conference on computer vision, pages 630–645. Springer, 2016.
  * [8] Peter J Huber.  Robust estimation of a location parameter.  In Breakthroughs in statistics, pages 492–518. Springer, 1992.


# Typicality and entropy of processes on infinite trees

Ágnes Backhausz1,2 1 ELTE Eötvös Loránd University, Budapest, Hungary, Faculty
of Science and Alfréd Rényi Institute of Mathematics  2 Alfréd Rényi Institute
of Mathematics  ,  Charles Bordenave3 3Institut de Mathématiques de Marseille
and  Balázs Szegedy2

###### Abstract.

Consider a uniformly sampled random $d$-regular graph on $n$ vertices. If $d$
is fixed and $n$ goes to $\infty$ then we can relate typical (large
probability) properties of such random graph to a family of invariant random
processes (called "typical" processes) on the infinite $d$-regular tree
$T_{d}$. This correspondence between ergodic theory on $T_{d}$ and random
regular graphs is already proven to be fruitful in both directions. This paper
continues the investigation of typical processes with a special emphasis on
entropy. We study a natural notion of micro-state entropy for invariant
processes on $T_{d}$. It serves as a quantitative refinement of the notion of
typicality and is tightly connected to the asymptotic free energy in
statistical physics. Using entropy inequalities, we provide new sufficient
conditions for typicality for edge Markov processes. We also extend these
notions and results to processes on unimodular Galton-Watson random trees.

###### Abstract.

[Fr] On considère un graphe $d$-régulier aléatoire avec $n$ sommets
uniformément distribué. Si $d$ est fixé et $n$ diverge, nous pouvous alors
relié les propriétés typiques (de grande probabilité) d’un tel graphe
aléatoire avec une famille de processus aléatoires invariants (dénommés
processus "typiques") sur l’arbre $d$-régulier infini $T_{d}$. Cette
correspondance entre théorie ergodique sur $T_{d}$ et graphes réguliers
aléatoires s’est déjà révélée fructueuse dans les deux directions. Ce papier
poursuit l’investigation des processus typiques avec un accent mis sur
l’entropie. Nous y étudions une notion naturelle d’entropie micro-état pour
les processus invariant sur $T_{d}$. Elle sert de rafinement quantitatif à la
notion de typicalité et elle est intimement reliée à l’energie libre
asymptotique en physique statistique. Au moyen d’inégalités entropiques, nous
démontrons des nouvelles conditions suffisantes de typicalité pour des
processus markovien sur les arêtes de l’arbre. Nous étendons aussi ces notions
et résultats à des processus sur des arbres de Galton-Watson unimodulaires.

##  1\. Introduction

###  1.1. Typical processes and sofic entropy

Random $d$-regular graphs have been extensively studied over the past 50 years
[10, 21, 28, 32]. Sophisticated methods from probability theory, combinatorics
and statistical physics have been successfully used to uncover many of their
properties such as independence ratio, the density of a maximal cut or its
spectral gap [18, 31, 21]. The recently emerging theory of graph limits [8,
24, 22, 26] gives a new, limiting point of views on the subject. It turns out
that many of the crucial properties of random $d$-regular graphs for $d$ fixed
and $n$ going to infinity can also be studied in the framework of ergodic
theory on the infinite $d$-regular tree $T_{d}$ [2]. An illustration of the
power of this method is the proof of the Gaussianity of the almost
eigenvectors of random $d$-regular graphs [3, 11]. The proof is a combination
of ergodic theory on $T_{d}$ with information theoretic methods.

In this paper we are interested in a question which is also related to the
limit of random regular graphs, namely, to the family of typical processes on
$T_{d}$ introduced in [2]. These objects arise as the local limits of vertex-
colored random $d$-regular graphs (see formal definition below). These typical
processes contain useful information on the structure of $d$-regular graphs.
For example, the classical fact from [9] that the independence ratio is
separated from $1/2$ is equivalent to the fact that the alternating coloring
of the infinite $d$-regular tree is not typical. Several necessary conditions
have been formulated for typical processes in the last years. Some of them are
about the covariance structure, others are entropy inequalities [4, 5, 15].
However, general sufficient conditions for a process to be typical are less
common.

In this paper we obtain sufficient conditions for the typicality of processes
on $T_{d}$, by studying a new micro-state entropy. This entropy measures in
some sense the number of finite approximations of a process on a random
instance of a large $d$-regular graph. This entropy is tightly connected to
Bowen’s sofic entropy in measured group theory, see [13].

Our approach has another connection to the convergence of random graphs. While
graph limit theory shows great promise in a variety of questions related to
random $d$-regular graphs, it also revealed an intriguing open problem. It is
believed that for fix $d$ and $n\to\infty$ we have that a random $d$-regular
graph on $n$ vertices is convergent (in probability) in the local-global sense
of [24] and also right-convergent in the sense of [22], this last notion of
convergence relies on a deep statistical physics theory, see the monograph
[27]. These general conjectures are a common strengthening of a large variety
of conjectures many of which are already proven. For example the convergence
of the independence ratio is proven in [6, 17] and the convergence of
asymptotic free energies of a large class of statistical physics models on
random $d$-regular graphs in [29, 14]. In this paper, we introduce an upper
and a lower version of the micro-state entropies. Equality of these entropies
imply the convergence of random regular graphs. For a family of processes we
can establish this equality. This will lead to the sufficient conditions
mentioned above, and this shows that our results might lead to a deep
understanding of the structure of random regular graphs.

###  1.2. Definitions.

We now formalize the main definitions. Let $d\geq 3$ be an integer and $T_{d}$
the infinite $d$-regular tree (all vertices have $d$ neighbors). Let $M$ be a
finite set. A process $X$ on $T_{d}$ is a random variable on $M^{T_{d}}$. This
process (or its law) is invariant if the law of $X$ is invariant by all
automorphisms of the tree $T_{d}$. We denote by $\mathcal{I}_{d}(M)$ the set
of invariant probability measures on $M^{T_{d}}$.

We now define the Benjamini-Schramm topology. A pair $(G,f)$ formed by a graph
$G=(V,E)$ and a map $f:V\to M$ will be called a colored graph with color set
$M$. A rooted colored graph is a triple $(G,f,o)$ formed by a connected
colored graph $(G,f)$ and a distinguished vertex $o$ of $G$, called the root.
Two rooted colored graphs $(G,f,o)$ and $(G^{\prime},f^{\prime},o^{\prime})$
are isomorphic if there is an isomorphism of $G$ and $G^{\prime}$ which
preserves the colors and the roots. An equivalence class of rooted colored
graphs is called an unlabeled rooted colored graph in combinatorics.

Unlabeled rooted graphs give the proper setup for defining a meaningful notion
of convergence. It is however more convenient to work with rooted labeled
graphs instead of unlabeled rooted graphs. To this end, we now define a
randomized canonical graph in each equivalence class. We define the set of
finite integer sequences as

$\mathbb{N}^{f}=\cup_{k\geq 0}\mathbb{N}^{k}$ (1.1)

where $\mathbb{N}^{0}=\\{o\\}$ and $\mathbb{N}=\\{1,2,\ldots,\\}$ by
convention. The tree $T_{d}$ can be classically built on a subset of
$\mathbb{N}^{f}$ as follows. The root of the tree is $o$, its $d$-neighbors of
$o$ are $V_{1}=\\{1,\ldots,d\\}\subset\mathbb{N}$, the neighbors of $i\in
V_{1}$ are $o$ and $\\{(i,1),\ldots,(i,d-1)\\}\in\mathbb{N}^{2}$ and so on.
More generally, if $(G,o)$ is a rooted graph, the breadth-first search tree
started at the root $o$, where ties between vertices are broken uniformly at
random defines a random graph $(G^{\prime},o)$ on a subset of $\mathbb{N}^{f}$
whose law depends only the equivalence class of $(G,o)$: a vertex at distance
$k$ from the root receives a label in $\mathbb{N}^{k}$, if
$(i_{1},\ldots,i_{k-1})$ is the label of its parent in the search tree, it has
the label $(i_{1},\ldots,i_{k-1},j)$ if it the $j$-th offspring of its parent
in the random ordering. We call this random rooted graph, the randomly labeled
rooted graph associated to $(G,o)$. Conversely, we will say that a random
labeled colored graph $(G,f,o)$ on a subset of $\mathbb{N}^{f}$ is randomly
labeled if its law is equal to the law of the randomly labeled rooted colored
graph associated to its unlabeled rooted colored graph. By definition if
$X\in\mathcal{I}_{d}(M)$ then $(T_{d},X,o)$ is randomly labeled.

Recall that a graph is locally finite if all its vertices have a finite number
of neighbors. We denote by $\mathcal{G}^{\bullet}$ (respectively
$\mathcal{G}^{\bullet}_{M}$) the set of locally finite graphs (respectively
locally finite colored graphs on the color set $M$) on the vertex set
$\mathbb{N}^{f}$ rooted at $o$ which are admissible in the sense that they are
realizable as a breadth-first search labeling of a locally finite graph. The
sets $\mathcal{G}^{\bullet}$ and $\mathcal{G}^{\bullet}_{M}$ are complete
separable metric spaces when equipped with the distance
${\mathrm{d}}(g,g^{\prime})=\sum_{r\geq
0}2^{-r}{\mathbf{1}}_{(g)_{r}\neq(g^{\prime})_{r}}$ where ${\mathbf{1}}$ is
the indicator function and $g_{r}$ is the restriction of $g$ to the vertices
at distance at most $r$ from the root. We denote by
$\mathcal{P}(\mathcal{G}^{\bullet}_{M})$ the set of probability measures on
$\mathcal{G}^{\bullet}_{M}$. We equip $\mathcal{P}(\mathcal{G}^{\bullet}_{M})$
with a distance, also denoted by ${\mathrm{d}}$, which generates the weak
topology on $\mathcal{P}(\mathcal{G}^{\bullet}_{M})$ (for example, the Lévy-
Prohorov distance).

If $(G,f)$ is a locally finite colored graph and $v$ is a vertex of $G$ then
we denote by ${\mathrm{distr}}_{G,v}(f)$ the law in
$\mathcal{P}(\mathcal{G}^{\bullet}_{M})$ of the randomly labeled rooted graph
$((G,f)(v),v)$ where $(G,f)(v)$ is the restriction of $(G,f)$ to the connected
component of $G$ containing $v$. The law ${\mathrm{distr}}_{G,v}$ in
$\mathcal{P}(\mathcal{G}^{\bullet})$ is defined similarly for a graph $G$ and
a vertex $v$. Finally, if $G$ is finite with vertex set $V$, we may define the
probability measures in $\mathcal{P}(\mathcal{G}^{\bullet})$ and
$\mathcal{P}(\mathcal{G}^{\bullet}_{M})$:

${\mathrm{distr}}_{G}=\frac{1}{|V|}\sum_{v\in
V}{\mathrm{distr}}_{G,v}\quad\hbox{ and
}\quad{\mathrm{distr}}_{G}(f)=\frac{1}{|V|}\sum_{v\in
V}{\mathrm{distr}}_{G,v}(f).$

For integers $n\geq d+1$ with $nd$ even, the set $\mathcal{G}_{n}(d)$ of
simple $d$-regular graphs on the vertex set $[n]=\\{1,\ldots,n\\}$ is not
empty. For each integer $n\geq d+1$ with $nd$ even, let $G_{n}$ be a uniformly
distributed random graph on $\mathcal{G}_{n}(d)$. Almost-surely, the
probability distribution ${\mathrm{distr}}_{G_{n}}$ converges as $n$ goes to
infinity to the Dirac mass at $T_{d}$ rooted at $o$ (it is a consequence of
the fact that the number of cycles of length $k$ in $G_{n}$ is $O(1)$ for any
fixed $k$, see [10]). It can further be checked that, a.s. if $\mu$ is an
accumulation point of ${\mathrm{distr}}_{G_{n}}(f_{n})$ for some sequence of
colorings $f_{n}\in M^{n}$, then $\mu\in\mathcal{I}_{d}(M)$. This motivates
the following definition introduced in [2].

######  Definition 1.1 (Typical process).

A measure $\mu\in\mathcal{I}_{d}(M)$ is _weakly typical_ if

$\lim_{\epsilon\to 0}\limsup_{n\to\infty}\mathbb{P}(\exists f\in
M^{n}:{\mathrm{d}}({\mathrm{distr}}_{G_{n}}(f),\mu)\leq\epsilon)=1.$

It is _strongly typical_ if

$\lim_{\epsilon\to 0}\lim_{n\to\infty}\mathbb{P}(\exists f\in
M^{n}:{\mathrm{d}}({\mathrm{distr}}_{G_{n}}(f),\mu)\leq\epsilon)=1.$

Note that it is apparent from the definition that being typical does not
depend on the choice of the distance ${\mathrm{d}}$ which generates the weak
topology. We note also that the definition in [2] is slightly different but it
turns out to be equivalent by using some measure concentration phenomena (see
[3, Section 5]).

We may also define a notion of micro-state entropy of
$\mu\in\mathcal{I}_{d}(M)$ as follows. For $\mu\in\mathcal{I}_{d}(M)$ and
$r\geq 0$, the probability measure $\mu_{r}$ is defined as the restriction of
$\mu$ to the vertices at distance at most $r$ from the root. Similarly, for
$f\in M^{n}$, we define ${\mathrm{distr}}_{G}(f)_{r}$ as the restriction of
the distribution ${\mathrm{distr}}_{G}(f)$ to the set of vertices at distance
at most $r$ from the root. For any $\epsilon>0$, if $G\in\mathcal{G}_{n}(d)$,
we define

$\mathcal{F}_{G}(\mu,r,\epsilon)=\\{f\in
M^{n}:{\mathrm{d}}({\mathrm{distr}}_{G}(f)_{r},\mu_{r})\leq\epsilon\\}.$ (1.2)

This is the set of coloring functions $f$ on $G$ which are $\epsilon$ close to
$\mu_{r}$ in the Benjamini-Schramm sense. Let $G_{n}$ be a uniformly
distributed random graph on $\mathcal{G}_{n}(d)$ with $n\geq d-1$ and $nd$
even. Roughly speaking the sofic entropy of $\mu$ is a limit of

$H_{G_{n}}(\mu,r,\epsilon)=\frac{1}{n}\log|\mathcal{F}_{G_{n}}(\mu,r,\epsilon)|,$
(1.3)

in $n\to\infty$ and then in $\epsilon\to 0$ and $r\to\infty$. Notice that
random regular graphs could be replaced by other locally tree-like graph
sequences, but as the expectation of $|\mathcal{F}_{G_{n}}(\mu,r,\epsilon)|$
is easier to compute in our case, we use the definition based on random
regular graphs. Since $H_{G_{n}}(\mu,r,\epsilon)$ is a random variable in
$\\{-\infty\\}\cup[0,\infty)$ some care is needed. More formally, we fix
$0<\alpha<1$ and consider the following median value of
$H_{G_{n}}(\mu,r,\epsilon)$,

$h_{n}(\mu,r,\epsilon,\alpha)=\sup\left\\{h\in\\{-\infty\\}\cup[0,\infty):\mathbb{P}\left(H_{G_{n}}(\mu,r,\epsilon)\geq
h\right)\geq\alpha\right\\}.$

Since $h_{n}$ is non-decreasing in $\epsilon$, we may define the upper and
lower entropies of $\mu$ as

$\bar{h}(\mu,r,\alpha)=\lim_{\epsilon\to
0}\limsup_{n\to\infty}h_{n}(\mu,r,\epsilon,\alpha)\quad\hbox{ and
}\quad\underline{h}(\mu,r,\alpha)=\lim_{\epsilon\to
0}\liminf_{n\to\infty}h_{n}(\mu,r,\epsilon,\alpha).$

These entropies are extended real numbers in $\\{-\infty\\}\cup[0,\infty)$.
This entropy can be interpreted as a version of Bowen’s sofic entropy, see the
survey [13].

The sofic entropies $\bar{h}(\mu,r,\alpha)$ and $\underline{h}(\mu,r,\alpha)$
do not depend on $\alpha\in(0,1)$. Note that they do not depend neither on the
choice of the distance ${\mathrm{d}}$ (in the sense that if two distances are
topologically equivalent, the corresponding quantities $\bar{h}(\mu,r,\alpha)$
and $\underline{h}(\mu,r,\alpha)$ are equal). We shall prove the following.

######  Lemma 1.2.

Let $\mu\in\mathcal{I}_{d}(M)$ and $r\geq 0$. The function
$\alpha\mapsto(\bar{h}(\mu,r,\alpha),\underline{h}(\mu,r,\alpha))$ is constant
on $(0,1)$.

By Lemma 1.2, we may consider the common value of the entropies: for all
$\alpha\in(0,1)$,

$\bar{h}(\mu,r)=\bar{h}(\mu,r,\alpha)\quad\hbox{ and
}\quad\underline{h}(\mu,r)=\underline{h}(\mu,r,\alpha).$

By construction, $\bar{h}(\mu,r)$ and $\underline{h}(\mu,r)$ are the growth
rates of the number of coloring of a random $d$-regular graph whose
$r$-neighborhood is close to $\mu_{r}$. Finally, since $\bar{h}(\mu,r)$ and
$\underline{h}(\mu,r)$ are non-increasing in $r$, we may define the upper and
lower sofic entropies as

$\bar{h}(\mu)=\lim_{r\to\infty}\bar{h}(\mu,r)\quad\hbox{ and
}\quad\underline{h}(\mu)=\lim_{r\to\infty}\underline{h}(\mu,r).$

Taking the limit as $\alpha\to 1$, for $h\geq 0$, the inequality
$\bar{h}(\mu)\geq h$ is equivalent to the existence of a vanishing sequence
$(\epsilon_{n})$ and such that

$\limsup_{n\to\infty}\mathbb{P}(H_{G_{n}}(\mu,1/\epsilon_{n},\epsilon_{n})\geq(h-\epsilon_{n})_{+})=1,$

where $(x)_{+}=x\vee 0$, and similarly for $\underline{h}(\mu)$. Since for
$\nu,\mu\in\mathcal{P}(\mathcal{G}^{\bullet}_{M})$,
${\mathrm{d}}(\nu_{r},\mu_{r})$ converges to ${\mathrm{d}}(\nu,\mu)$ as
$r\to\infty$, the sofic entropy is thus closely related to the typicality:

######  Lemma 1.3.

Let $\mu\in\mathcal{I}_{d}(M)$. We have $\bar{h}(\mu)\geq 0$ (resp.
$\underline{h}(\mu)\geq 0$) if and only if $\mu$ is weakly (resp. strongly)
typical.

This work is notably motivated the following conjecture which is connected to
the notion of right convergence, see [22] and Subsection 1.6 below.

######  Conjecture 1.4.

For all $\mu\in\mathcal{I}_{d}(M)$, we have $\underline{h}(\mu)=\bar{h}(\mu)$.
In particular, $\mu$ is weakly typical if and only if it is strongly typical.

In this work, we will compute the entropy $\underline{h}(\mu)=\bar{h}(\mu)$
for a large class of invariant measures $\mu\in\mathcal{I}_{d}(M)$. This class
is a class of processes where a second moment method can be applied. In a
subsequent work, we will use more advanced statistical physics methods to
refine our criterion. This conjecture might also be related to the Guerra’s
interpolation method [23] developed in the context of random graphs notably in
[20, 6, 22, 29, 14, 25].

###  1.3. Annealed entropy

If $r\geq 0$ is an integer and $S$ is a subset of $T_{d}$, we define
$B_{r}(S)$ the subset of vertices of $T_{d}$ at distance at most $r$ from a
vertex in $S$. For ease of notation, for $r\geq 1$, we define $S_{r}=B_{r}(o)$
as the ball of radius $r$ around the root of $T_{d}$ and
$E_{r}=B_{r-1}(\\{o,1\\})$ is the set of vertices at distance $r-1$ from the
edge $\\{o,1\\}$ of $T_{d}$.

If $X$ is an invariant process with law $\mu\in\mathcal{I}_{d}(M)$ and $r\geq
1$ integer, we set

$\Sigma_{r}(X)=\Sigma_{r}(\mu)=H(X_{S_{r}})-\frac{d}{2}H(X_{E_{r}}),$ (1.4)

where $X_{S}$ is the restriction of $X$ to the subset $S\subset T_{d}$ and $H$
is the usual Shannon entropy: if $Y$ is a random variable taking value a
finite set $F$, then

$H(Y)=-\sum_{x\in F}\mathbb{P}(Y=x)\ln\mathbb{P}(Y=x).$

By abusing notation, we denote entropy in the same way for both random
variables and their distributions. It follows from [3, 12] (see Subsection 2.2
below for details) that $\Sigma_{r}(\mu)$ is non-increasing in $r$. We may
thus define

$\Sigma(\mu)=\lim_{r\to\infty}\Sigma_{r}(\mu).$

Note that the law of $X_{S_{r}}$ is $\mu_{r}$ and that the law of $X_{E_{r}}$
is a marginal of $\mu_{r}$. The quantities $\Sigma_{r}(\mu)$ and $\Sigma(\mu)$
will be called the annealed entropy of $\mu_{r}$ and $\mu$, the reason will be
clear in the forthcoming Subsection 2.3. The following first moment bound is
essentially contained in [2, 12].

######  Theorem 1.5.

For any $\mu\in\mathcal{I}_{d}(M)$ and integer $r\geq 1$, we have

$\bar{h}(\mu,r)\leq\Sigma_{r}(\mu)\quad\hbox{ and
}\quad\bar{h}(\mu)\leq\Sigma(\mu).$

As a corollary, we recover the "star-edge inequality" of [2, 3] which is a
necessary condition of typicality: if $\mu$ is weakly typical then by Lemma
1.3, $\bar{h}(\mu)\geq 0$ and thus, by Theorem 1.5, $\Sigma(\mu)\geq 0$.

######  Corollary 1.6 ([2, 3]).

If $\mu\in\mathcal{I}_{d}(M)$ is a weakly typical process then
$\Sigma(\mu)\geq 0$.

The main result of this paper is a matching lower bound for a large class of
invariant processes. To this end, we first recall the notion of coupling
restricted to our setting. Let $M_{1}$ and $M_{2}$ be two finite sets, $X_{1}$
and $X_{2}$ be two random variables on $M_{1}^{T_{d}}$ and $M_{2}^{T_{d}}$
with respective laws $\mu_{1}$ and $\mu_{2}$. A coupling of $\mu_{1}$ and
$\mu_{2}$ is a distribution $\nu$ on $(M_{1}\times M_{2})^{T_{d}}$ such that
if $Y=(Y_{1},Y_{2})$ has law $\nu$, $Y_{i}$ has law $\mu_{i}$ for $i=1,2$. If
$X_{i}$ is an invariant process for $i=1,2$, we say that $\nu$ or $Y$ is an
invariant coupling if $\nu\in\mathcal{I}_{d}(M_{1}\times M_{2})$.

######  Theorem 1.7.

Let $\mu\in\mathcal{I}_{d}(M)$. For any integer $r\geq 1$, if all invariant
couplings $\nu$ of $\mu$ and $\mu$ satisfy $\Sigma_{r}(\nu)\leq
2\Sigma_{r}(\mu)$ then $\underline{h}(\mu,r)=\bar{h}(\mu,r)=\Sigma_{r}(\mu).$
In particular, if the above condition holds for an increasing sequence of
integers $(r_{k})_{k\geq 1}$ then
$\underline{h}(\mu)=\bar{h}(\mu)=\Sigma(\mu).$

We note that the bound $\Sigma_{r}(\nu)\leq 2\Sigma_{r}(\mu)$ is attained for
the independent coupling $Y=(X_{1},X_{2})$ with $X_{i}$ independent with law
$\mu$. Note also that if $\nu$ is the trivial coupling of $\mu$ and $\mu$,
that is $Y=(X,X)$ with $X$ with law $\mu$, we find
$\Sigma_{r}(\nu)=\Sigma_{r}(\mu)$. Hence, under the condition of Theorem 1.7,
we have $\Sigma_{r}(\mu)\leq 2\Sigma_{r}(\mu)$ or equivalently
$\Sigma_{r}(\mu)\geq 0$. As a corollary, by Lemma 1.3, we thus obtain the
following sufficient condition for typicality.

######  Corollary 1.8.

Let $\mu\in\mathcal{I}_{d}(M)$ and $(r_{k})_{k\geq 1}$ an increasing sequence
of integers be such that for all invariant couplings $\nu$ of $\mu$ and $\mu$
and all $k\geq 1$ we have $\Sigma_{r_{k}}(\nu)\leq 2\Sigma_{r_{k}}(\mu)$. Then
$\mu$ is strongly typical.

###  1.4. Edge-Markov processes

There is a specific class of processes in $\mathcal{I}_{d}(M)$ for which it is
possible to improve on Theorem 1.7, the edge-Markov processes defined as
follows. As above, for integer $r\geq 0$, $B_{r}(S)$ is the $r$-neighborhood
of a subset $S$ in $T_{d}$. For $r\geq 1$, recall that $S_{r}=B_{r}(o)$ and
$E_{r}=B_{r-1}(\\{o,1\\})$.

######  Definition 1.9 (Edge-Markov process).

A probability measure in $M^{T_{d}}$ is edge-Markov if conditioned on the
value at an edge, the processes on the left and right subtrees of that edge
are independent.

More generally, for integer $r\geq 1$, a probability measure on $M^{T_{d}}$ is
$r$-Markov if conditioned on the value at $B_{r-1}(e)$, the
$(r-1)$-neighborhood of an edge $e$, the processes on the left and right
subtrees of $e$ are independent (for $r=1$ we recover the edge-Markov
process).

Let $\mathcal{I}_{d,r}(M)$ denote the set of probability measures on
$M^{S_{r}}$ that are invariant by automorphisms of $S_{r}$ and whose
restriction to $E_{r}$ is invariant by switching the two sides of the edge
$\\{o,1\\}$. If $\mu\in\mathcal{I}_{d}(M)$, then, $\mu_{r}$, its restriction
to $S_{r}$, is in $\mathcal{I}_{d,r}(M)$. Conversely, the following lemma is
easy to see.

######  Lemma 1.10.

Let $r\geq 1$ be an integer and $p\in\mathcal{I}_{d,r}(M)$. Then there is a
unique $r$-Markov process $\mu(p)\in\mathcal{I}_{d}(M)$ such that the marginal
of $\mu(p)$ on $S_{r}$ is equal to $p$.

If $p\in\mathcal{I}_{d,r}(M)$, we define
$\Sigma(p)=\Sigma_{r}(\mu(p))=H(X_{S_{r}})-(d/2)H(X_{E_{r}})$ as in Equation
(1.4), where $X$ has law $p$. As above, if $p_{1}$ and $p_{2}$ are probability
measures on $M_{1}^{S_{r}}$ and $M_{2}^{S_{r}}$, a coupling of $p_{1}$ and
$p_{2}$ is a probability measure on $M_{1}^{S_{r}}\times M_{2}^{S_{r}}$ whose
marginals are $p_{1}$ and $p_{2}$. The following theorem is a strengthening of
Theorem 1.7 for egde-Markov processes.

######  Theorem 1.11.

Let $r\geq 1$ be an integer and $p\in\mathcal{I}_{d,r}(M)$. If for all
couplings $q\in\mathcal{I}_{d,r}(M^{2})$ of $p$ and $p$, we have
$\Sigma(q)\leq 2\Sigma(p)$ then
$\underline{h}(\mu(p))=\bar{h}(\mu(p))=\Sigma(p)$ and $\mu(p)$ is strongly
typical.

Theorem 1.11 provides an easy to check criteria for typicality for edge Markov
processes. In the course of the proof, we will need an important maximizing
property satisfied by edge Markov processes (a closely related
characterization can be found in [12, Theorem 1.3] and [3, Lemma 10.1]).

######  Lemma 1.12.

Let $X\in\mathcal{I}_{d}(M)$ and $r\geq 1$. We have

$\Sigma_{r+1}(X)\leq\Sigma_{r}(X)$

with equality if and only if $X_{S_{r+1}}$ is a $r$-Markov process on
$S_{r+1}$.

Notice that we also get that $\Sigma(X)=\Sigma_{r}(X)$ holds for $r$-Markov
processes.

###  1.5. Vertex-Markov processes

There is a subclass of edge-Markov processes for which the annealed entropy
takes a particularly simple form.

######  Definition 1.13 (Vertex-Markov process).

Let $T$ be a tree, a probability measure in $M^{T}$ is vertex-Markov if
conditioned on the value at a vertex, the processes on the pending subtrees of
that vertex are independent.

Let $\mathcal{I}_{e}(M)$ denote the set of probability measures on $M^{E_{1}}$
that are invariant by switching the two sides of the edge $\\{o,1\\}$. If
$\mu\in\mathcal{I}_{d}(\mu)$ then its restriction to $E_{1}$ is in
$\mathcal{I}_{e}(M)$. Conversely, if $p\in\mathcal{I}_{e}(M)$, there exists a
unique vertex-Markov process whose restriction to $E_{1}$ is $p$. We denote
the law of this process by $\mu(p)$. If $X\in\mathcal{I}_{d}(M)$, we define

$\Sigma_{e}(X)=\frac{d}{2}H(X_{E_{1}})-(d-1)H(X_{o}).$

If $p\in\mathcal{I}_{e}(M)$, we set $\Sigma(p)=\Sigma_{e}(\mu(p))$. Vertex-
Markov processes satisfy the following extremal property.

######  Lemma 1.14.

If $X\in\mathcal{I}_{d}(M)$ then

$\Sigma_{1}(X)\leq\Sigma_{e}(X),$

with equality if and only if $X_{S_{1}}$ is a vertex-Markov process on
$S_{1}$.

Combined with Theorem 1.11, the above lemma implies the following corollary.

######  Theorem 1.15.

Let $p\in\mathcal{I}_{e}(M)$. If for all couplings
$q\in\mathcal{I}_{e}(M^{2})$ of $p$ and $p$ we have $\Sigma(q)\leq
2\Sigma(p)$, then $\underline{h}(\mu(p))=\bar{h}(\mu(p))=\Sigma(p)$ and
$\mu(p)$ is strongly typical.

###### Proof.

Let $p^{\prime}=\mu(p)_{1}\in\mathcal{I}_{d,1}(M)$ be the law of $\mu(p)$
restricted to $S_{1}$. Let $q^{\prime}$ be an invariant coupling of
$p^{\prime}$ and $p^{\prime}$ and let $q$ be its restriction to $E_{1}$. By
construction $q\in\mathcal{I}_{e}(M^{2})$. Moreover, by Lemma 1.14,
$\Sigma(q^{\prime})\leq\Sigma_{1}(\mu(q^{\prime}))=\Sigma_{e}(\mu(q))=\Sigma(q)$.
It follows that Theorem 1.15 is a consequence of Theorem 1.11 applied to $r=1$
and $p^{\prime}=\mu(p)_{1}$. ∎

###  1.6. Application to factor graphs and combinatorial optimization

In this paragraph, we discuss a basic connection between asymptotic free
energy of factor graphs and sofic entropy. This may serve an extra motivation
for studying the sofic entropy.

Let $M$ be a finite set, $r\geq 1$ be an integer and let $\varphi$ be a
function on the set of rooted unlabeled $M$-colored graphs of radius $r$
taking value in $(0,\infty)$. If $G\in\mathcal{G}_{n}(d)$,

$Z_{G}=\sum_{f\in M^{n}}\prod_{v=1}^{n}\varphi((G,f,v)_{r}),$

where $(G,f,v)_{r}$ is the rooted colored graph associated to the ball of
radius $r$ around $v$ in $G$. We set

$\psi=\ln\varphi.$

The asymptotic free energy is defined as the limit of $(1/n)\ln Z_{G_{n}}$
where $G_{n}$ is a uniformly sampled graph in $\mathcal{G}_{n}(d)$ (provided
that the limit exists). By standard concentration inequality (see argument in
Theorem 2.1), it is easy to check that if $G_{n}$ is uniformly sampled in
$\mathcal{G}_{n}(d)$, then, in probability, as $n$ goes to infinity,

$\frac{1}{n}\ln Z_{G_{n}}-{\mathbb{E}}\frac{1}{n}\ln Z_{G_{n}}\to 0.$ (1.5)

It is straightforward to express the limits of the expected free energy in
terms of the entropy. If $p\in\mathcal{I}_{d,r}(M)$, we set for ease of
notation $\underline{h}(p)=\underline{h}(\mu(p),r)$ and similarly for
$\bar{h}(p)$ (there are the upper and lower growth rates of the number of
colorings of $G_{n}$ whose $r$-neighborhood is close to $p$). In the statement
below, we use the notation $\langle p,\psi\rangle={\mathbb{E}}\psi(X)$ where
$X$ has law $p$.

######  Lemma 1.16.

For integer $r\geq 1$ and $\psi$ as above, if $G_{n}$ is uniformly distributed
on $\mathcal{G}_{n}(d)$ (with $nd$ even and $n\geq d+1$), we have

$\sup_{p\in\mathcal{I}_{d,r}(M)}{{\left(\underline{h}(p)+\langle
p,\psi\rangle\right)}}\leq\liminf_{n\to\infty}{\mathbb{E}}\frac{1}{n}\ln
Z_{G_{n}}\leq\limsup_{n\to\infty}{\mathbb{E}}\frac{1}{n}\ln
Z_{G_{n}}\leq\sup_{p\in\mathcal{I}_{d,r}(M)}{{\left(\bar{h}(p)+\langle
p,\psi\rangle\right)}}.$

In particular, if Conjecture 1.4 holds true, then it would automatically imply
the convergence of the expected free energy for all functions $\psi$. Note
also that Theorem 1.7 can be used to obtain a lower bound expected free energy
while Theorem 1.5 can be used to get an upper bound. With proper technical
conditions, it is possible to extend Lemma 1.16 to some hard-constrained
models, that is to some functions $\varphi=e^{\psi}$ which take value in
$[0,\infty)$. For simplicity, we will however not discuss in details this
possibility here.

In the same vein, in combinatorial optimization problems, we are often
interested in the computation of a graph functional of the form:

$L_{G}=\max_{f\in M^{n}}\sum_{v=1}^{n}\psi((G,f,v)_{r}),$

with $r\geq 1$ and $\psi$ as above. Again, it is easy to check that if $G_{n}$
is uniformly sampled in $\mathcal{G}_{n}(d)$, we have, in probability,

$\frac{L_{G_{n}}}{n}-\frac{{\mathbb{E}}L_{G_{n}}}{n}\to 0.$

The following statement is a corollary of Lemma 1.16. It shows that typical
processes are intimately connected to the computation of limits of
${\mathbb{E}}L_{G_{n}}/n$.

######  Lemma 1.17.

For integer $r\geq 1$ and $\psi$ as above, if $G_{n}$ is uniformly distributed
on $\mathcal{G}_{n}(d)$ (with $nd$ even and $n\geq d+1$), we have

$\sup_{p\in\mathcal{I}_{d,r}(M):\underline{h}(p)\geq 0}\langle
p,\psi\rangle\leq\liminf_{n\to\infty}\frac{{\mathbb{E}}L_{G_{n}}}{n}\leq\limsup_{n\to\infty}\frac{{\mathbb{E}}L_{G_{n}}}{n}\leq\sup_{p\in\mathcal{I}_{d,r}(M):\bar{h}(p)\geq
0}\langle p,\psi\rangle.$

Again, we observe that Theorem 1.7 can be used to obtain a lower bound on
${\mathbb{E}}L_{G_{n}}/n$ and Theorem 1.5 an upper bound.

######  Remark 1.18.

We conclude this paragraph by mentioning that, for $r=1$, there is a
simplification of Lemma 1.16 and Lemma 1.17 for functions $\psi$ of the form

$\psi((G,f,v)_{1})=\psi_{0}(f(v))+\sum_{u:u\sim v}\psi_{1}(f(v),f(u))$

where the supremum in Lemma 1.16 and Lemma 1.17 is taken over
$p\in\mathcal{I}_{e}(M)$ instead of $p\in\mathcal{I}_{d,1}(M)$ and the
entropic term is given by $\underline{h}(p)=\sup\underline{h}(q)$ where the
supremum is over all $q\in\mathcal{I}_{d,1}(M)$ whose restriction to $E_{1}$
is $p$, and similarly for $\bar{h}(p)$. This can be useful because it reduces
the dimension of the underlying optimization problem. In that case, Theorem
1.15 can be used to give lower bounds.

### Organization of the paper

The remainder of this text is organized as follows. In Section 2, we will
establish the key properties of sofic and annealed entropies. In Section 3, we
will prove the main results of this paper. In the final Section 4, we will
extend our framework and main results to invariant processes on unimodular
Galton-Watson trees.

##  2\. Properties of sofic and annealed entropies

###  2.1. Concentration of entropy: proof of Lemma 1.2

Let $G_{n}$ be a uniformly distributed random graph on $\mathcal{G}_{n}(d)$
with $n\geq d-1$ and $nd$ even. Recall the definition of
$H_{G_{n}}(\mu,r,\epsilon)$ in (1.3). The aim of this subsection is to
establish the following concentration result.

######  Theorem 2.1.

Let $r\geq 0$, $\mu\in\mathcal{I}_{d}(M)$, $h\in\\{-\infty\\}\cup[0,\infty)$.
For all functions $\delta:(0,\infty)\to(0,\infty]$ with $\lim_{\epsilon\to
0}\delta(\epsilon)=0$, we have the following: if for all $\epsilon>0$,

$\limsup_{n\to\infty}\frac{1}{n}\log\mathbb{P}(H_{G_{n}}(\mu,r,\epsilon)\geq
h)\geq-\delta(\epsilon),$ (2.1)

then $\overline{h}(\mu,r,\alpha)\geq h$ for all $0<\alpha<1$. Conversely, for
all functions $\delta$ as above such that $\lim_{\epsilon\to
0}\epsilon^{-2}\delta(\epsilon)=0$: if for all $\epsilon>0$,

$\limsup_{n\to\infty}\frac{1}{n}\log\mathbb{P}(H_{G_{n}}(\mu,,r,\epsilon)\leq
h)\geq-\delta(\epsilon)$ (2.2)

then $\bar{h}(\mu,r,\alpha)\leq h$ for all $0<\alpha<1$. Finally, the same
claims hold with $\liminf$ and $\underline{h}$ replacing $\limsup$ and
$\bar{h}$.

It is immediate to check that Lemma 1.2 is a corollary of Theorem 2.1. Beware
of the asymmetry between the lower and upper bound. We believe that it is a
caveat of our proof. It is ultimately due to the fact that
$H_{G_{n}}(\mu,r,\epsilon)$ can be equal to $-\infty$.

The proof of Theorem 2.1 makes a detour through a relaxation of the entropy.
Fix $\mu\in\mathcal{I}_{d}(M)$ and $r\geq 0$. If $G$ is in
$\mathcal{G}_{d}(n)$, we define for $\beta>0$,

$Z_{G}(\beta)=\sum_{f\in
M^{n}}e^{-n\beta{\mathrm{d}}({\mathrm{distr}}_{G}(f)_{r},\mu_{r})}.$

We start the proof of the proposition with a concentration inequality.

######  Lemma 2.2.

Let $G_{n}$ be uniformly distributed on $\mathcal{G}_{n}(d)$ with $dn$ even
and $n\geq d-1$. There exists a constant $C$ depending on $(d,r)$ and a
deterministic number $s_{n}(\beta)$ depending on $(n,d,r,\beta)$ such that for
any $t>0$, we have

$\mathbb{P}{{\left({{\left|\frac{1}{n}\ln
Z_{G_{n}}(\beta)-s_{n}(\beta)\right|}}\geq t\right)}}\leq
C\exp(-nt^{2}/(C\beta)^{2}).$

###### Proof.

The proof follows a standard path. By classical contiguity results, it is
enough to establish the claim for the configuration model (see Bollobás [10,
Section 2.4]). Recall that the configuration model is the graph (with possible
loops and multiple edges) obtained as follows. We attach to each vertex in
$[n]$, $d$ half-edges. We sample a matching $m$ on the set $\vec{E}$ of $nd$
half-edges uniformly at random (recall that a matching is an involution
without fixed point). Finally, we form a $d$-regular graph $G=G(m)$ by
creating an edge for each pair of matched half-edges.

Let us say that two matchings $m,m^{\prime}$ differ by a switch if there
exists $(a,b,c,d)$ in $\vec{E}$ such that $m(e)=m^{\prime}(e)$ for all
$e\in\vec{E}\backslash\\{a,b,c,d\\}$ and $m(a)=b$, $m^{\prime}(a)=c$,
$m(c)=d$, $m^{\prime}(b)=d$. If $m$ and $m^{\prime}$ differ by a switch, we
claim that for any $f\in M^{n}$,

${\mathrm{d}}({\mathrm{distr}}_{G(m)}(f)_{r},{\mathrm{distr}}_{G(m^{\prime})}(f)_{r})\leq
C_{0}\frac{4d(d-1)^{r-1}}{n}=\frac{\theta}{n},$

where $C_{0}$ is the diameter of $\mathcal{P}(\mathcal{G}^{\bullet}_{M})$ for
the distance ${\mathrm{d}}$. Indeed, we have
${\mathrm{distr}}_{G,v}(f)_{r}={\mathrm{distr}}_{G^{\prime},v^{\prime}}(f^{\prime})_{r}$
if the rooted subgraphs $(G,f,v)_{r}$ and
$(G^{\prime},f^{\prime},v^{\prime})_{r}$ are isomorphic. Notably,
${\mathrm{distr}}_{G(m),v}(f)_{r}={\mathrm{distr}}_{G(m^{\prime}),v}(f)_{r}$
unless $v$ is at distance at most $r$ from an edge in the symmetric difference
of $G(m)$ and $G(m^{\prime})$.

We deduce that

$e^{-\beta\theta}\leq\frac{Z_{G(m^{\prime})}}{Z_{G(m)}}\leq e^{\beta\theta}$

and

${{\left|\ln Z_{G(m)}-\ln Z_{G(m^{\prime})}\right|}}\leq\beta\theta.$

From [32, Theorem 2.19], if $m$ is a uniformly sampled matching on $\vec{E}$,
we get

$\mathbb{P}{{\left({{\left|\frac{1}{n}\ln Z_{G(m)}-{\mathbb{E}}\frac{1}{n}\ln
Z_{G(m)}\right|}}\geq t\right)}}\leq 2\exp(-nt^{2}/(2d\theta^{2}\beta^{2})).$

The conclusion follows with $s_{n}(\beta)={\mathbb{E}}\frac{1}{n}\ln
Z_{G(m)}(\beta)$. ∎

We are ready for the proof of Theorem 2.1.

###### Proof of Theorem 2.1.

Recall the definition of $\mathcal{F}_{G}(\mu,r,\epsilon)$ in (1.2). Since
$\mu$ and $r$ are fixed, we write simply $\mathcal{F}_{G}(\epsilon)$ and set
$F_{G}(\epsilon)=|\mathcal{F}_{G}(\epsilon)|$. For any $\epsilon>0$, we have

$\ln Z_{G}(\beta)\geq\ln F_{G}(\epsilon)-n\beta\epsilon,$ (2.3)

where we have used that
${\mathrm{d}}({\mathrm{distr}}_{G}(f)_{r},\mu_{r})\leq\epsilon$ for all
$f\in\mathcal{F}_{G}(\epsilon)$. The other way around, if
$f\notin\mathcal{F}_{G}(\epsilon)$, we have
${\mathrm{d}}({\mathrm{distr}}_{G}(f)_{r},\mu_{r})\geq\epsilon$. Hence,

$\ln
Z_{G}(\beta)\leq\ln{{\left(|M|^{n}e^{-n\beta\epsilon}+F_{G}(\epsilon)\right)}}\leq\ln
2+{{\left(\ln F_{G}(\epsilon)\right)}}\vee(n(\ln|M|-\beta\epsilon)).$ (2.4)

We may now prove the first claim of the theorem. Assume that (2.1) holds for
some $h\geq 0$ (if $h=-\infty$, there is nothing to prove). Let $h_{1}<h$ and
$\mathcal{E}=\\{H_{G_{n}}(\mu,r,\epsilon)\geq h\\}$. On the event
$\mathcal{E}$, from (2.3), we have for all $\beta>0$,

$\frac{1}{n}\ln Z_{G_{n}}(\beta)\geq h-\beta\epsilon.$

There exists $\beta_{\epsilon}$ such that, as $\epsilon\to 0$,
$\beta_{\epsilon}\epsilon\to 0$, $\beta_{\epsilon}\to\infty$ and
$\beta_{\epsilon}^{2}\delta(\epsilon)\to 0$. For this choice of $\beta$,
$(t_{\epsilon}/\beta_{\epsilon})^{2}\gg\delta(\epsilon)$ for some
$t_{\epsilon}\to 0$. It follows from Lemma 2.2 and (2.1) that for any
$h_{2},h_{3}$ such that $h_{1}<h_{2}<h_{3}<h$, $s_{n}(\beta_{\epsilon})\geq
h_{3}$ for all $n$ large enough (depending on $\epsilon$), because the event
$\mathcal{E}$ overlaps with the event from Lemma 2.2 when $\beta_{\epsilon}$
satisfies this condition. Let $0<\alpha<1$. Applying again Lemma 2.2, we
deduce that the event $\mathcal{E}_{2}=\\{\frac{1}{n}\ln
Z_{G_{n}}(\beta_{\epsilon})\geq h_{2}\\}$ has probability greater than
$\alpha$ for all $n$ large enough.

Now, there exists $\eta_{\epsilon}$ such that, as $\epsilon\to 0$,
$\eta_{\epsilon}\to 0$ and $\beta_{\epsilon}\eta_{\epsilon}\to\infty$ (for
example $\eta_{\epsilon}=1/\sqrt{\beta}_{\epsilon}$). We apply (2.4) with
$\epsilon=\eta_{\epsilon}$. We get on the event $\mathcal{E}_{2}$, if
$\epsilon$ is small enough,

$H_{G_{n}}(\mu,r,\eta_{\epsilon})\geq\frac{1}{n}\ln
Z_{G_{n}}(\beta_{\epsilon})-\frac{1}{n}\ln 2\geq h_{2}-\frac{1}{n}\ln 2.$

The right-hand side is larger than $h_{1}$ if $n$ is large enough. We deduce
that $\bar{h}(\mu,r,\alpha)\geq h_{1}$, since $h_{1}$ can be arbitrarily close
to $h$, the first claim follows.

The second claim is proven similarly. Since $H_{G_{n}}(\mu,r,\epsilon)$ takes
value in $\\{-\infty\\}\cup[0,\infty)$, we have
$H_{G_{n}}(\mu,r,\epsilon)\leq-1$ if and only if
$H_{G_{n}}(\mu,r,\epsilon)=-\infty$. We may thus prove the second claim with
$h\geq-1$. Assume that (2.2) holds for some $\delta(\epsilon)$ which will be
defined later on. We now set $\mathcal{E}=\\{H_{G_{n}}(\mu,r,\epsilon)\leq
h\\}$. On the event $\mathcal{E}$, from (2.4), we have for all $\beta>0$,

$\frac{1}{n}\ln Z_{G_{n}}(\beta)\leq\frac{1}{n}\ln
2+h\vee(\ln|M|-\beta\epsilon).$

If $\beta\geq\beta_{\epsilon}=(\ln|M|+1)/\epsilon$ then we get, for all $n$
large enough

$\frac{1}{n}\ln Z_{G_{n}}(\beta)\leq\frac{1}{n}\ln 2+h.$

For our choice of $\delta(\epsilon)$, we have
$\delta(\epsilon)\beta^{2}_{\epsilon}\to 0$ as $\epsilon\to 0$. Then, if
$h_{1}>h_{2}>h_{3}>h$ and $\epsilon$ is small enough, we deduce by Lemma 2.2
that

$s_{n}(\beta_{\epsilon})\leq h_{3}$

for all $n$ large enough. We apply again Lemma 2.2 and deduce that the event
$\mathcal{E}_{2}=\\{\frac{1}{n}\ln Z_{G_{n}}(\beta_{\epsilon})\leq h_{2}\\}$
has probability greater than $\alpha$ for all $n$ large enough. Finally, from
(2.3), we have on the event $\mathcal{E}_{2}$,

$H_{G_{n}}(\mu,r,\epsilon^{2})\leq h_{2}+\beta_{\epsilon}\epsilon^{2}$

The latter is less than $h_{1}$ for all $\epsilon$ small enough. The second
claim follows. Obviously, the same argument works with $\liminf$ and
$\underline{h}(\mu,r,\alpha)$. ∎

###  2.2. Maximizers of the annealed entropy: proofs of Lemma 1.12 and Lemma
1.14

In this subsection, we prove Lemma 1.12 and Lemma 1.14. If $X,Y$ are discrete
random variables, we recall that the relative entropy of $X$ given $Y$ is

$H(X|Y)=-\sum_{x,y}\mathbb{P}((X,Y)=(x,y))\ln\mathbb{P}(X=x|Y=y),$

where $\mathbb{P}(A|B)=\mathbb{P}(A\cap B)/\mathbb{P}(B)$ is the usual
conditional probability (if $\mathbb{P}(B)=0$, $\mathbb{P}(A|B)$ takes an
arbitrary value). In other words, $H(X|Y)$ is the average over $Y$ of the
entropy of the conditional law of $X$ given $Y$. We will repeatedly use that

$H(X,Y)=H(Y)+H(X|Y)\quad\hbox{ and }\quad H(X|(Y,Y^{\prime}))\leq H(X|Y),$
(2.5)

with equality if and only if $X$ conditioned on $Y$ is independent of
$Y^{\prime}$.

We start with the proof of Lemma 1.12.

###### Proof of Lemma 1.12.

The following fact is useful. For a given integer $r\geq 1$, we introduce the
finite set $N=M^{S_{r-1}}$ where as usual $S_{r-1}=B_{r-1}(o)$. We consider
the map $\Psi$ from $M^{T_{d}}$ to $N^{T_{d}}$ which maps $x$ to $\Psi(x)$
such that for $v\in T_{d}$, $\Psi(x)_{v}$ is the restriction of $x$ to
$S_{r-1}(v)$ (composed by a given isomorphism from $S_{r-1}(v)$ to $S_{r-1}$).
If $X$ is a process on $T_{d}$ then for all integers $t\geq 0$, we have
$\Sigma_{t+r}(X)=\Sigma_{t+1}(\Psi(X))$. Moreover, if $X$ is a $r$-Markov
process, then $\Psi(X)$ is an edge-Markov process.

As a byproduct, it is sufficient to prove Theorem 1.12 with $r=1$: we should
check that

$\Sigma_{2}(X)\leq\Sigma_{1}(X)$

with equality if and only if $X_{S_{2}}$ is an edge Markov process. Note that
the above inequality can be equivalently written as

$H(X_{S_{2}})-H(X_{S_{1}})-\frac{d}{2}H(X_{E_{2}})+\frac{d}{2}H(X_{E_{1}})\leq
0.$ (2.6)

To check that (2.6) holds, we need some extra notation. We denote by
$L=\\{2,\ldots,d\\}$ the left side of $E_{2}$ along $E_{1}=\\{o,1\\}$. We also
set $L_{i}=\\{(i,1),\ldots,(i,d-1)\\}$ with $i=1,\ldots,d$. We have
$S_{1}=L\cup E_{1}$ and thus, from (2.5)

$H(S_{1})=H(E_{1})+H(L|E_{1}),$

where for ease of notation, for sets $S,T$, we write $H(S)$ and $H(S|T)$ in
place of $H(X_{S})$ and $H(X_{S}|X_{T})$. Similarly, since $E_{2}=S_{1}\cup
L_{1}$,

$H(E_{2})=H(S_{1})+H(L_{1}|S_{1})=H(E_{1})+H(L|E_{1})+H(L_{1}|S_{1}).$

Finally, since $S_{2}$ is the disjoint union of $E_{2}$ and
$\cup_{i=2}^{d}L_{i}$, we have,

$H(S_{2})=H(E_{2})+H(\cup_{i=2}^{d}L_{i}|E_{2}).$

The last three identities imply that Equation (2.6) is equivalent to

$H(\cup_{i=2}^{d}L_{i}|E_{2})-{{\left(\frac{d}{2}-1\right)}}H(L_{1}|S_{1})-\frac{d}{2}H(L|E_{1})\leq
0.$ (2.7)

Using the invariance, we deduce from (2.5) that

$H(\cup_{i=2}^{d}L_{i}|E_{2})\leq(d-1)H(L_{2}|E_{2})$

with equality if and only if there is conditional independence of the
$X_{L_{i}}$’s given $X_{E_{2}}$. Now, since $E_{2}$ contains $S_{1}$, we get

$H(L_{2}|E_{2})\leq H(L_{2}|S_{1})=H(L_{1}|S_{1}),$

with equality in case of conditional independence of $X_{L_{2}}$ and
$X_{E_{2}\backslash S_{1}}$ given $X_{S_{1}}$. It follows that the left-hand
side of (2.7) is upper bounded by

$\frac{d}{2}H(L_{1}|S_{1})-\frac{d}{2}H(L|E_{1}).$ (2.8)

From the invariance of $X$ by switching the two sides of $e$, we get
$H(L|E_{1})=H(L_{1}|E_{1})$ and thus (2.8) is equal to

$\frac{d}{2}{{\left(H(L_{1}|S_{1})-H(L_{1}|E_{1})\right)}}.$

Using again (2.5), since $E_{1}\subset S_{1}$, this last expression is always
non-positive with equality if and only if $X_{L_{1}}$ is conditionally
independent of $X_{S_{1}}$ given $X_{e}$. This proves that (2.6) holds. By
considering the case of equality, it is then easy to check that it implies
that $X_{S_{2}}$ is an edge Markov process. It concludes the proof of Lemma
1.12.∎

We now prove Lemma 1.14.

###### Proof of Lemma 1.14.

Let $X\in\mathcal{I}_{d}(M)$. From (2.5), with the notation used in the proof
of Lemma 1.12, we have

$H(S_{1})=H(o)+H(S_{1}|o)\leq H(o)+dH(E_{1}|o),$

with equality if the variables $(X_{o},X_{i})_{1\leq i\leq d}$ conditioned on
$X_{o}$ are independent. Using (2.5) again, we get

$H(S_{1})\leq dH(E_{1})-(d-1)H(o).$

So finally,
$\Sigma_{1}(X)=H(S_{1})-\frac{d}{2}H(E_{1})\leq\frac{d}{2}H(E_{1})-(d-1)H(o)=\Sigma_{e}(X)$
as requested. ∎

###  2.3. Combinatorial characterization of the annealed entropy

In this subsection, we give a combinatorial interpretation of the annealed
entropy $\Sigma_{r}(\mu)$. Recall that $\mathcal{G}_{n}(d)$ is the set of
simple $d$-regular graphs on the vertex set $[n]$. For
$\mu\in\mathcal{I}_{d}(M)$, $r\geq 0$ integer and $\epsilon>0$, we define the
set of colored graphs whose $r$-neighborhood is close to $\mu_{r}$ as

$\displaystyle\mathcal{G}_{n}(\mu,r,\epsilon)$ $\displaystyle=$
$\displaystyle\\{(G,f):G\in\mathcal{G}_{n}(d),f\in
M^{n},{\mathrm{d}}({\mathrm{distr}}_{G}(f)_{r},\mu_{r})\leq\epsilon\\}$
$\displaystyle=$
$\displaystyle\bigsqcup_{G\in\mathcal{G}_{n}(d)}\mathcal{F}_{G}(\mu,r,\epsilon),$

where $\sqcup$ is the disjoint union and $\mathcal{F}_{G}(\mu,r,\epsilon)$ was
defined in (1.2). We then set

$\Sigma_{n}(\mu,r,\epsilon)=\frac{1}{n}{{\left(\log|\mathcal{G}_{n}(\mu,r,\epsilon)|-\log|\mathcal{G}_{n}(d)|\right)}}=\frac{1}{n}\log{\mathbb{E}}|\mathcal{F}_{G_{n}}(\mu,r,\epsilon)|,$
(2.9)

where the expectation is with respect to the random graph $G_{n}$ uniformly
distributed on $\mathcal{G}_{n}(d)$. In comparison with the definition of
$H_{G_{n}}(\mu,r,\epsilon)$ in (1.3), $\Sigma_{n}(\mu,r,\epsilon)$ appears as
an annealed quantity in the sense that there is an average over the randomness
of $G_{n}$ inside the logarithm. The following theorem asserts that
$\Sigma_{n}(\mu,r,\epsilon)$ is close to $\Sigma_{r}(\mu)$ as $n$ goes to
infinity and $\epsilon$ goes to $0$.

######  Theorem 2.3.

Let $\mu\in\mathcal{I}_{d}(M)$ and $r\geq 1$ integer. We have

$\lim_{\epsilon\to
0}\liminf_{n\to\infty}\Sigma_{n}(\mu,r,\epsilon)=\lim_{\epsilon\to
0}\limsup_{n\to\infty}\Sigma_{n}(\mu,r,\epsilon)=\Sigma_{r}(\mu).$

###### Proof.

One side of this identity can be found in [3, Lemma 6.2]. We will however give
a proof which relies on [16] which is a generalization of [12] to colored
graphs. This is interesting because it connects [12, 16] to the entropic
inequalities found in [2, 3]. First, a classical result of Bender and Canfield
[7] implies that

$\frac{1}{n}\log|\mathcal{G}_{n}(d)|=\frac{d}{2}\log n-s(d)-\log(d!)+o(1),$
(2.10)

where $s(d)=d/2-(d/2)\log d$. On the other hand, Proposition 5 and Proposition
6 in Delgosha and Anantharam [16] imply that

$\lim_{\epsilon\to
0}\liminf_{n\to\infty}{{\left(\frac{1}{n}\log|\mathcal{G}_{n}(\mu,r,\epsilon)|-\frac{d}{2}\log
n\right)}}=\lim_{\epsilon\to
0}\limsup_{n\to\infty}{{\left(\frac{1}{n}\log|\mathcal{G}_{n}(\mu,r,\epsilon)|-\frac{d}{2}\log
n\right)}}=J_{r}(\mu),$

where $J_{r}(\mu)$ has an explicit formula that we now describe (the same
formula appears in [12]).

We define $\widetilde{\mathcal{T}}^{\bullet}_{r-1}$ as the set of unlabeled
colored rooted $(d-1)$-ary trees of depth $r-1$. An element
$g=(t,t^{\prime})\in\widetilde{\mathcal{E}}_{r}=\widetilde{\mathcal{T}}^{\bullet}_{r-1}\times\widetilde{\mathcal{T}}^{\bullet}_{r-1}$
can be seen as an unlabeled coloring of $E_{r}$ rooted on the oriented edge
$(o,1)$. For $g=(t,t^{\prime})$ in $\widetilde{\mathcal{E}}_{r}$ and $X$ a
coloring of $T_{d}$, we then define $N_{X}(g)$ as the number of neighbors $v$
of the root such that $X$ restricted to $E_{r}(o,v)=B_{r-1}(\\{o,v\\})$ is
isomorphic to $g$: more precisely such that the restriction of $X$ to
$(d-1)$-ary tree rooted at $o$ (respectively $v$) in
$E_{r}(o,v)\backslash\\{o,v\\}$ is isomorphic to $t$ (respectively
$t^{\prime}$). By construction

$\sum_{g\in\widetilde{\mathcal{E}}_{r}}N_{X}(g)=\deg(o)=d.$ (2.11)

If $X$ is a random coloring of $T_{d}$ with $\mu$, we then define a
probability measure on $\widetilde{\mathcal{E}}_{r}$ by, for all
$g\in\widetilde{\mathcal{E}}_{r}$:

$\pi_{\mu}(g)=\frac{{\mathbb{E}}[N_{X}(g)]}{d},$

where the expectation is with respect to the randomness of $X$. We have

$J_{r}(\mu)=-s(d)+H(\widetilde{X}_{S_{r}})-\frac{d}{2}H(\pi_{\mu})-\sum_{g\in\widetilde{\mathcal{E}}_{r}}{\mathbb{E}}[\log(N_{X}(g)!)],$

where $\widetilde{X}_{S_{r}}$ is the rooted unlabeled coloring associated to
$X_{S_{r}}$. As a sanity check, if $M$ is a singleton, then
$J_{r}(\mu)=-s(d)-\log(d!)$ and we retrieve Equation (2.10). Moreover, in view
of Equation (2.10), the theorem follows from the claim

$J_{r}(\mu)=-s(d)-\log(d!)+H(X_{S_{r}})-\frac{d}{2}H(X_{E_{r}}).$ (2.12)

The expression (2.12) is obtained by putting random labeling on an unlabeled
rooted coloring and following the effect on the Shannon entropy. We first
observe that, since $X$ is invariant, for any
$g\in\widetilde{\mathcal{E}}_{r}$, we have

$\mathbb{P}(X_{E_{r}}\simeq
g)=\frac{1}{d}\sum_{v=1}^{d}\mathbb{P}(X_{E_{r}(o,v)}\simeq g)=\pi_{\mu}(g).$

It follows that $\pi_{\mu}$ is the law of $\widetilde{X}_{E_{r}}$ defined as
the unlabeled coloring associated to $X_{E_{r}}$ rooted at the oriented edge
$(o,1)$. Besides, since $X$ is invariant, $X_{E_{r}}$ is in one-to-one
correspondence with the triple
$(\widetilde{X}_{E_{r}},\sigma,\sigma^{\prime})$ where, given
$\widetilde{X}_{E_{r}}$, $\sigma$ and $\sigma^{\prime}$ are independent and
$\sigma$ is a uniform random labeling of $\widetilde{X}_{E_{r}}$ restricted to
$E_{r}^{o}$, the $(d-1)$-ary tree rooted at $o$ in $E_{r}\backslash\\{o,1\\}$,
and similarly for $\sigma^{\prime}$. From the relative entropy identity (2.5),
we find that

$H(X_{E_{r}})=H(\pi_{\mu})+2K,$

where $K$ is the relative entropy of $\sigma$ given
$\widetilde{X}_{E_{r}^{o}}$.

Secondly, we observe that $X_{S_{r}}$ is in one-to-one correspondence with the
vector $Y=(X_{E^{1}_{r}},\ldots,X_{E^{d}_{r}})$ where $E^{k}_{r}$ is the
$(d-1)$-ary tree rooted at $k$ in $E_{r}\backslash\\{o,k\\}$. It follows that
$H(Y)=H(X_{S_{r}})$. Also, if
$\widetilde{Y}=(\widetilde{X}_{E^{1}_{r}},\ldots,\widetilde{X}_{E^{d}_{r}})$,
we find from what precedes and the invariance of $X$ that

$H(X_{S_{r}})=H(Y)=H(\widetilde{Y})+dK.$

Finally, the difference between $\widetilde{Y}$ and $\widetilde{X}_{S_{r}}$ is
that the neighbors of $o$ are ordered (or labeled) in $\widetilde{Y}$. We
deduce from Lemma 2.4 below that

$H(\widetilde{Y})=H(\widetilde{X}_{S_{r}})-\sum_{g\in\widetilde{\mathcal{E}}_{r}}{\mathbb{E}}[\log(N_{X}(g)!)]+\log(d!).$

This concludes the proof of (2.12). ∎

In the proof of Theorem 2.3, we have used the following elementary lemma.
Recall that a vector is exchangeable if its law is invariant by any
permutation of its coordinates.

######  Lemma 2.4.

Let $F$ be a finite set and $Z=(Z_{1},\ldots,Z_{n})$ a random exchangeable
vector in $F^{n}$. The counting measure $N_{Z}=\sum_{i=1}^{n}\delta_{Z_{i}}$
associated to $Z$ satisfies

$H(Z)=H(N_{Z})-\sum_{x\in F}{\mathbb{E}}[\log N_{Z}(x)!]+\log n!.$

###### Proof.

We consider the equivalence class on $F^{n}$, $z\sim z^{\prime}$ if $z$ and
$z^{\prime}$ are equal up to a permutation of the coordinates of $z$. We have
$z\sim z^{\prime}$ if and only if $N_{z}=N_{z^{\prime}}$. Moreover, the number
of vectors in the equivalence class of $z$ is given by the multinomial
formula:

$\frac{n!}{\prod_{x\in F}N_{z}(x)!}.$

Using the exchangeability of $Z$, we deduce that

$\mathbb{P}(Z=z)=\frac{\prod_{x\in F}N_{z}(x)!}{n!}\sum_{z^{\prime}\sim
z}\mathbb{P}(Z=z^{\prime})=\frac{\prod_{x\in
F}N_{z}(x)!}{n!}\mathbb{P}(N_{Z}=N_{z}).$

It then remains to use the relative entropy formula (2.5). ∎

##  3\. Proofs of main results

###  3.1. First moment method: proof of Theorem 1.5

Let $r\geq 1$, $\epsilon>0$ and $G_{n}$ be uniformly sampled on
$\mathcal{G}_{n}(d)$. From Markov inequality, for any real $h$,

$\mathbb{P}(H_{G_{n}}(\mu,r,\epsilon)\geq
h)=\mathbb{P}(|\mathcal{F}_{G_{n}}(\mu,r,\epsilon)|\geq e^{nh})\leq
e^{-nh}{\mathbb{E}}|\mathcal{F}_{G_{n}}(\mu,r,\epsilon)|.$

In particular, we find

$\frac{1}{n}\log\mathbb{P}(H_{G_{n}}(\mu,r,\epsilon)\geq
h)\leq\Sigma_{n}(\mu,r,\epsilon)-h.$

From Theorem 2.3, we deduce the large deviations bound

$\limsup_{n\to\infty}\frac{1}{n}\log\mathbb{P}(H_{G_{n}}(\mu,r,\epsilon)\geq
h)\leq\Sigma_{r}(\mu)-h+\delta(\epsilon),$

where $\delta(\epsilon)$ goes to $0$ as $\epsilon\to 0$. If
$h>\Sigma_{r}(\mu)$, the right-hand side of the above expression is negative
for all $\epsilon$ small enough. We deduce in particular that for all
$\epsilon$ small enough, $\mathbb{P}(H_{G_{n}}(\mu,r,\epsilon)\geq h)$
converges to $0$. By Lemma 1.2, this proves that $\overline{h}(\mu,r)<h$. It
concludes the proof of Theorem 1.5. ∎

###  3.2. Second moment method: proof of Theorem 1.7

Let $\mu\in\mathcal{I}_{d}(M)$, $r\geq 1$ and set
$p=\mu_{r}\in\mathcal{I}_{d,r}(M)$. In view of Theorem 1.5, we should prove
that

$\underline{h}(\mu,r)\geq\Sigma(p).$ (3.1)

For ease of notation, we write $\mathcal{F}_{G}(p,\epsilon)$ in place of
$\mathcal{F}_{G}(\mu,r,\epsilon)$ (since this depends of $\mu$ only through
$\mu_{r}=p$). The Paley-Zygmund inequality implies that

$\displaystyle\mathbb{P}{{\left(H_{G_{n}}(\mu,r,\epsilon)\geq\Sigma_{n}(\mu,r,\epsilon)-\frac{1}{n}\right)}}$
$\displaystyle=$
$\displaystyle\mathbb{P}{{\left(|\mathcal{F}_{G_{n}}(p,\epsilon)|\geq
e^{-1}{\mathbb{E}}|\mathcal{F}_{G_{n}}(p,\epsilon)|\right)}}$
$\displaystyle\geq$
$\displaystyle(1-e^{-1})^{2}\frac{{{\left({\mathbb{E}}|\mathcal{F}_{G_{n}}(p,\epsilon)|\right)}}^{2}}{{\mathbb{E}}|\mathcal{F}_{G_{n}}(p,\epsilon)|^{2}}$
$\displaystyle=$
$\displaystyle(1-e^{-1})^{2}\frac{\exp(2n\Sigma_{n}(\mu,r,\epsilon))}{{\mathbb{E}}|\mathcal{F}_{G_{n}}(p,\epsilon)|^{2}}.$

Since $\mu_{r}=p$, we have $\Sigma(p)=\Sigma_{r}(\mu)$ and, by Theorem 2.3,

$\liminf_{n\to\infty}\Sigma_{n}(\mu,r,\epsilon)\geq\Sigma(p)-\delta(\epsilon),$

where $\delta(\epsilon)$ goes to $0$ as $\epsilon\to 0$. We deduce that if we
manage to prove that

$\limsup_{n\to\infty}\frac{1}{n}\log{\mathbb{E}}|\mathcal{F}_{G_{n}}(p,\epsilon)|^{2}\leq
2\Sigma(p)+\delta^{\prime}(\epsilon),$ (3.2)

where $\delta^{\prime}(\epsilon)$ goes to $0$ as $\epsilon\to 0$, then we
would get that

$\liminf_{n\to\infty}\frac{1}{n}\log\mathbb{P}{{\left(H_{G_{n}}(\mu,r,\epsilon)\geq\Sigma(p)-2\delta(\epsilon)\right)}}\geq-2\delta(\epsilon)-\delta^{\prime}(\epsilon).$

From Equation (2.1) in Theorem 2.1, this would imply that
$\underline{h}(\mu,r)\geq\Sigma(p)$ as claimed in (3.1).

It thus remains to prove Equation (3.2). For concreteness, we may assume that
the chosen distance ${\mathrm{d}}$ generating the weak topology is the total
variation distance. To that end, let $\epsilon>0$ and
$\mathcal{N}_{\varepsilon}$ be an $\varepsilon$-net on the set of invariant
coupling $q\in\mathcal{I}_{d,r}(M^{2})$ of $p$ and $p$. Given a graph
$G\in\mathcal{G}_{n}(d)$, consider two colorings of $G$ with color set $M$
whose $r$-neighborhood statistics are at most at total variation distance
$\varepsilon$ from $p$. The number of such pairs is
$|\mathcal{F}_{G}(p,\varepsilon)|^{2}$. On the other hand, each pair is in
fact a coloring of $G$ on $M^{2}$. Then its $r$-neighborhood statistics is an
element $q^{\prime}\in\mathcal{I}_{d,r}(M^{2})$. Since both marginals of
$q^{\prime}$ are at most at total variation distance $\varepsilon$ from $p$,
there is a measure $q^{*}\in\mathcal{I}_{d,r}(M^{2})$ whose total variation
distance is at most $2\varepsilon$ from $q^{\prime}$ and whose both marginals
are exactly $p$ (for each marginal of $q^{\prime}$, there is an invariant
coupling of this marginal and $p$ such that the two colorings are equal with
probability $1-\epsilon$). Therefore there exists an element in the
$\varepsilon$-net, $q\in\mathcal{N}_{\epsilon}$ such that the distance of $q$
from the original pair of coloring is at most $3\varepsilon$. We conclude that

$|\mathcal{F}_{G}(p,\varepsilon)|^{2}\leq\sum_{q\in\mathcal{N}_{\varepsilon}}|\mathcal{F}_{G}(q,3\varepsilon)|.$

This implies that

$\displaystyle{\mathbb{E}}|\mathcal{F}_{G_{n}}(p,\epsilon)|^{2}$
$\displaystyle\leq\frac{1}{|\mathcal{G}_{n}(d)|}\sum_{G\in\mathcal{G}_{n}(d)}\sum_{q\in\mathcal{N}_{\varepsilon}}|\mathcal{F}_{G}(q,3\varepsilon)|=\sum_{q\in\mathcal{N}_{\varepsilon}}\exp(n\Sigma_{n}(\mu(q),r,3\epsilon)).$

It follows that,

$\frac{1}{n}\log{\mathbb{E}}|\mathcal{F}_{G_{n}}(p,\epsilon)|^{2}\leq\max_{q\in\mathcal{N}_{\epsilon}}\Sigma_{n}(\mu(q),r,3\epsilon)+\frac{1}{n}\log|\mathcal{N}_{\varepsilon}|.$

By Theorem 2.3, we deduce that, for some function $\delta^{\prime}(\epsilon)$
going to $0$ with $\epsilon\to 0$,

$\limsup_{n\to\infty}\frac{1}{n}\log{\mathbb{E}}|\mathcal{F}_{G_{n}}(p,\epsilon)|^{2}\leq\max_{q\in\mathcal{N}_{\epsilon}}\Sigma(q)+\delta^{\prime}(\epsilon).$

By assumption for any $q\in\mathcal{I}_{d,r}(M^{2})$, $\Sigma(q)\leq
2\Sigma(p)$. We thus have proved that (3.2) holds. ∎

###  3.3. Proof of Theorem 1.11

In view of Theorem 1.5 and Theorem 1.7, it remains to prove that for any
$t\geq r$,

$\underline{h}(\mu(p),t)\geq\Sigma_{r}(\mu(p))=\Sigma(p).$

Let $q\in\mathcal{I}_{d,t}(M^{2})$ be an invariant coupling of $(\mu(p))_{t}$
and $(\mu(p))_{t}$. Then $q_{r}$ is an invariant coupling of $p$ and $p$
(since $((\mu(p))_{t})_{r}=\mu(p)_{r}=p$ by construction). By Lemma 1.12, we
have

$\Sigma(q)=\Sigma(\mu(q))\leq\Sigma(\mu(\mu(q)_{r}))=\Sigma(q_{r}).$

By assumption $\Sigma(q_{r})\leq 2\Sigma(p)$. However, by Lemma 1.12, we have
$\Sigma(p)=\Sigma(\mu(p)_{t})$. It follows that

$\Sigma(q)\leq 2\Sigma(\mu(p)_{t}).$

From Equation (3.1) applied to the radius $t$, this implies that

$\underline{h}(\mu(p),t)\geq\Sigma(\mu(p)_{t}).$

By a last application of Lemma 1.12, the right-hand side of above expression
is equal to $\Sigma(p)$. This concludes the proof of Theorem 1.11. ∎

###  3.4. Application to factor graphs: proofs of Lemmas 1.16 and Lemma 1.17

We start with the proof of Lemma 1.16.

###### Proof of Lemma 1.16.

By construction, we have

$Z_{G}=\sum_{f\in M^{n}}\prod_{v=1}^{n}e^{\psi((G,f,v)_{r})}=\sum_{f\in
M^{n}}e^{n\langle{\mathrm{distr}}_{G}(f)_{r},\psi\rangle}.$

Let $\epsilon>0$ and $\mathcal{N}_{\varepsilon}$ be an $\varepsilon$-net of
$\mathcal{I}_{d,r}(M)$. The function $p\to\langle p,\psi\rangle$ being
uniformly continuous (since $M$ is finite), there exists a function
$\delta(\epsilon)\to 0$ as $\epsilon\to 0$ such that for any probability
measure, say $q$, on rooted colored graphs of radius $r$, if
${\mathrm{d}}(q,p)\leq\epsilon$ then $|\langle q,\psi\rangle-\langle
p,\psi\rangle|\leq\delta(\epsilon)$. If $N_{G}$ is the number of colorings
such that ${\mathrm{distr}}_{G}(f)$ is at distance larger than $\epsilon$ from
$\mathcal{N}_{\varepsilon}$, it follows that

$\displaystyle Z_{G}$ $\displaystyle\leq$
$\displaystyle\sum_{p\in\mathcal{N}_{\varepsilon}}|\mathcal{F}_{G}(\mu(p),r,\epsilon)|e^{n\langle
p,\psi\rangle+n\delta(\epsilon)}+N_{G}e^{n\|\psi\|_{\infty}},$
$\displaystyle\leq$
$\displaystyle|\mathcal{N}_{\epsilon}|\max_{p\in\mathcal{I}_{d,r}(M)}e^{n(H_{G}(\mu(p),r,\epsilon)+\langle
p,\psi\rangle+\delta(\epsilon))}+N_{G}e^{n\|\psi\|_{\infty}}.$

Now, if $G_{n}$ is uniformly sampled on $\mathcal{G}_{n}(d)$, then, for any
fixed $\epsilon>0$, $\mathbb{P}(N_{G_{n}}=0)$ converges to $1$ (since
${\mathrm{distr}}_{G_{n}}$ converges in probability to a Dirac mass at
$(T_{d},o)$). Using (1.5) and taking the limit in $n$, we find

$\limsup_{n\to\infty}{\mathbb{E}}\frac{1}{n}\ln
Z_{G_{n}}\leq\max_{p\in\mathcal{I}_{d,r}(M)}{{\left(\bar{h}(p)+\langle
p,\psi\rangle+\delta^{\prime}(\epsilon)\right)}}$

with $\delta^{\prime}(\epsilon)\to 0$ as $\epsilon\to 0$. This gives the upper
bound in Lemma 1.16.

For the lower bound, we write similarly,

$\displaystyle Z_{G}$ $\displaystyle\geq$
$\displaystyle\sum_{p\in\mathcal{N}_{\varepsilon}}|\mathcal{F}_{G}(\mu(p),r,\epsilon)|e^{n\langle
p,\psi\rangle-n\delta(\epsilon)},$ $\displaystyle\geq$
$\displaystyle\max_{p\in\mathcal{N}_{\varepsilon}}e^{n(H_{G}(\mu(p),r,\epsilon)+\langle
p,\psi\rangle-\delta(\epsilon))}$ $\displaystyle\geq$
$\displaystyle\max_{p\in\mathcal{I}_{d,r}(M)}e^{n(H_{G}(\mu(p),r,\epsilon)+\langle
p,\psi\rangle-2\delta(\epsilon))}.$

The conclusion follows easily. ∎

Lemma 1.17 is a corollary of Lemma 1.16.

###### Proof of Lemma 1.17.

For $\beta>0$, let $Z_{G}(\beta)$ be the factor graph model:

$Z_{G}(\beta)=\sum_{f\in M^{n}}\prod_{v=1}^{n}e^{n\beta\psi((G,f,v)_{r})}.$

By construction, we have

$|M|^{-n}Z_{G}(\beta)\leq e^{\beta L_{G}}\leq Z_{G}(\beta).$

By Lemma 1.16, we find

$\sup_{p\in\mathcal{I}_{d,r}(M)}{{\left(\frac{\underline{h}(p)}{\beta}+\langle
p,\psi\rangle-\frac{\ln|M|}{\beta}\right)}}\leq\liminf_{n}\frac{{\mathbb{E}}L_{G_{n}}}{n}\leq\limsup_{n}\frac{{\mathbb{E}}L_{G_{n}}}{n}\leq\sup_{p\in\mathcal{I}_{d,r}(M)}{{\left(\frac{\bar{h}(p)}{\beta}+\langle
p,\psi\rangle\right)}}.$

We recall that $\bar{h}(p)$ and $\underline{h}(p)$ take value in
$\\{-\infty\\}\cup[0,\ln|M|]$. We get

$\sup_{p\in\mathcal{I}_{d,r}(M):\underline{h}(p)\geq 0}{{\left(\langle
p,\psi\rangle-\frac{\ln|M|}{\beta}\right)}}\leq\liminf_{n}\frac{{\mathbb{E}}L_{G_{n}}}{n}\leq\limsup_{n}\frac{{\mathbb{E}}L_{G_{n}}}{n}\leq\sup_{p\in\mathcal{I}_{d,r}(M):\underline{h}(p)\geq
0}{{\left(\frac{\ln|M|}{\beta}+\langle p,\psi\rangle\right)}}.$

We obtain the statement of the lemma by taking the limit $\beta\to\infty$. ∎

##  4\. Extension to processes on unimodular Galton-Watson trees

###  4.1. An extended setting

We now discuss an extension to processes on random trees. We will focus our
attention on unimodular Galton-Watson trees. In this section, we fix a
probability measure $\pi$ on integers with positive and finite expectation:

$d=\sum_{k=0}^{\infty}k\pi(k)>0.$

We define $\hat{\nu}$, the size-biased version of $\nu$ as the probability
measure defined by: for all integers $k\geq 0$

$\hat{\pi}(k)=\frac{(k+1)\pi(k+1)}{d}.$

Then, the unimodular Galton-Watson tree with degree distribution $\pi$, is the
Galton-Watson tree whose vertex set is a subset of $\mathbb{N}^{f}$ defined in
(1.1) such that the root $o$ has a number of offsprings $N_{o}$ with
distribution $\pi$ indexed by $1,\ldots,N_{o}$ and all other vertices $v$ have
an independent number of offsprings $N_{v}$ with distribution $\hat{\pi}$
indexed by $(v,1),\ldots,(v,N_{v})$. We will denote by $T$ a realization of
this random tree and ${\mathrm{UGW}}(\pi)$ the law of the rooted tree $(T,o)$.
We note that $(T,o)$ is randomly labeled in the sense defined in Subsection
1.1.

For example, if $\pi$ is a Dirac mass at $d$ then $T$ is the $d$-regular tree.
If $\pi$ is a Poisson random variable with mean $d$, then $\hat{\pi}=\pi$ and
$T$ is a standard Galton-Watson tree with Poisson offspring distribution.

As its name suggests, the random rooted tree $T$ is unimodular. Recall that a
random rooted graph $(G,o)$ is unimodular if for all non-negative functions
$f$ on the set of doubly rooted graphs (a connected graph with two ordered
distinguished vertices) which are invariant by isomorphisms, we have

${\mathbb{E}}\sum_{v\in V}f(G,o,v)={\mathbb{E}}\sum_{v\in V}f(G,v,o).$ (4.1)

where $V$ is the vertex set of $G$ and the expectation is with respect to the
randomness of $(G,o)$.

If $M$ is a finite set, an invariant process $X$ on $T$ is defined as a random
colored tree $(T,X)$ such that $(T,X,o)$ is unimodular (that is, it satisfies
(4.1) with $G=(T,X)$ and $f$ defined on the set of doubly rooted colored
graphs which are invariant by isomorphisms). We denote by
$\mathcal{I}_{\pi}(M)$ the set of laws of $(T,X)$ with $X$ invariant colorings
of $T$ on the color set $M$.

Now, in order to define a relevant notion of sofic entropy, we need to choose
the ensemble of finite graphs $G_{n}$ such that ${\mathrm{distr}}_{G_{n}}$
converges to ${\mathrm{UGW}}(\pi)$. A natural choice is the family of uniform
random graphs with a given degree sequence. Let
$d_{n}=(d_{n}(1),\ldots,d_{n}(n))$ be a sequence of integers, indexed by a
subset of $\mathbb{N}$, whose sum is even and such that

${\mathrm{distr}}_{d_{n}}=\frac{1}{n}\sum_{v=1}^{n}\delta_{d_{n}(v)}$

converges weakly to $\pi$. For technical simplicity, we assume that the degree
sequence is uniformly bounded: for some real $\Delta$,

$\sup_{n}\max_{1\leq v\leq n}d_{n}(v)\leq\Delta.$ (4.2)

Note in particular that (4.2) implies that the support of $\pi$ is contained
in $\\{0,\ldots,\Delta\\}$. From Erdős-Gallai Theorem [19], for all $n$ large
enough, the set $\mathcal{G}_{n}(d_{n})$ of simple graphs with vertex set
$[n]=\\{1,\ldots,n\\}$ such that for all $v\in[n]$, $v$ has degree $d_{n}(v)$
is not empty. Under these conditions, if $G_{n}$ is uniformly distributed on
$\mathcal{G}_{n}(d_{n})$ then almost surely ${\mathrm{distr}}_{G_{n}}$
converges to ${\mathrm{UGW}}(\pi)$, see for example [30]. In the statements
below, we will not repeat the above assumptions on the sequence $(d_{n})$.

For a given probability measure $\mu\in\mathcal{I}_{\pi}(M)$ (that is, $\mu$
is the law of an invariant coloring $(T,X)$), we can now reproduce the
definition of weakly and typical processes and define the sofic entropy by
taking limits of $H_{G_{n}}(\mu,r,\epsilon)$ defined in (1.3). We do not
repeat the definitions since there are identical except that $G_{n}$ is now a
random graph uniformly distributed on $\mathcal{G}_{n}(d_{n})$. For integer
$r\geq 1$ and $0<\alpha<1$, we define the quantity $\bar{h}(\mu,r,\alpha)$ and
$\underline{h}(\mu,r,\alpha)$ exactly as done below (1.3). Lemma 1.2 continues
to holds in this more general setting.

######  Lemma 4.1.

Let $\mu\in\mathcal{I}_{\pi}(M)$ and $r\geq 0$. The function
$\alpha\mapsto(\bar{h}(\mu,r,\alpha),\underline{h}(\mu,r,\alpha))$ is constant
on $(0,1)$.

###### Proof.

The proof of Theorem 2.1 works verbatim under the assumption (4.2). ∎

We define $\bar{h}(\mu,r)$ and $\underline{h}(\mu,r)$ as the common value of
$\bar{h}(\mu,r,\alpha)$ and $\underline{h}(\mu,r,\alpha)$. The upper and lower
sofic entropies $\bar{h}(\mu)$ and $\underline{h}(\mu)$ are the limits in $r$
of $\bar{h}(\mu,r)$ and $\underline{h}(\mu,r)$. Exactly as in Lemma 1.3, as a
corollary of Lemma 4.1, we obtain the following claim.

######  Lemma 4.2.

Let $\mu\in\mathcal{I}_{\pi}(M)$. We have $\bar{h}(\mu)\geq 0$ (resp.
$\underline{h}(\mu)\geq 0$) if and only if $\mu$ is weakly (resp. strongly)
typical.

###  4.2. Annealed entropy

In this broader setting, the annealed entropy is defined as follows. Let
$(T,o)$ be a randomly labeled rooted unimodular tree and $X$ an invariant
coloring of $T$ with $(T,X)$ having law $\mu$. The degree of a vertex $v$ of
$T$ is denoted by $\deg(v)$. We assume that $d={\mathbb{E}}\deg(o)>0$. As
above, if $r\geq 0$ is an integer and $S$ is a subset of the vertices of $T$,
$B_{r}(S)$ is the subset of vertices of $T$ at distance at most $r$ from $S$.
For $r\geq 1$, we set $S_{r}=B_{r}(o)$ and, if $\deg(o)\geq 1$, we set
$E_{r}=B_{r-1}(\\{o,1\\})$ (since $T$ is randomly labeled, the neighbors of
the root are indexed by $(1,\ldots,\deg(o))$).

We denote by $X_{S_{r}}$ the colored tree $(T,X)$ restricted to $S_{r}$: by
construction, $X_{S_{r}}$ has law $\mu_{r}$. We also need to define the law of
$X$ restricted to $E_{r}$ but this requires a biasing of the tree $T$. This is
done as follows. A (directed) edge-rooted graph is defined as a pair
$(G,\rho)$ formed by a connected graph $G$ and a distinguished directed edge
$\rho=(u,v)$ (that is, $\\{u,v\\}$ is an edge of the graph). Now, we denote by
$\vec{\mu}$ the law on colored edge-rooted trees defined by:

$\vec{\mu}(\cdot)=\frac{1}{d}{\mathbb{E}}{{\left[\deg(o){\mathbf{1}}((T,X,(o,1))\in\cdot\right]}},$
(4.3)

where $(T,X)$ has law $\mu$ and $d={\mathbb{E}}\deg(o)$. Note that under the
probability measure $\vec{\mu}$, $o$ has at least degree $1$ and thus
$\\{o,1\\}$ is an edge of the tree. We denote by $(\vec{T},\vec{X},\rho)$,
with $\rho=(o,1)$ a random variable with law $\vec{\mu}$. It is easy to check
that Equation (4.1) implies that $\vec{\mu}$ is invariant by switching the two
sides of the oriented edge. Moreover, if $T$ has law ${\mathrm{UGW}}(\pi)$
then $\vec{T}$ is given by two independent Galton-Watson trees with offspring
distribution $\hat{\pi}$ whose roots are connected by the root-edge, see [1,
Example 1.1]. In particular, if $\pi$ is a Dirac mass at $d$, then
$T=\vec{T}$.

We denote by $\vec{X}_{E_{r}}$ the colored tree $(\vec{T},\vec{X})$ restricted
to $E_{r}$. The law of $\vec{X}_{E_{r}}$ is $\vec{\mu}_{r}$, the restriction
of $\vec{\mu}$ to $E_{r}$. We observe that $\vec{\mu}_{r}$ depends on $\mu$
only through its marginal $\mu_{r}$.

Now, if $X$ is an invariant coloring of $T$ with law
$\mu\in\mathcal{I}_{\pi}(M)$ and $r\geq 1$ is an integer, we set

$\Sigma_{r}(X)=\Sigma_{r}(\mu)=H(X_{S_{r}})-\frac{d}{2}H(\vec{X}_{E_{r}})-H(\pi).$
(4.4)

See Remark 4.5 for an alternative expression which is arguably more natural.
Thanks to assumption (4.2) it is immediate that the above entropies are finite
as soon as $M$ is finite. Note also that $\Sigma_{r}(\mu)$ depends on $\mu$
only through $\mu_{r}$. We will check in Lemma 4.10 below that
$\Sigma_{r}(\mu)$ is non-increasing in $r$. We may thus define

$\Sigma(\mu)=\lim_{r\to\infty}\Sigma_{r}(\mu).$

The quantities $\Sigma_{r}(\mu)$ and $\Sigma(\mu)$ are the annealed entropies
of $\mu_{r}$ and $\mu$. The following lemma generalizes Lemma 4.3.

######  Theorem 4.3.

For any $\mu\in\mathcal{I}_{\pi}(M)$ and integer $r\geq 1$, we have

$\bar{h}(\mu,r)\leq\Sigma_{r}(\mu)\quad\hbox{ and
}\quad\bar{h}(\mu)\leq\Sigma(\mu).$

There is also an analog of Theorem 1.7.

######  Theorem 4.4.

Let $\mu\in\mathcal{I}_{\pi}(M)$. For any integer $r\geq 1$, if all invariant
couplings $\nu$ of $\mu$ and $\mu$, we have $\Sigma_{r}(\nu)\leq
2\Sigma_{r}(\mu)$ then $\underline{h}(\mu,r)=\bar{h}(\mu,r)=\Sigma_{r}(\mu).$
In particular, if the above condition holds for an increasing sequence of
integers $(r_{k})_{k\geq 1}$ then
$\underline{h}(\mu)=\bar{h}(\mu)=\Sigma(\mu).$

######  Remark 4.5.

The annealed entropy is also given by the formula:

$\Sigma_{r}(X)=H(X_{S_{r}}|T_{S_{r}})-\frac{d}{2}H(\vec{X}_{E_{r}}|\vec{T}_{E_{r}}),$

where $H(X|Y)=H(X,Y)-H(Y)$ is the relative entropy. Indeed $\vec{T}$ is the
union of two independent copies of $T^{\prime}$, a Galton-Watson tree with
offspring distribution $\hat{\pi}$, while $T$ is the union of $N$ independent
copies of $T^{\prime}$ and with $N$ independent with distribution $\pi$. It
follows that, $H(\vec{T}_{E_{r}})=2H(T^{\prime}_{S_{r-1}})$ and
$H(T_{S_{r}})=H(N)+dH(T^{\prime}_{S_{r-1}})$ (from (2.5)). In particular,
$H(T_{S_{r}})-(d/2)H(\vec{T}_{E_{r}})=H(N)=H(\pi)$.

###  4.3. Markov processes

There is an extension of Theorem 1.11 and Theorem 1.15 in our extended
setting. The previous definitions of Markov processes carry over when
conditioned on the random tree. More precisely, we use the following
definitions.

######  Definition 4.6 (Markov process).

Let $(T,X)$ be a random coloring of a random tree $T$ on a finite set $M$ with
law $\mu$. For integer $r\geq 1$, $X$ or $\mu$ is $r$-Markov if conditioned on
$T$ on $B_{r-1}(e)$ and on the value at $B_{r-1}(e)$, the $(r-1)$-neighborhood
of an edge $e$, the processes on the left and right subtrees of $e$ are
independent. Similarly, $X$ or $\mu$ is vertex-Markov if conditioned on $T$
and on the value at a vertex, the processes on the pending subtrees of that
vertex are independent.

For integer $r\geq 1$, let $\mathcal{I}_{\pi,r}(M)$ denote the set of laws
$\mu$ of coloring $(T^{\prime},X^{\prime})$ on $M$ which are randomly labeled,
such that $T^{\prime}$ has law ${\mathrm{UGW}}(\pi)_{r}$ (the law of the
restriction of $T$ to $S_{r}$) and such that $\vec{\mu}$ as defined above is
invariant by switching the two sides of the oriented edge. If
$\mu\in\mathcal{I}_{\pi}(M)$ then $\mu_{r}\in\mathcal{I}_{\pi}(M)$.
Conversely, we have the following (see [12, Proposition 1.1]):

######  Lemma 4.7.

Let $r\geq 1$ integer and $p\in\mathcal{I}_{\pi,r}(M)$. Then there is a unique
$r$-Markov process $\mu(p)\in\mathcal{I}_{\pi}(M)$ such that the marginal of
$\mu(p)$ on $S_{r}$ is equal to $\mu$.

If $p\in\mathcal{I}_{\pi,r}(M)$, we define $\Sigma(p)=\Sigma_{r}(\mu(p))$ as
in Equation (4.4). The following theorem is an extension of Theorem 1.11.

######  Theorem 4.8.

Let $r\geq 1$ be an integer and $p\in\mathcal{I}_{\pi,r}(M)$. If for all
couplings $q\in\mathcal{I}_{\pi,r}(M^{2})$ of $p$ and $p$, we have
$\Sigma(q)\leq 2\Sigma(p)$ then
$\underline{h}(\mu(p))=\bar{h}(\mu(p))=\Sigma(p)$ and $\mu(p)$ is strongly
typical.

There is a version of this theorem for vertex-Markov processes. As above, let
$\mathcal{I}_{e}(M)$ denote the set of probability measures on $M^{E_{1}}$
that are invariant by switching the two sides of the edge $\\{o,1\\}$. If
$\mu\in\mathcal{I}_{\mu}(M)$ then the restriction of $\vec{\mu}$ to $E_{1}$ is
in $\mathcal{I}_{e}(M)$. Conversely, if $p\in\mathcal{I}_{e}(M)$, there exists
a unique vertex-Markov process $\mu(p)$ in $\mathcal{I}_{\pi}(M)$ such that
$\vec{\mu}$ restricted to $E_{1}$ is in $\mathcal{I}_{e}(M)$. If
$(T,X)\in\mathcal{I}_{\pi}(M)$, we define

$\Sigma_{e}(X)=\frac{d}{2}H(\vec{X}_{E_{1}})-dH(\vec{X}_{o})+H(X_{o})-H(\pi).$

If $p\in\mathcal{I}_{e}(M)$, we set $\Sigma(p)=\Sigma_{e}(\mu(p))$. The
following theorem is an extension of Theorem 1.15.

######  Theorem 4.9.

Let $p\in\mathcal{I}_{e}(M)$. If for all couplings
$q\in\mathcal{I}_{e}(M^{2})$ of $p$ and $p$, we have $\Sigma(q)\leq
2\Sigma(p)$ then $\underline{h}(\mu(p))=\bar{h}(\mu(p))=\Sigma(p)$ and
$\mu(p)$ is strongly typical.

In the remainder of the paper, we explain the proofs of Theorem 4.3, Theorem
4.4, Theorem 4.8 and Theorem 4.9. The proofs are entirely similar to the proof
of the corresponding results for invariant processes on $T_{d}$. We will only
sketch the proof and explain the differences.

###  4.4. Maximizers of the annealed entropy

The following lemma is the exact analog of Lemma 1.12 and Lemma 1.14.

######  Lemma 4.10.

Let $X\in\mathcal{I}_{\pi}(M)$ and $r\geq 1$. We have

$\Sigma_{r+1}(X)\leq\Sigma_{r}(X),$

with equality if and only if $X_{S_{r+1}}$ is a $r$-Markov process on
$S_{r+1}$. Moreover,

$\Sigma_{1}(X)\leq\Sigma_{e}(X),$

with equality if and only if $X_{S_{1}}$ is a vertex-Markov process on
$S_{1}$.

###### Proof.

We start by the first statement. Arguing as in the proof of Lemma 4.10, it is
enough to check the inequality for $r=1$. The inequality
$\Sigma_{2}(X)\leq\Sigma_{1}(X)$ is equivalent to

$H(X_{S_{2}})-H(X_{S_{1}})-\frac{d}{2}H(\vec{X}_{E_{2}})+\frac{d}{2}H(\vec{X}_{E_{1}})\leq
0.$ (4.5)

Let $\deg_{T}(o)$ and $\deg_{\vec{T}}(o)$ be the degrees of the root in $T$
and $\vec{T}$. For integer $k\geq 1$, from (4.3), we have, for any event $A$,

$\mathbb{P}((\vec{X},\vec{T})\in
A,\deg_{\vec{T}}(o)=k)=\frac{k}{d}\mathbb{P}((X,T)\in A,\deg_{T}(o)=k).$

It follows that $\mathbb{P}(\deg_{\vec{T}}(o)=k)=k\pi(k)/d$ and if $k\geq 1$
is in the support of $\pi$,

$\mathbb{P}((\vec{X},\vec{T})\in A|\deg_{\vec{T}}(o)=k)=\mathbb{P}((X,T)\in
A|\deg_{T}(o)=k).$ (4.6)

In other words, $(X,T)$ and $(\vec{X},\vec{T})$ have the same law when
conditioned on the root degree is $k\geq 1$. For a set $S$ of vertices, let us
denote by by $H_{k}(S)$ the entropy of the variable $(T,X)$ restricted to $S$
and conditioned on the event $\deg_{T}(o)=k$. Similarly, we set
$H_{k}(S|S^{\prime})=H_{k}(S,S^{\prime})-H_{k}(S^{\prime})$ is the associated
relative entropy.

From (2.5), we may write, for $t=1,2$,

$H(X_{S_{t}})=H(\deg_{T}(o))+\pi(0)H_{0}(X_{o})+\sum_{k=1}^{\infty}\pi(k)H_{k}(S_{t}).$

and

$H(\vec{X}_{E_{t}})=H(\deg_{\vec{T}}(o))+\sum_{k=1}^{\infty}\frac{k\pi(k)}{d}H_{k}(E_{t}).$

Hence, (4.5) is equivalent to the claim:

$\sum_{k=1}^{\infty}\pi(k){{\left(H_{k}(S_{2})-H_{k}(S_{1})-\frac{k}{2}H_{k}(E_{2})+\frac{k}{2}H_{k}(E_{1})\right)}}\leq
0.$ (4.7)

On the event $\deg_{T}(o)=k$, for $1\leq i\leq k$, let
$L_{i}=\\{(i,1),\ldots,(i,n_{i})\\}$ be the offspring of vertex $i$. Note that
the random variables $X_{L_{i}}$ conditioned on the event $\deg_{T}(o)=k$ are
exchangeable. Then, the computation from (2.6) to (2.8) gives

$H_{k}(S_{2})-H_{k}(S_{1})-\frac{k}{2}H_{k}(E_{2})+\frac{k}{2}H_{k}(E_{1})\leq\frac{k}{2}H_{k}(L_{1}|S_{1})-\frac{k}{2}H_{k}(L|E_{1})$

The left-hand side of (4.7) is thus upper bounded by

$\sum_{k=1}^{\infty}\frac{k}{2}\pi(k){{\left(H_{k}(L_{1}|S_{1})-H_{k}(L|e)\right)}}=\frac{d}{2}{{\left(H(\vec{X}_{L_{1}}|\vec{X}_{S_{1}})-H(\vec{X}_{L}|\vec{X}_{E_{1}})\right)}}.$

We now use the invariance of $\vec{\mu}$ by switching the two sides of the
edge $E_{1}=\\{o,1\\}$. We get
$H(\vec{X}_{L}|\vec{X}_{E_{1}})=H(\vec{X}_{L_{1}}|\vec{X}_{E_{1}})$. Finally,
since $E_{1}\subset S_{1}$, we deduce that the inequalities (4.5)-(4.7) hold.
As in the proof of Lemma 1.12, the case of equality is a directed consequence
of the case of equality in (2.5).

We now prove the second statement of Lemma 4.10,
$\Sigma_{1}(X)\leq\Sigma_{e}(X)$. It is equivalent to prove that

$H(X_{S_{1}})-\frac{d}{2}H(\vec{X}_{E_{1}})\leq\frac{d}{2}H(\vec{X}_{E_{1}})-dH(\vec{X}_{o})+H(X_{o}).$

Arguing as above, we find that this is equivalent to

$\sum_{k=1}^{\infty}\pi(k){{\left(H_{k}(S_{1})-kH_{k}(E_{1})-(k-1)H_{k}(o)\right)}}\leq
0.$

As in the proof of Lemma 1.14, it remains to use that $H_{k}(S_{1})\leq
H(o)+kH_{k}(E_{1}|o)$ and $H_{k}(E_{1}|o)=H_{k}(E_{1})-H_{k}(o)$. In the case
of equality, this implies the conditional independence of
$(X_{1},\ldots,X_{k})$ given $X_{o}$ and root degree equal to $k$. ∎

###  4.5. Combinatorial characterization of the annealed entropy

In our extended setting, the combinatorial interpretation of the annealed
entropy $\Sigma_{r}(\mu)$ explained in Subsection 2.3 continues to hold. The
definition of $\Sigma_{n}(\mu,r,\epsilon)$ in (2.9) remains unchanged. The
following theorem is an extension of Theorem 2.3.

######  Theorem 4.11.

Let $\mu\in\mathcal{I}_{\pi}(M)$ and $r\geq 1$ integer. We have

$\lim_{\epsilon\to
0}\liminf_{n\to\infty}\Sigma_{n}(\mu,r,\epsilon)=\lim_{\epsilon\to
0}\limsup_{n\to\infty}\Sigma_{n}(\mu,r,\epsilon)=\Sigma_{r}(\mu).$

###### Proof.

Let $s(d)=d/2-(d/2)\log d$. From [10, Theorem 2.16], we have

$\lim_{n\to\infty}{{\left(\frac{1}{n}\log|\mathcal{G}_{n}(d_{n})|-\frac{d}{2}\log
n\right)}}=-s(d)+H(\deg(o))-{\mathbb{E}}[\log(\deg(o)!)],$

where $\deg(o)$ has law $\pi$. Also, from [12, 16], we have

$\lim_{\epsilon\to
0}\liminf_{n\to\infty}{{\left(\frac{1}{n}\log|\mathcal{G}_{n}(\mu,r,\epsilon)|-\frac{d}{2}\log
n\right)}}=\lim_{\epsilon\to
0}\limsup_{n\to\infty}{{\left(\frac{1}{n}\log|\mathcal{G}_{n}(\mu,r,\epsilon)|-\frac{d}{2}\log
n\right)}}=J_{r}(\mu),$

where
$J_{r}(\mu)=-s(d)+H(\widetilde{X}_{S_{r}})-\frac{d}{2}H(\pi_{\mu})-\sum_{g\in\widetilde{\mathcal{E}}_{r}}{\mathbb{E}}[\log(N_{X}(g)!)]$
is defined exactly as in Theorem 2.3, the only difference being that (2.11) is
replaced by

$\sum_{g\in\widetilde{\mathcal{E}}_{r}}N_{X}(g)=\deg(o).$

Arguing as in the proof of Theorem 2.3, we have
$H(\pi_{\mu})=H(\widetilde{X}_{E_{r}})$ where $\widetilde{X}_{E_{r}}$ is the
unlabeled coloring associated to $\vec{X}_{E_{r}}$. Hence, the theorem follows
by checking that

$H(\widetilde{X}_{S_{r}})-\frac{d}{2}H(\widetilde{X}_{E_{r}})=H(X_{S_{r}})-\frac{d}{2}H(\vec{X}_{E_{r}})+\sum_{g\in\widetilde{\mathcal{E}}_{r}}{\mathbb{E}}[\log(N_{X}(g)!)]-{\mathbb{E}}[\log(\deg(o)!)].$
(4.8)

In order to prove that (4.8) holds, we decompose the left-hand side of the
possible values of the root-degree. We write

$H(\widetilde{X}_{S_{r}})=H(\pi)+H_{0}(X_{o})+\sum_{k=1}^{\infty}\pi(k)H_{k}(\widetilde{X}_{S_{r}}),$

where $H_{k}$ is the entropy conditioned on $\deg_{T}(o)=k$. Similarly,

$\frac{d}{2}H(\widetilde{X}_{E_{r}})=\frac{d}{2}H(\hat{\pi})+\sum_{k=1}^{\infty}\frac{k}{2}\pi(k)H_{k}(\widetilde{X}_{E_{r}}).$

Let ${\mathbb{E}}_{k}[\cdot]$ is the expectation conditioned on
$\deg_{T}(o)=k$. From (4.6), it follows that the identity (4.8) is equivalent
to

$\sum_{k=1}^{\infty}\pi(k){{\left(H_{k}(\widetilde{X}_{S_{r}})-\frac{k}{2}H_{k}(\widetilde{X}_{E_{r}})\right)}}=\sum_{k=1}^{\infty}\pi(k){{\left(H_{k}(X_{S_{r}})-\frac{k}{2}H_{k}(X_{E_{r}})+\sum_{g\in\widetilde{\mathcal{E}}_{r}}{\mathbb{E}}_{k}[\log(N_{X}(g)!)]-\log(k!)\right)}}.$
(4.9)

We denote by $E_{r}^{o}$, the tree rooted at $o$ in $E_{r}\backslash\\{o,1\\}$
and by $E_{r}^{1}$ the tree rooted at $1$. Arguing as in the proof of Theorem
2.3, we find

$H_{k}(X_{E_{r}})=H_{k}(\widetilde{X}_{E_{r}})+K_{k}+K^{\prime}_{k},$

where $K_{k}$ is the relative entropy of a random labeling $\sigma$ of
$\widetilde{X}_{E^{o}_{r}}$ conditioned on $\deg(o)=k$ and $K^{\prime}_{k}$ is
the relative entropy of a random labeling $\sigma^{\prime}$ of
$\widetilde{X}_{E^{1}_{r}}$ conditioned on $\deg(o)=k$. Similarly, arguing as
in the proof of Theorem 2.3, we get

$H_{k}(X_{S_{r}})=H_{k}(\widetilde{X}_{S_{r}})+kK^{\prime}_{k}-\sum_{g\in\widetilde{\mathcal{E}}_{r}}{\mathbb{E}}_{k}[\log(N_{X}(g)!)]+\log(k!).$

We deduce that the right-hand side of (4.9) is equal to

$\sum_{k=1}^{\infty}\pi(k){{\left(H_{k}(\widetilde{X}_{S_{r}})-\frac{k}{2}H_{k}(\widetilde{X}_{E_{r}})\right)}}+\sum_{k=1}^{\infty}\pi(k){{\left(\frac{k}{2}K_{k}^{\prime}-\frac{k}{2}K_{k}\right)}}.$

Finally, we observe that

$\sum_{k=1}^{\infty}\pi(k){{\left(\frac{k}{2}K_{k}^{\prime}-\frac{k}{2}K_{k}\right)}}=\frac{d}{2}{{\left(H(\sigma)-H(\sigma^{\prime})\right)}}.$

The above expression is equal to $0$ because the law $\vec{\mu}$ is invariant
by switching the two sides of the edge $\\{o,1\\}$. This concludes the proof
of Equation (4.8). ∎

######  Remark 4.12.

The proof of Theorem 4.11 gives the simplified expression
$J_{r}(\mu)=-s(d)+\Sigma_{r}(\mu)-{\mathbb{E}}[\log(\deg(o)!)]$. In
particular, the proof of Lemma 4.10 has an interesting corollary for the
maximizers of these functions $J_{r}(\mu)$. Notably, in [12, Theorem 1.3]
below (9) we may remove the assumption that $\rho_{1}$ has finite support.
Consequently, from [12, Corollary 1.4], the annealed entropy $\Sigma(\rho)$
defined in [12] for unimodular random trees with average root degree $d$ is
uniquely maximized by ${\mathrm{UGW}}(\mathrm{Poi}(d))$.

###  4.6. Proofs of Theorem 4.3, Theorem 4.4, Theorem 4.8 and Theorem 4.9

As already pointed, the conclusion of Theorem 2.1 holds in our extended
setting. We may thus repeat verbatim the proofs in Section 3 and invoke
Theorem 4.11 in place of Theorem 2.3 and Lemma 4.10 in place of Lemma 1.12. ∎

### Acknowledgement.

C.B. thanks Suman Chakraborty for his comments and for suggesting Remark 4.12.
The research was partially supported by the NKFIH "Élvonal" KKP 133921 grant
(for Á. B. and B. Sz.) and by grant ANR-16-CE40-0024 (for C.B.).

## References

  * [1] D. Aldous and R. Lyons.  Processes on unimodular random networks.  Electronic Journal of Probability, 12:1454–1508, 2007.
  * [2] A. Backhausz and B. Szegedy.  On large-girth regular graphs and random processes on trees.  Random Structures Algorithms, 53(3):389–416, 2018.
  * [3] A. Backhausz and B. Szegedy.  On the almost eigenvectors of random regular graphs.  Ann. Probab., 47(3):1677–1725, 2019.
  * [4] A. Backhausz, B. Szegedy, and B. Virág.  Ramanujan graphings and correlation decay in local algorithms.  Random Structures Algorithms, 47(3):424–435, 2015.
  * [5] A. Backhausz and B. Virág.  Spectral measures of factor of i.i.d. processes on vertex-transitive graphs.  Ann. Inst. Henri Poincaré Probab. Stat., 53(4):2260–2278, 2017\.
  * [6] M. Bayati, D. Gamarnik, and P. Tetali.  Combinatorial approach to the interpolation method and scaling limits in sparse random graphs.  Ann. Probab., 41(6):4080–4115, 2013.
  * [7] E. A. Bender and E. Canfield.  The asymptotic number of labeled graphs with given degree sequences.  Journal of Combinatorial Theory, Series A, 24(3):296 – 307, 1978\.
  * [8] I. Benjamini and O. Schramm.  Recurrence of distributional limits of finite planar graphs.  Electron. J. Probab., 6:no. 23, 13, 2001.
  * [9] B. Bollobás.  The independence ratio of regular graphs.  Proc. Amer. Math. Soc., 83(2):433–436, 1981.
  * [10] B. Bollobás.  Random graphs, volume 73 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, second edition, 2001.
  * [11] C. Bordenave.  Normalité asymptotique des vecteurs propres d’un graphe régulier aléatoire (d’après Backhausz et Szegedy).  Séminaire Bourbaki, 71e année, 2018–2019, No. 1151., 2018\.
  * [12] C. Bordenave and P. Caputo.  Large deviations of empirical neighborhood distribution in sparse random graphs.  Probab. Theory Related Fields, 163(1-2):149–222, 2015.
  * [13] L. P. Bowen.  A brief introduction of sofic entropy theory.  In Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. III. Invited lectures, pages 1847–1866. World Sci. Publ., Hackensack, NJ, 2018.
  * [14] A. Coja-Oghlan and W. Perkins.  Spin systems on Bethe lattices.  Comm. Math. Phys., 372(2):441–523, 2019.
  * [15] E. Csóka, V. Harangi, and B. Virág.  Entropy and expansion.  Ann. Inst. Henri Poincaré Probab. Stat., 56(4):2428–2444, 2020\.
  * [16] P. Delgosha and V. Anantharam.  A notion of entropy for stochastic processes on marked rooted graphs.  arXiv:1908.00964, 2019.
  * [17] J. Ding, A. Sly, and N. Sun.  Maximum independent sets on random regular graphs.  Acta Math., 217(2):263–340, 2016.
  * [18] W. Duckworth and N. C. Wormald.  On the independent domination number of random regular graphs.  Combin. Probab. Comput., 15(4):513–522, 2006.
  * [19] P. Erdős and T. Gallai.  Graphs with prescribed degrees of vertices (hungarian).  Mat. Lapok, 11:264–274, 1960.
  * [20] S. Franz and M. Leone.  Replica bounds for optimization problems and diluted spin systems.  J. Statist. Phys., 111(3-4):535–564, 2003.
  * [21] J. Friedman.  A proof of Alon’s second eigenvalue conjecture and related problems.  Mem. Amer. Math. Soc., 195(910):viii+100, 2008.
  * [22] D. Gamarnik.  Right-convergence of sparse random graphs.  Probab. Theory Related Fields, 160(1-2):253–278, 2014.
  * [23] F. Guerra.  Broken replica symmetry bounds in the mean field spin glass model.  Comm. Math. Phys., 233(1):1–12, 2003.
  * [24] H. Hatami, L. Lovász, and B. Szegedy.  Limits of locally-globally convergent graph sequences.  Geom. Funct. Anal., 24(1):269–296, 2014.
  * [25] M. Lelarge and M. Oulamara.  Replica bounds by combinatorial interpolation for diluted spin systems.  J. Stat. Phys., 173(3-4):917–940, 2018.
  * [26] L. Lovász.  Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications.  American Mathematical Society, Providence, RI, 2012.
  * [27] M. Mezard and A. Montanari.  Information, Physics, and Computation.  Oxford University Press, Inc., USA, 2009.
  * [28] D. Puder.  Expansion of random graphs: new proofs, new results.  Invent. Math., 201(3):845–908, 2015.
  * [29] J. Salez.  The interpolation method for random graphs with prescribed degrees.  Combin. Probab. Comput., 25(3):436–447, 2016.
  * [30] R. van der Hofstad.  Random Graphs and Complex Networks, Volume 2.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, to appear.
  * [31] N. C. Wormald.  Differential equations for random processes and random graphs.  Ann. Appl. Probab., 5(4):1217–1235, 1995.
  * [32] N. C. Wormald.  Models of random regular graphs.  In Surveys in combinatorics, 1999 (Canterbury), volume 267 of London Math. Soc. Lecture Note Ser., pages 239–298. Cambridge Univ. Press, Cambridge, 1999.