# Records of stationary processes and unimodular graphs

Bharath Roy Choudhury

► To cite this version:

Bharath Roy Choudhury. Records of stationary processes and unimodular graphs. Probability [math.PR]. Ecole normale supérieure PSL, 2023. English. NNT: tel-04426692

HAL Id: tel-04426692

https://inria.hal.science/tel-04426692

Submitted on 30 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
## THÈSE DE DOCTORAT
DE L'UNIVERSITÉ PSL

Préparée au Département d'Informatique de l'ENS

# Records of stationary processes and unimodular graphs

Soutenue par

**Bharath Roy Choudhury**

Le 18/09/2023

École doctorale n°386

**Mathématiques Paris Centre**

Spécialité

**Mathématiques**

### Composition du jury :

Pierre Calka
Université de Rouen Normandie
Président du jury

Charles Bordenave
Institut de Mathématiques de Marseille
Rapporteur

Hermann Thorisson
University of Iceland
Rapporteur

David Dereudre
Université de Lille
Examinateur

Sergey Foss
Heriot-Watt University
Examinateur

Eliza O'Reilly
Johns Hopkins University
Examinatrice

François Baccelli
INRIA
Directeur de thèse

Bartłomiej (Bartek) Błaszczyszyn
INRIA
Co-Directeur de thèse

<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>
# Contents

Contents 1

1 Introduction 5

2 Preliminaries 15

2.1 Canonical probability spaces for networks 15
Relative compactness and tightness 18

2.2 Dynamics on networks 19
Notations 19
Royal Line of Succession order 21

2.3 Unimodular random networks and their properties 21
Vertex-shifts on unimodular networks 23
Unimodular ordered Eternal Galton-Watson Tree 25
Unimodular Family Trees of class $\mathcal{I}/\mathcal{F}$ 27
Typical re-rooting operation 27

3 Record vertex-shift for random walk case 29

3.1 Record map 30
Properties of the record map 32
Properties of the record map on skip-free to the left random walk 34

Relation between RLS order and the order on integers 38
Relation between offspring count and increment in the record graph 39

The type function and its properties 41

3.2 Classification theorem and phase transitions 45
Instances of unimodular Family Trees 47
Distribution of the record graph in the three phases 51
3.3 Record foil structure and a measure preserving map . . . . . 68

4 Vertex-shift probabilities 71

4.1 Vertex-shift probabilities . . . . . . . . . . . . . . . . . . . . . . 72
Forward Backward Lemma . . . . . . . . . . . . . . . . . . . . . . 75

4.2 Finite orbits and relative compactness . . . . . . . . . . . . . . 76

4.3 Evaporation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

4.4 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.5 Examples and their F-probabilities . . . . . . . . . . . . . . . . 82
Canopy tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Typically rooted Galton-Watson Tree (TGWT) . . . . . . . . . . 85
Unimodular Eternal Galton-Watson Tree . . . . . . . . . . . . . 86
Unimodularised bi-variate marked Eternal Kesten Tree . . 89

5 Record vertex-shift probability for the random walk case 93

5.1 The backward map of the record vertex-shift . . . . . . . . . . 94

5.2 Bijectivity and continuity of the backward map . . . . . . . . 98

5.3 The extended backward map of record vertex-shift . . . . . . 101

5.4 Bijectivity and continuity of the extended backward map . . 103

5.5 Existence of R-probability for non-negative mean . . . . . . . 104

5.6 Construction of the R-probability for zero mean . . . . . . . . 105

5.7 Properties of the R-probability sequence for zero mean . . 111

5.8 Construction of R-probability for positive mean . . . . . . . . 112

5.9 R-foils of R-probability for zero mean . . . . . . . . . . . . . . 117

6 Vertex-shifts on processes with stationary increments 119

6.1 Record vertex-shift on processes with stationary and ergodic increments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

6.2 Record representable Eternal Family Trees . . . . . . . . . . . 125
Examples of record representable vertex-shifts . . . . . . . . . 132

Bibliography 137
Acknowledgements

I would like to express my sincere gratitude to all the people who have sup-
ported me during my PhD journey. Many thanks to the ERC (grant number
788851) for financially supporting this work. I am profoundly indebted to
my advisor, François Baccelli, for the invaluable guidance, encouragement,
and mentorship he has provided. His kindness and patience have made
this journey not only enjoyable but also rewarding. Under his tutelage,
I've learned not only about mathematics but also about life and happiness,
gaining insights that extend far beyond the academic realm.

I wholeheartedly thank my co-supervisor, Bartłomiej Błaszczyszyn. He has generously shared his insights and expertise with me and has always encouraged me to improve my work. I have greatly benefited from our fruitful discussions and his constructive feedback.

I am thankful to the reviewers of my thesis, Hermann Thorisson, and
Charles Bordenave, for their careful reading and thoughtful suggestions.
Their suggestions have helped me to improve my work. I extend my thanks
to the other jury members: Pierre Calka, David Dereudre, Sergey Foss, and
Eliza O'Reilly, for agreeing to be part of this important milestone of my
academic career and for asking stimulating questions.

I thank my colleague Ali Khezeli, who has consistently been available
to validate the technical aspects of the proofs.

My heartfelt appreciation also goes to Michel Davydov, Ke Feng, Sayeh
Khaniha, and Pierre Popineau. They not only enriched my experience dur-
ing my stay at INRIA but also made it enjoyable and memorable through
their kindness, humor, and goûter. I am thankful to my colleagues Chris-
tine Fricker, Roman Gambelin, Guodong Sun, Alessia Rigonat, and Sanket
Kalamkar for the informal discussions and encouragement.

I would like to thank Julien Guieu, Marion Cueille, Christine Tanguy
from INRIA, and Eric Sinaman from ENS for their help in the administra-
tive work.

I express my gratitude to my wife Sayanika, whose support was indis-
pensable in bringing this work to completion. Finally, many thanks to all
those individuals whom I may not have mentioned explicitly but who have
contributed to my academic journey in various ways.
# Chapter 1

## Introduction

Consider a navigation rule defined on a graph that maps every vertex of the graph to a vertex in such a way that the navigation rule commutes with every automorphism of the graph. It is to say that the navigation rule applied to the vertices remains the same after taking any automorphism of the graph. Such a navigation rule is said to have the covariance property. Such covariant navigation rule indexed by locally finite graphs and satisfying a measurability condition is called a vertex-shift. More generally, one can consider vertex-shifts on networks, graphs that have labels on edges and on vertices. A vertex-shift induces a dynamic on the space of locally finite rooted networks. We are interested in a navigation rule, called the record vertex-shift, defined on trajectories of the one dimensional discrete random walk that can jump only one step to the left. The main part of the thesis is focused on studying the record vertex-shift on random walks. A few results on record vertex-shift on processes with stationary increments are also derived. The thesis also contains results on more general vertex-shifts on unimodular networks (see Def. 6).

A random walk on $\mathbb{Z}$ is called skip-free to the left (resp. right) if its i.i.d. increments take values in $\{j \in \mathbb{Z} : j \ge -1\}$ (resp. $\{j \in \mathbb{Z} : j \le 1\}$).

Consider an i.i.d. sequence of random variables $X = (X_n)_{n \in \mathbb{Z}}$, where $X_n$ takes values in $\{j \in \mathbb{Z} : j \ge -1\}$ and with finite mean for all $n \in \mathbb{Z}$. A two-sided skip-free random walk $(S_n)_{n \in \mathbb{Z}}$ on $\mathbb{Z}$ with increment sequence $X$ is given by: $S_0 = 0$, $S_n = \sum_{k=0}^{n-1} X_k$, $\forall n \ge 0$, and $S_n = \sum_{k=n}^{-1} -X_k$, $\forall n \le -1$. Observe that $(S_n)_{n \ge 0}$ is skip-free to the left whereas $(S_{-n})_{n \ge 0}$ is skip-free to the right. Construct the record graph of $X$ on $\mathbb{Z}$ by drawing a directed edge from each integer $i$ to its record $R(i) := \min\{n > i : S_n \ge S_i\}$ if the minimum
exists, otherwise to *i* itself. The record graph is a random directed graph, with $\mathbb{Z}$ as the vertex set and where the directed edges are random. Consider the connected component of 0 in the constructed record graph and root it at 0. Denote it by $[T, 0]$. This work is motivated by the following questions:

1. What is the distribution of the random rooted graph $[T, 0]$?

2. How does the distribution of $[T, 0]$ vary with the mean of the increment $\mathbb{E}[X_0]$?

3. What is the trajectory of the random walk seen from the $n$-th record of 0 as $n \to \infty$?

4. Is there a non-trivial measure-preserving map on the trajectory of the random walk which is compatible with the record map $R$ (see the discussion below for the definition of ‘compatibility’)?

Concerning the second question, we show that the record graph exhibits a phase transition when the mean $\mathbb{E}[X_0]$ is varied between $-\infty$ and $\infty$. There are three distinct phases, and each phase has a characteristic feature in terms of the classification of unimodular directed trees. The first phase is observed in the region $(-\infty, 0)$, in which the record graph has an infinite number of connected components with the component of the origin being a finite unimodular directed tree. The second phase occurs when $\mathbb{E}[X_0] = 0$. In this phase, the record graph is a.s. connected, and it is a one-ended unimodular directed tree. The third phase, which occurs when $\mathbb{E}[X_0] \in (0, \infty)$, has the characteristic feature that the record graph is a.s. a two-ended unimodular directed tree.

A Family Tree is a rooted directed tree whose out-degree is at most 1. By neglecting the loops, which occur only if $\mathbb{E}[X_0] < 0$, we obtain that the connected component of 0 in the record graph is a random Family Tree $T$ rooted at 0. We address the first question by explicitly computing the distribution of the Family Tree $[T, 0]$ in the three regimes, namely when $\mathbb{E}[X_0] \in (-\infty, 0)$ (Theorem 48), $\mathbb{E}[X_0] = 0$ (Theorem 53), and $\mathbb{E}[X_0] \in (0, \infty)$ (Theorem 54, Theorem 55).

In [7], the authors introduced the notion of vertex-shifts on graphs. Informally, a vertex-shift is a collection of maps on graphs that are covariant and satisfy a measurability condition. Given a vertex-shift $f$, we can associate to each graph $G$ its $f$-graph $G^f$ whose vertices are the same as those
of $G$ and with directed edges given by $\{(x, f(x)) : x \in V(G), f(x) \neq x\}$. The vertex-shift $f$ defines an equivalence relation on $V(G)$ by saying that two vertices $u$ and $v$ are equivalent if there exists some positive integer $n$ such that $f^n(u) = f^n(v)$. The equivalence class of $u \in V(G)$ is called the foil of $u$ (denoted as $\text{foil}(u)$) and the collection of all foils of $V(G)$ is called the foliation of $G$. Since the connected component $G_f(u)$ of any vertex $u$ in $G^f$ is the set $\{v \in V(G) : f^n(v) = f^m(u) \text{ for some } n \ge 1, m \ge 1\}$, we have $\text{foil}(u) \subseteq V(G_f(u))$.

The authors showed in [7] that given a unimodular random rooted graph $[G, o]$, the connected component of the root in the $f$-graph $G^f$ is a unimodular Family Tree, and a.s. every component of $G^f$ belongs to one of the three classes: $\mathcal{F}/\mathcal{F}$, $\mathcal{I}/\mathcal{I}$, and $\mathcal{I}/\mathcal{F}$. The class $\mathcal{F}/\mathcal{F}$ corresponds to the component being finite and its foils being finite. Similarly, the classes $\mathcal{I}/\mathcal{I}$ and $\mathcal{I}/\mathcal{F}$ correspond to the component being infinite and all foils of the component being infinite, and the component being infinite and all foils of the component being finite, respectively. It is easy to see that the record map $R$ is a vertex-shift, which implies that the Family Tree $[T, 0]$ is unimodular, where $T$ is the connected component of 0 in the record graph. The three phases of the record graph $[T, 0]$ for $\mathbb{E}[X_0] < 0$, $\mathbb{E}[X_0] = 0$ and $\mathbb{E}[X_0] > 0$ correspond to these three classes $\mathcal{F}/\mathcal{F}$, $\mathcal{I}/\mathcal{I}$ and $\mathcal{I}/\mathcal{F}$ respectively. So, the record vertex-shift is an example for which all the three classes respectively occur depending on the mean $\mathbb{E}[X_0]$.

Using the framework of [3], we view the increments of the skip-free random walk as marks associated to the edges of $\mathbb{Z}$, seen from the root $0$. More precisely, we consider the random rooted network $[\mathbb{Z}, 0, X]$, with $X = (X_n)_{n \in \mathbb{Z}}$ being the sequence of increments and $X_n$ being the label assigned to the edge $(n, n+1)$, for all $n \in \mathbb{Z}$. It is easy to see that $[\mathbb{Z}, 0, X]$ is a unimodular network. By the local view from the $n$-th record ($n \ge 1$), we mean the distribution of $[\mathbb{Z}, R^n(0), X]$. The latter is the same as $[\mathbb{Z}, 0, R^n(0)X]$, where $R^n(0)X$ is the shifted sequence $(X_{m+R^n(0)})_{m \in \mathbb{Z}}$. Using the unimodularity of $[\mathbb{Z}, 0, X]$, we show that the local view from the $n$-th record is absolutely continuous with respect to $[\mathbb{Z}, 0, X]$ with Radon-Nikodym derivative $d_n(0)$, which is defined as the number of integers for which $0$ is the $n$-th record.

Further, in connection with the third question, we show that the local view seen from the $n$-th record as $n$ tends to $\infty$, $\lim_{n \to \infty}[\mathbb{Z}, 0, R^n(0)X]$, exists for $\mathbb{E}[X_0] < 0$, $\mathbb{E}[X_0] = 0$ and $\mathbb{E}[X_0] > 0$ respectively. Denote this limit by $[\mathbb{Z}, 0, Y]$, where $Y = (Y_n)_{n \in \mathbb{Z}}$ is the mark on the edges of $\mathbb{Z}$. We observe
that $Y$ is not an i.i.d. sequence. In particular, its negative part $(Y_n)_{n<0}$ fails to be an i.i.d. sequence. However, it has a regenerative structure when $\mathbb{E}[X_0] \ge 0$.

As for the fourth question, a map $R'$ on $\mathbb{Z}$ is said to be *foil-preserving* with $R$ if it maps every foil to itself, i.e., for every $i \in \mathbb{Z}$, $R'(i)$ belongs to the foil($i$) (the foil associated to the vertex-shift $R$ and $i$).

When $\mathbb{E}[X_0] \ge 0$, we define a random map $R_\perp$ that takes $i$ to

$$R_\perp(i) = \inf\{k > i : R^n(i) = R^n(k) \text{ for some } n \ge 1\}.$$

We show that $R_\perp$ is foil-preserving with $R$ and it preserves the distribution of $[\mathbb{Z}, 0, X]$, i.e., the distribution of $[\mathbb{Z}, R_\perp(0), X]$ is the same as that of $[\mathbb{Z}, 0, X]$.

The statistics of records of time series have found applications in finance, hydrology and physics. See for instance the references in the survey [13] for a non-exhaustive list of applications. These studies of records are focused on statistics such as the distribution of $n$-th record, the age of a record (i.e., the gap between two consecutive records), and the age of the long-lasting record ([21], [13]). When the time series under consideration is an i.i.d. sequence, it is shown in [19] that the mean of the jump between two consecutive record values conditioned on the initial record value could characterize the distribution of the i.i.d. sequence. In contrast, in the present work, the focus is on the joint local structure of the records of skip-free random walks. The structure has a natural family tree flavour with an order suggesting to term it as ‘genealogy of records’.

The relation between skip-free random walks and Galton-Watson trees was extensively discussed in, e.g., [8], [16], and [14]. In fact, the authors of [8] encode the critical Galton-Watson tree and show that the encoding gives a correspondence between records of the random walk and ancestors of the root in the Galton-Watson tree. We extend these ideas to define the backward map $\Phi_R$ that takes a record graph and maps it back to the trajectory of a random walk (see Section 5.1, Chapter 5). However, we are not restricted to finite Galton-Watson trees here. To the best of our knowledge this complete description of the record graph of skip-free random walk is new.

In Chapter 2, we give the background and the statements of the theorems that we use in this work. We introduce the canonical probability spaces in which our random objects take values and introduce the dynamics induced
by vertex-shifts. Our focus is on studying vertex-shifts on unimodular networks. We state a key theorem that we use in this regard known as Foil classification in unimodular networks Theorem. We also introduce some operations on unimodular Family Trees.

In Chapter 3, we introduce the record map with which we obtain the record vertex-shift. We study its properties on deterministic integer-valued sequences. We study the properties of the record graph associated to the sequences. Using these properties, we prove that the record graph of [Z, 0, X] exhibits phase transitions, where X is the i.i.d. sequence of increments of a skip-free to the left random walk. We also describe the distribution of component of 0 in the record graph of [Z, 0, X] in each of these phases. We define the map $R_⊥$ and prove that it preserves the measure of [Z, 0, X] when $E[X_0] = 0$.

In Chapter 4, we focus on general vertex-shifts on unimodular networks and study the existence and uniqueness of vertex-shift probabilities. We provide sufficient conditions under which a vertex-shift on a random network has a unique vertex-shift probability. We apply these results to compute the vertex-shift probability of unimodular Family Trees where the vertex-shift is given by the parent vertex-shift.

In Chapter 5, we apply the results of Chapter 4 to study the R-probability of [Z, 0, X], where R is the record vertex-shift and X is the i.i.d. sequence of increments of a ship-free to the left random walk. We also provide constructions to generate the R-probability.

In Chapter 6, we study the record graph of a stationary and ergodic sequence. We show that the component of 0 in the record graph exhibits a phase transition at 0 when the mean is varied between $-∞$ and $+∞$ (see Theorem 119). We provide a sufficient condition under which a unimodular ordered EFT can be represented as the component of 0 in the record graph of the network associated to a stationary sequence (Theorem 121).

# Introduction in French

Considérez une règle de navigation définie sur un graphe qui associe à chaque sommet du graphe un sommet de telle sorte que la règle de navigation commute avec chaque automorphisme du graphe. Cela signifie que la règle de navigation appliquée aux sommets reste la même après avoir pris n'importe quel automorphisme du graphe. Une telle règle de navigation est
4. Existe-t-il une application non triviale qui préserve la mesure sur la trajectoire de la marche aléatoire qui est compatible avec l'application record $R$ (voir la discussion ci-dessous pour la définition de ‘compatibilité’) ?

En ce qui concerne la deuxième question, nous montrons que le graphe des records présente une transition de phase lorsque la moyenne $\mathbb{E}[X_0]$ varie entre $-\infty$ et $\infty$. Il y a trois phases distinctes, et chaque phase a une caractéristique propre en termes de classification des arbres dirigés unimodulaires.

La première phase est observée dans la région $(-\infty, 0)$, dans laquelle le graphe des records a un nombre infini de composantes connexes avec la composante de l'origine étant un arbre dirigé unimodulaire fini. La deuxième phase se produit lorsque $\mathbb{E}[X_0] = 0$. Dans cette phase, le graphe des records est connexe, et c'est un arbre dirigé unimodulaire à une extrémité. La troisième phase, qui se produit lorsque $\mathbb{E}[X_0] \in (0, \infty)$, a la caractéristique que le graphe des records est un arbre dirigé unimodulaire à deux extrémités.

Un arbre généalogique est un arbre dirigé enraciné dont le degré sørtant est au plus 1. En négligeant les boucles, qui ne se produisent que si $\mathbb{E}[X_0] < 0$, nous obtenons que la composante connexe de 0 dans le graphe des records est un arbre généalogique aléatoire $T$ enraciné en 0. Nous abordons la première question en calculant explicitement la distribution de l'arbre généalogique $[T, 0]$ dans les trois régimes, à savoir lorsque $\mathbb{E}[X_0] \in (-\infty, 0)$ (Théorème 48), $\mathbb{E}[X_0] = 0$ (Théorème 53), et $\mathbb{E}[X_0] \in (0, \infty)$ (Théorème 54, Théorème 55).

Dans [7], les auteurs ont introduit la notion de décalages de sommets sur les graphes. Informellement, un décalage de sommet est une collection de fonctions sur les graphes qui sont covariantes et satisfont une condition de mesurabilité. Étant donné un décalage de sommet $f$, nous pouvons associer à chaque graphe $G$ son $f$-graphe $G^f$ dont les sommets sont les mêmes que ceux de $G$ et avec des arêtes dirigées données par $\{(x, f(x)) : x \in V(G)\}$. Le décalage de sommet $f$ définit une relation d'équivalence sur $V(G)$ en disant que deux sommets $u$ et $v$ sont équivalents s'il existe un entier positif $n$ tel que $f^n(u) = f^n(v)$. La classe d'équivalence de $u \in V(G)$ est appelée le feuillet de $u$ (noté feuillet($u$)) et l'ensemble de tous les feuillets de $V(G)$ est appelé la foliation de $G$. Comme la composante connexe $G_f(u)$ de tout sommet $u$ dans $G^f$ est l'ensemble $\{v \in V(G) : f^n(v) = f^m(u) \text{ pour certains } n \ge 1, m \ge 1\}$, nous avons feuillet($u$) $\subseteq V(G_f(u))$.
Les auteurs ont montré dans [7] que, étant donné un graphe aléatoire unimodulaire enraciné [G, o], c.-à-d. la composante connexe de la racine dans le *f*-graphe $G^f$, est un arbre généalogique unimodulaire appartenant à l'une des trois classes : $\mathcal{F}/\mathcal{F}$, $\mathcal{I}/\mathcal{I}$, et $\mathcal{I}/\mathcal{F}$. La classe $\mathcal{F}/\mathcal{F}$ correspond au ces où la composante de o est finie et ses feuillets sont finis. De même, les classes $\mathcal{I}/\mathcal{I}$ et $\mathcal{I}/\mathcal{F}$ correspondent au ces où la composante est infinie et tous les feuillets de la composante sont infinis, et où la composante est infinie et tous les feuillets de la composante sont finis, respectivement. Il est facile de voir que le décalage record $R$ est un décalage de sommet, ce qui implique que l'arbre généalogique $[T, 0]$ est unimodulaire, où $T$ est la composante connexe de 0 dans le graphe des records. Les trois phases du graphe des records $[T, 0]$ pour $\mathbb{E}[X_0] < 0$, $\mathbb{E}[X_0] = 0$ et $\mathbb{E}[X_0] > 0$ correspondent à ces trois classes $\mathcal{F}/\mathcal{F}$, $\mathcal{I}/\mathcal{I}$ et $\mathcal{I}/\mathcal{F}$ respectivement. Ainsi, le décalage record est un exemple pour lequel les trois classes se produisent respectivement en fonction de la moyenne $\mathbb{E}[X_0]$.

En utilisant le cadre de [3], nous considérons les accroissements de la
marche aléatoire sans saut comme des marques associées aux arêtes de
$\mathbb{Z}$, vues depuis la racine 0. Plus précisément, nous considérons le réseau
aléatoire enraciné $[\mathbb{Z}, 0, X]$, avec $X = (X_n)_{n \in \mathbb{Z}}$ étant la suite des accroisse-
ments et $X_n$ étant le label assigné à l'arête $(n, n+1)$, pour tout $n \in \mathbb{Z}$. Il est
facile de voir que $[\mathbb{Z}, 0, X]$ est un réseau unimodulaire. Par vue locale depuis
le $n$-ième record $(n \ge 1)$, nous entendons la distribution de $[\mathbb{Z}, R^n(0), X]$.
Cette dernière est la même que celle de $[\mathbb{Z}, 0, R^n(0)X]$, où $R^n(0)X$ est la
suite décalée $(X_{m+R^n(0)})_{m \in \mathbb{Z}}$. En utilisant l'unimodularité de $[\mathbb{Z}, 0, X]$, nous
montrons que la vue locale depuis le $n$-ième record est absolument continue
par rapport à $[\mathbb{Z}, 0, X]$ avec une dérivée de Radon-Nikodym $d_n(0)$, qui est
définie comme le nombre d'entiers pour lesquels $0$ est le $n$-ième record.

De plus, en lien avec la troisième question, nous montrons que la vue locale vue depuis le *n*-ième record lorsque *n* tend vers *∞*, $\lim_{n \to \infty}[\mathbb{Z}, 0, R^n(0)X]$, existe pour $\mathbb{E}[X_0] < 0$, $\mathbb{E}[X_0] = 0$ et $\mathbb{E}[X_0] > 0$ respectivement. Notons cette limite par $[\mathbb{Z}, 0, Y]$, où $Y = (Y_n)_{n \in \mathbb{Z}}$ est la marque sur les arêtes de $\mathbb{Z}$. Nous observons que $Y$ n'est pas une suite i.i.d. En particulier, sa partie négative $(Y_n)_{n<0}$ n'est pas une suite i.i.d. Cependant, elle a une structure régénérative lorsque $\mathbb{E}[X_0] \ge 0$.

En ce qui concerne la quatrième question, une fonction $R'$ sur $\mathbb{Z}$ est dite
préservant les feuillets avec $R$ si elle envoie chaque feuillet sur lui-même,
c'est-à-dire que pour tout $i \in \mathbb{Z}$, $R'(i)$ appartient au feuillet $(i)$ (le feuillet
associé au décalage de sommet $R$ et $i$).
Lorsque $\mathbb{E}[X_0] \ge 0$, nous définissons une fonction aléatoire $R_\perp$ qui envoie $i$ en

$$R_\perp(i) = \inf\{k > i : R^n(i) = R^n(k) \text{ pour un certain } n \ge 1\}.$$

Nous montrons que $R_\perp$ préserve les feuillets de $R$ et préserve la distribution de $[\mathbb{Z}, 0, X]$, c'est-à-dire que la distribution de $[\mathbb{Z}, R_\perp(0), X]$ est la même que celle de $[\mathbb{Z}, 0, X]$.

Les statistiques des records des séries temporelles ont trouvé des applications en finance, hydrologie et physique. Voir par exemple les références dans l'article de synthèse [13] pour une liste non exhaustive d'applications. Ces études sur les records sont centrées sur des statistiques telles que la distribution du n-ième record, l'âge d'un record (c'est-à-dire l'écart entre deux records consécutifs), et l'âge du record le plus durable ([21], [13]). Lorsque la série temporelle considérée est une suite i.i.d., il est montré dans [19] que la moyenne du saut entre deux valeurs consécutives de record conditionnée à la valeur initiale du record peut caractériser la distribution de la suite i.i.d. En revanche, dans le présent travail, l'accent est mis sur la structure locale conjointe des records des marches aléatoires sans saut vers la gauche. La structure a une connexion naturelle avec la notion d'arbre généalogique qui justifié de parler de 'généalogie des records'.

La relation entre les marches aléatoires sans saut vers la gauche et les arbres de Galton-Watson a été largement discutée dans, par exemple, [8], [16] et [14]. En fait, les auteurs de [8] codent l'arbre de Galton-Watson critique et montrent que le codage donne une correspondance entre les records de la marche aléatoire et les ancêtres de la racine dans l'arbre de Galton-Watson. Nous étendons ces idées pour définir l'application réciproque $\Phi_R$ qui prend un graphe des records et le renvoie à la trajectoire d'une marche aléatoire (voir Section 5.1, Chapitre 5). Cependant, nous ne sommes pas limités aux arbres de Galton-Watson finis ici. À notre connaissance, cette description complète du graphe des records de la marche aléatoire sans saut est nouvelle. Nous ne sommes pas limités au cas des marche aléatoires par ailleur.

Dans le chapitre 2, nous donnons les préliminaires et les énoncés des théorèmes que nous utilisons dans ce travail. Nous introduisons les espaces probabilisés canoniques dans lesquels nos objets aléatoires prennent leurs valeurs et introduisons la dynamique induite par les décalages de sommets. Nous nous concentrons sur l'étude des décalages de sommets sur les réseaux unimodulaires. Nous énonçons un théorème clé que nous utilisons à cet
égard, connu sous le nom de théorème de classification des feuillets dans les réseaux unimodulaires. Nous introduisons également quelques opérations sur les arbres généalogiques unimodulaires.

Dans le chapitre 3, nous introduisons le décalage de sommet des records. Nous étudions ses propriétés sur les suites déterministes à valeurs entières. Nous étudions les propriétés du graphe des records associé aux suites. En utilisant ces propriétés, nous prouvons que le graphe des records de $[\mathbb{Z}, 0, X]$ présente des transitions de phase, où $X$ est la suite i.i.d. des accroissements d'une marche aléatoire sans saut vers la gauche. Nous décrivons également la distribution de la composante de (0) dans le graphe des records de $[\mathbb{Z}, 0, X]$ dans chacune de ces phases. Nous définissons la fonction $R_⊥$ et prouvons qu'elle préserve la loi de $[\mathbb{Z}, 0, X]$ lorsque $\mathbb{E}[X_0] = 0$.

Dans le chapitre 4, nous nous intéressons aux décalages de sommets généraux sur les réseaux unimodulaires et nous étudions l'existence et l'unicité des probabilités de décalage de sommet. Nous fournissons des conditions suffisantes sous lesquelles un décalage de sommet sur un réseau aléatoire a une probabilité de décalage de sommet unique. Nous appliquons ces résultats pour calculer la probabilité de décalage de sommet des arbres généalogiques unimodulaires où le décalage de sommet est donné par le décalage de sommet parent.

Dans le chapitre 5, nous appliquons les résultats du chapitre 4 pour étudier la $R$-probabilité de $[\mathbb{Z}, 0, X]$, où $R$ est le décalage record de sommet et $X$ est la suite i.i.d. des accroissements d'une marche aléatoire sans saut vers la gauche. Nous donnons également des constructions pour générer la $R$-probabilité.

Dans le chapitre 6, nous étudions le graphe des records d'une suite stationnaire et ergodique. Nous montrons que la composante de 0 dans le graphe des records présente une transition de phase en 0 lorsque la moyenne varie entre $-\infty$ et $+\infty$ (voir le théorème 119). Nous fournissons une condition suffisante sous laquelle un EFT ordonné unimodulaire peut être représenté comme la composante de 0 dans le graphe des records du réseau associé à une suite stationnaire (théorème 121).
# Chapter 2

## Preliminaries

In this chapter, we summarize the framework of networks given in [3] and in [7].

### 2.1 Canonical probability spaces for networks

A graph $G$ with a vertex set $V = V(G)$ and an (undirected) edge set $E = E(G)$ is denoted by $G = (V, E)$. A **network** is a graph $G = (V, E)$ together with a Polish space $\Xi$ and two maps: one from $V$ to $\Xi$ and the other from $E$ to $\Xi$. The space $\Xi$ is called mark space and the value assigned to a vertex (resp. an edge) is called **mark of the vertex** (resp. edge). Each edge $e = \{x, y\}$ in the network has two marks associated with its endpoints, one assigned to $\{e, x\}$ and the other assigned to $\{e, y\}$. A directed edge can be obtained from an undirected edge by assigning 0 as mark to one of its endpoint and 1 as mark to the other, with the understanding that the orientation of the directed edge is from the endpoint with mark 0 to the endpoint with mark 1. A graph can be seen as a network with a fixed mark. In this work, we focus on the networks that are connected and locally finite, i.e., degree of every vertex is finite, and whose mark space is $\mathbb{Z}$.

An **isomorphism** $\phi$ of networks $G_1$ and $G_2$, denoted as $\phi : G_1 \to G_2$, is a bijective map $\phi_V : V(G_1) \to V(G_2)$ satisfying the three conditions: (1) for every pair of vertices $u, v \in V(G_1)$, $(u, v)$ is an edge of $G_1$ if and only if $(\phi_V(u), \phi_V(v))$ is an edge of $G_2$, (2) for all $u \in V(G_1)$, mark of $u$ is the same as that of $\phi_V(u)$, (3) for all $e = (u, v) \in E(G_1)$, mark of $e$ is same as
that of $(\phi_V(u), \phi_V(v))$. In particular, both $G_1, G_2$ should have the same
mark space.

A **rooted network** $(G, o)$ is a network $G$ with a distinguished vertex $o \in V(G)$. For any $r \ge 0$, let $(G, o)_r$ be the subgraph induced by the vertices $\{u \in V(G) : d_G(u, o) \le r\}$, where $d_G$ denotes the graph distance in $G$, and for any vertex $v \in V((G, o)_r)$, let $((G, o)_r, v)$ be the rooted network obtained by rooting $(G, o)_r$ at $v$. The marks of $(G, o)_r$ are induced by the marks of $(G, o)$. A **rooted-isomorphism** $\phi$ of two rooted networks $(G_1, o_1), (G_2, o_2)$ is an isomorphism $\phi : G_1 \to G_2$ of networks $G_1, G_2$ with the additional condition that $\phi_V(o_1) = \phi_V(o_2)$. Two rooted networks $(G_1, o_1)$ and $(G_2, o_2)$ are said to be **equivalent**, denoted as $(G_1, o_1) \sim (G_2, o_2)$, if and only if there is a rooted-isomorphism from one to the other. An equivalent class of $(G_1, o_1)$ is denoted by $[G_1, o_1]$. We do not distinguish between a rooted graph and its equivalent class unless explicitly stated.

A doubly rooted network $(G, u, v)$ is a network $G$ with two distinguished vertices $u, v \in V(G)$. For any $r \ge 0$, let $(G, u, v)_r$ be the subgraph induced by the vertices $\{w \in V(G) : d_G(w, u) \wedge d_G(w, v) \le r\}$ with marks of edges and vertices induced from that of $G$, where $d_G$ denotes the graph distance in $G$ and $\wedge$ denotes the minimum function. A doubly rooted-isomorphism $\phi$ of two doubly rooted networks $(G_1, u_1, v_1)$ and $(G_2, u_2, v_2)$ is an isomorphism $\phi : G_1 \to G_2$ of networks $G_1, G_2$ such that $\phi_V(u_1) = u_2$ and $\phi_V(v_1) = v_2$. Two doubly rooted networks $(G_1, u_1, v_1)$ and $(G_2, u_2, v_2)$ are said to be equivalent, denoted as $(G_1, u_1, v_1) \sim (G_2, u_2, v_2)$, if and only if there exists a doubly rooted-isomorphism between them.

We denote the **space of equivalence class of rooted locally finite and connected networks** by $\mathcal{G}_*$ and the **space of equivalence class of doubly rooted locally finite and connected networks** by $\mathcal{G}_{**}$.

The space $\mathcal{G}_*$ can be equipped with a metric in the following way: distance between two rooted networks $(G_1, o_1)$ and $(G_2, o_2)$ is defined as $2^{-d_{1,2}}$, where $d_{1,2}$ is the supremum of $r \ge 0$ such that there exists a network isomorphism $\phi_r : (G_1, o_1)_r \to (G_2, o_2)_r$ and that for every $u \in V(G_1), (v, w) \in E(G_1)$, the distance between marks of $u$ and of $\phi(u)$ is at most $\frac{1}{r}$, and the distance between mark of $(v, w)$ and of $(\phi_r(v), \phi_r(w))$ is at most $\frac{1}{r}$. The space $\mathcal{G}_{**}$ can also be equipped with a metric in the similar way as in $\mathcal{G}_*$ by defining the distance between two doubly rooted networks $(G_1, u_1, v_1)$ and $(G_2, u_2, v_2)$ as $2^{-d_{1,2}}$, where $d_{1,2}$ is the same as in $\mathcal{G}_*$ but applied to $(G_1, u_1, v_1)_r, (G_2, u_2, v_2)_r$ instead of $(G_1, o_1)_r, (G_2, o_2)_r$ respectively. The topology generated on $\mathcal{G}_*$ with the above metric is called the local topology.
Both the spaces $G_*$ and $G_{**}$ endowed with their respective metrics are Polish spaces. Let us denote the space of equivalence classes of graphs by $\hat{G}_*$

In this work, we often encounter with a special networks called Family Trees. A **Family Tree** is a locally finite directed tree that has the property that the out-degree of every vertex is at most 1. If the out-degree of every vertex is equal to 1 a.s. then it is called an **Eternal Family Tree** (EFT). A vertex $u$ of a Family Tree is called the **parent** of a vertex $v$ if there is a directed edge from $v$ to $u$. In this case, $v$ is called a **child** of $u$. An **ordered Family Tree** is a Family Tree in which children of every vertex are ordered. Although, we use similar notation for ordered and unordered, one can distinguish them depending on the context. A rooted (ordered) Family Tree is a pair $(T, o)$, where $T$ is an (ordered) Family Tree and $o$ is a distinguished vertex of $T$. The space of equivalence classes of rooted (ordered) Family Trees is denoted by $\mathcal{T}_*$, where the equivalence relation is given by rooted (ordered) isomorphisms, i.e., two rooted Family Trees are equivalent if there is a rooted isomorphism between them that preserves the order. The space $\mathcal{T}_*$ is Polish with respect to local topology [7]. By forgetting the order of an ordered Family Tree, one obtains an unordered Family Tree. We often call a rooted Family Tree, a Family Tree.

We will also encounter marked Family Trees whose vertices have $Z$-valued marks. Denote the space of equivalence classes of such (rooted) marked Family Trees by $\hat{\mathcal{T}}_*$.

A random (rooted) network is a measurable map from a probability space to $G_*$. We use the bold fonts to denote a random network and normal fonts to denote a realization of a random network.

We use the following theorem to prove the convergence of random networks. For any rooted network $(G, o)$ and $r \ge 0$, let $[G, o]_r$ denote the equivalent class $(G, o)_r$.

**Theorem 1 ([17]).** A sequence of random networks $([G_n, o_n])_{n \ge 1}$ converges in distribution to a random network $[G, o]$ as $n \to \infty$ if and only if for every $r \ge 0$, the sequence of random networks $([G_n, o_n]_r)_{n \ge 1}$ converges in distribution as $n \to \infty$.
## Relative compactness and tightness

We recall the definitions of relative compactness and tightness. This sub-section is concerned only about graphs (not networks). A subset $\mathcal{A}$ of a topological space is said to be **relatively compact** if every sequence in $\mathcal{A}$ has a convergent subsequence. A subset $\mathcal{A}$ of probability measures on a measurable space is said to be **tight** if for any $\epsilon > 0$ there exists a compact set $K$ such that $\forall \mathcal{P} \in \mathcal{A}, \mathcal{P}[K] \ge 1 - \epsilon$. In particular, if there exists an increasing sequence of compact sets $\{K_m\}_{m \in \mathbb{N}}$ such that

$$ \limsup_{m \to \infty} \mathcal{P}[K_m^c] = 0, $$

then $\mathcal{A}$ is tight. Prokhorov's theorem states that if $\mathcal{A}$ is tight then $\mathcal{A}$ is relatively compact and if the measurable space is complete and separable, then relative compactness is equivalent to tightness, i.e., $\mathcal{A}$ is relatively compact if and only if $\mathcal{A}$ is tight.

For any $r \ge 0$, we define the restriction map $|_r : \mathcal{G}_* \to \mathcal{G}_*$ taking $[G, o]$ to $[G, o]_r$ by $[G, o]_r = [(G, o)|_r, o]$ for any $[G, o] \in \mathcal{G}_*$. The image of this restriction map $\mathcal{G}_*|_r$ is countable and does not have any accumulation point. So, every compact subset of $\mathcal{G}_*|_r$ is finite. Let $K_m^r$ be those rooted graphs of $\mathcal{G}_*|_r$ that have at most $m$ vertices, i.e., $K_m^r := \{[G, o] \in \mathcal{G}_*|_r \text{ such that } |V(G)| \le m\}$ which is a finite set. Then, the sequence $\{K_m^r\}_{m \in \mathbb{N}}$ is an increasing sequence of compact sets.

We state a lemma that gives an equivalent condition for a sequence of random graphs to be tight in terms of their neighborhood restrictions.

**Lemma 2.** A family of random graphs $\{[G_i, o_i], i \in I\}$ is tight if and only if for all $r \ge 1$, the family $\{[G_i, o_i]_r, i \in I\}$ is tight.

*Proof.* Refer [17]. □

<figure><img src="image_4.png" /></figure>

Therefore, from the above discussion and Lemma 2, we conclude that a family of random graphs $\{[G_i, o_i], i \in I\}$ is relatively compact if and only if for any $r \ge 1$

$$ \limsup_{m \to \infty} \mathcal{P}[[G_i, o_i]_r \notin K_m^r] = 0. $$

We use this conclusion to prove the relative compactness of vertex-shift-probabilities when the vertex-shift has finite orbits.
## 2.2 Dynamics on networks

The dynamics we look at are navigation rules known as vertex-shifts on random networks. The definitions and notations of this section are taken from [7].

**Definition 3.** A vertex-shift $f$ is a collection of maps indexed by networks $f_G : V(G) \to V(G)$, where $G$ is a locally finite network, satisfying the following properties:

1. *Covariance*: For any graph isomorphism $\sigma: G \to H$ of two graphs $G$ and $H$, $f$ satisfies $f_H \circ \sigma = \sigma \circ f_G$,

2. *Measurability*: The map $[G, u, v] \mapsto \mathbf{1}_{\{f_G(u)=v\}}$ from the doubly rooted space $\mathcal{G}_{**}$ is measurable.

The first condition allows us to define a (deterministic) dynamic on the space $\mathcal{G}_*$ in the following way: for each vertex-shift $f$, define a map $\theta_f$ by

$$ \theta_f: \mathcal{G}_* \to \mathcal{G}_* \\ [G, o] \mapsto [G, f(o)]. \qquad (2.2.1) $$

The map $\theta_f$ is well-defined.

The second condition allows us to define the following functions. For any non-negative measurable function $h: \mathcal{G}_{**} \to \mathbb{R}_{\ge 0}$, we define two measurable functions $h^+ : \mathcal{G}_* \to \mathbb{R}_{\ge 0}$ and $h^- : \mathcal{G}_* \to \mathbb{R}_{\ge 0}$ by

$$ h^+([G, o]) = \sum_{u \in V(G)} h([G, o, u]) \mathbf{1}\{f_G(u) = o\} \\ h^-([G, o]) = \sum_{u \in V(G)} h([G, u, o]) \mathbf{1}\{f_G(o) = u\}, $$

for all $[G, o] \in \mathcal{G}_*$.

## Notations

Given a vertex-shift $f$ and a network $G$, the $f$-graph of $G$ is the network $G^f$ with vertex set $V(G^f) := V(G)$ and directed edges $E(G^f) = \{(u, f_G(u)) : u \in V(G) \text{ and } f_G(u) \neq u\}$. Let $G^f(u)$ denote the component of $u$, for any vertex $u \in V(G)$. Define the map $\Psi_f: \mathcal{G}_* \to \mathcal{T}_*$ that maps a rooted network
$[G, o]$ to $[G^f(o), o]$, where $G^f(o)$ is obtained by discarding all self-loops (if there are any) of the connected component of $o$ in its $f$-graph $G^f$.

For every vertex-shift $f$ on a network $G$, the components of the $f$-graph of $G$ are Family Trees [7]. For any integer $n \ge 0$, a vertex of the form $f_G^n(u)$ is called the **ancestor of order $n$ of $u$** (also called $n$-th ancestor of $u$). We denote the set of $n$-th descendants (also called descendants of order $n$) of vertex $u \in V(G)$ by $D_n(u) := \{v \in V(G)\setminus\{u\} : f_G^n(v) = u\}$ and its cardinality by $d_n(u) := \#D_n(u)$, for any $n \ge 1$. We follow the convention that $f^0(u) = D_0(u) = u$. Denote the set of all descendants of $u$ by $D(u) := \{v \in V(G)\setminus\{u\} : f_G^n(v) = u \text{ for some } n > 0\} \cup \{u\}$ and its cardinality by $d(u) = \#D(u)$. For any vertex $u \in G$, its ancestor of order 1 is called the **parent of $u$**, its descendants of order 1 are called **children of $u$**, and the set $\{v \in V(G)\setminus\{u\} : f_G(v) = f_G(u)\}$ is called the **set of siblings of $u$**.

A vertex-shift $f$ defines the following equivalence relation on the vertices of any network $G$: two vertices $u$ and $v$ of $G$ are equivalent if and only if $f_G^n(u) = f_G^n(v)$ for some $n \ge 0$. The equivalence class of $u$ is called the **$f$-foil** of $u$, and the collection of $f$-foils of $G$ is called the **$f$-foliation** of $G$.

A **covariant subset** is a collection of subsets $S_G$ indexed by network $G$, where $S_G \subseteq V(G)$ and the collection satisfies the following two conditions, (1) for every network isomorphism $\alpha : G \to H$, we have $\alpha(S_G) = S_H$, (2) the map $[G, o] \mapsto \mathbf{1}_{\{o \in S_G\}}$ is measurable. A **covariant partition** is a collection of partitions $\Pi_G$ indexed by network $G$, where $\Pi_G$ is a partition of $V(G)$ and the collection satisfies the following two conditions, (1) for every network isomorphism $\alpha : G \to H$, we have $\alpha \circ \Pi_G = \Pi_H$, (2) the subset $\{[G, o, u] : u \in \Pi_G(o)\}$ is a measurable subset.

Examples of covariant partitions can be constructed from any vertex-shift $f$. Given $f$, the collection of $f$-foils of $G$ indexed by $G$ is a covariant partition. Similarly, the collection of subsets $S_G = \{u \in V(G) : f_G(u) = u\}$ of $V(G)$ indexed by network $G$ is an example of a covariant subset.

**Example 4.** For every Family Tree $T$, consider the map $F_T : V(T) \to V(T)$ that maps every vertex $u$ to its parent if it exists, otherwise maps to itself. The vertex-shift $F$ is called the **parent vertex-shift**.

For every vertex-shift $f$ on $G$, the $f$-graph of $G$ is a Family Tree [7]. Observe that the terminologies of parent and child are consistent with respect to the parent vertex-shift. The dynamic naturally induced by the parent vertex-shift is given by $\theta_F : \mathcal{T}_* \to \mathcal{T}_*$ given by $\theta_F([T, o]) = [T, F(o)]$.
Given a Family Tree $T$, let $l(\cdot, \cdot) = l_T(\cdot, \cdot) : V(T) \times V(T) \to \mathbb{Z}$ be the function defined by the following equations: for every $v, w \in V(T)$,

$$ 
\begin{aligned}
l(v, v) &= 0, & l(v, F(w)) &= l(v, w) - 1, \\
l(w, v) &= -l(v, w), & l(v, w) + l(w, z) &= l(v, z).
\end{aligned}
$$

For a rooted Family Tree $[T, o]$, the set $\{w \in V(T) : l(o, w) = n\}$ is the $n$-th generation of $[T, o]$.

### Royal Line of Succession order

Let $T$ be an ordered Family Tree, i.e., the children of every vertex are totally ordered, with an order denoted by $<$. We can extend this order on children to a total order on the vertices of $T$ in the following way. Let $u, v$ be two vertices of $T$. We say that $v$ has precedence over $u$, denoted as $v > u$ (or $u < v$), if either $F^k(u) = v$ for some $k > 0$, or there exists a common ancestor $w = F^m(u) = F^n(v)$ of $u$ and $v$ with $m, n$ being the smallest positive integers with this property, and $F^{m-1}(u) < F^{n-1}(v)$. In the latter case, both $F^{m-1}(u)$ and $F^{n-1}(v)$ can be compared since they are children of $w$.

*Remark 5.* For two vertices $u, v$ with common ancestor $w$, distinct from $u$ and $v$, $u < v$ if and only if $y_u < y_v$ for every descendant $y_u$ of $u$ and for every descendant $y_v$ of $v$.

We call the total order $<$ the **Royal Line of Succession (RLS) order** associated with $<$. It is also known as **Depth First Search order**.

## 2.3 Unimodular random networks and their properties

**Definition 6.** A random network $[G, o]$ is said to be **unimodular** if it satisfies the **Mass Transport Principle**:

$$ \mathbb{E}\left[\sum_{u \in V(G)} f([G, o, u])\right] = \mathbb{E}\left[\sum_{u \in V(G)} f([G, u, o])\right], \quad (2.3.1) $$

for every non-negative measurable function $f : \mathcal{G}_{**} \to \mathbb{R}_{\ge 0}$.
The following theorem suggests that there are a wide class of unimodular random networks. For any finite network $G$, we can associate a random rooted network $[G, \mathbf{o}]$ by choosing the root uniformly among the vertices of $G$, i.e., for any measurable set $A \subset \mathcal{G}_*$, we have

$$ \mathbb{P}[[G, \mathbf{o}] \in A] = \frac{1}{\#V(G)} \sum_{u \in V(G)} \mathbf{1}_A([G, u]). \qquad (2.3.2) $$

It can be easily shown that $[G, \mathbf{o}]$ is unimodular [17]. In fact every random finite network can be obtained by uniformly choosing the root [17].

**Theorem 7 ([3]).** Let $[G_n, o_n]$ be a sequence of unimodular networks that converge in distribution to a random network $[G, o]$. Then, $[G, o]$ is unimodular.

The above theorem implies that if $(G_n)_{n \ge 1}$ is a sequence of finite deterministic networks such that the sequence of random networks $([G_n, o_n])_{n \ge 1}$, obtained by applying Eq. (2.3.2), converges in distribution to a random network $[G, o]$, then $[G, o]$ is unimodular. In the above, we can replace deterministic finite network by random finite network. The network $[G, o]$ is said to be obtained by taking **Benjamini-Schramm** limit of $(G_n)_{n \ge 1}$.

**Definition 8 (Network associated to a sequence).** Let $x = (x_n)_{n \in \mathbb{Z}}$ be a sequence of real numbers. The network associated to $x$ is the network $(\mathbb{Z}, x)$ with vertex set $\mathbb{Z}$, with edge set $\{(n, n+1) : n \in \mathbb{Z}\}$, and with $x_n$ as mark of the edge $(n, n+1)$ for all $n \in \mathbb{Z}$.

See Figure 2.1 for an illustration.

**Example 9 (of a unimodular network).** Let $X = (X_n)_{n \in \mathbb{Z}}$ be a stationary sequence. The network $[\mathbb{Z}, 0, X]$ associated to the sequence $X$ is unimodular.

The network $[\mathbb{Z}, 0, X]$ in Example 9 is unimodular because the network can be shown to be the **Benjamini-Schramm** limit of the sequence $(G_n, X^{(n)})_{n \ge 1}$, where $(G_n, X^{(n)})$ is the network with vertex set $\{-n, -n+1, \dots, 0, 1, \dots, n\}$, edge set $\{(k, k+1) : -n \le k \le n-1\}$ with mark $X_k$ assigned to the edge $(k, k+1)$ for all $-n \le k \le n-1$.
<figure><img src="image_5.png" /><figcaption>Figure 2.1: The network $(\mathbb{Z}, x)$ associated to a sequence $x = (x_n)_{n \in \mathbb{Z}}$. The rooted network $[\mathbb{Z}, 0, x]$ denotes the equivalence class of the network $(\mathbb{Z}, x)$ rooted at 0.</figcaption></figure>

### Vertex-shifts on unimodular networks

Recall the map $\theta_f$, in Eq. (2.2.1), associated to a vertex-shift $f$. The following proposition will be used in the later chapters while studying measure preserving vertex-shifts.

**Proposition 10** (Mecke-Thorisson Point Stationarity [7]). Let $f$ be a vertex-shift and $[G,o]$ be a unimodular measure. Then, the map $\theta_f$ preserves the distribution of $[G,o]$ if and only if $f$ is a.s. bijective.

The following two propositions will be used to show in the later chapters that a unimodular ordered Family Tree does not have a smallest nor a largest vertex.

**Proposition 11** ([7]). Let $[G,o]$ be unimodular and $f$ be a vertex-shift.

1. If $f$ is injective a.s., then $f$ is bijective a.s.

2. If $f$ is surjective a.s., then $f$ is bijective a.s.

**Lemma 12** (No Infinite/Finite Inclusion [7]). Let $[G,o]$ be a unimodular network, $\mathcal{S}$ be a covariant subset and $\Pi$ be a covariant partition. Almost surely, there is no infinite element $E$ of $\Pi_G$ such that $E \cap \mathcal{S}_G$ is finite and non-empty.

The following lemma shows that probability that covariant subset is non-empty is related to the probability that the root belongs to this covariant subset.
**Lemma 13 ([7]).** Let $[G,o]$ be a unimodular network, $\mathcal{G}$ be a covariant subset. Then, $\mathbb{P}[\mathcal{G}_G \text{ is non-empty}] > 0$ if and only if $\mathbb{P}[o \in \mathcal{G}_G] > 0$.

*Proof.* Take $f([G, u, v]) = \mathbf{1}\{v \in \mathcal{G}_G\}$ and apply the Mass Transport Principle. $\square$

The following theorem gives a classification of the components of $f$-graph, for any vertex-shift $f$ on a unimodular network.

**Theorem 14 (Foil Classification in Unimodular Networks [7]).** Let $[G,o]$ be a unimodular network and $f$ be a vertex-shift. Almost surely, every vertex has finite degree in the graph $G^f$. In addition, each component $C$ of $G^f$ has at most two ends and it belongs to one of the following three classes:

* Class $\mathcal{F}/\mathcal{F}$: $C$ and all its foils are finite. If $n = n(C)$ is the number of foils in $C$, then

- $C$ has a unique $f$-cycle and its length is $n$;

- $f_G^\infty(C)$ is the set of vertices of the cycle;

- Each foil of $C$ contains exactly one vertex of the cycle.

* Class $\mathcal{I}/\mathcal{F}$: $C$ is infinite but all its foils are finite. In this case,

- The (undirected) $f$-graph on $C$ is a tree;

- There is a unique bi-infinite $f$-path in $C$, each foil in $C$ contain exactly one vertex of the path, and $f_G^\infty(C)$ coincides with the set of vertices of the path;

- The order of the foils of $C$ is of type $\mathbb{Z}$; that is, there is no youngest foil in $C$.

* Class $\mathcal{I}/\mathcal{I}$: $C$ and all foils of $C$ are infinite. In this case,

- The (undirected) $f$-graph on $C$ is a tree;

- $C$ has one end, there is no bi-infinite $f$-path in $C$, $D(v)$ is finite for every vertex $v \in C$, and $f_G^\infty(C) = \emptyset$;

- The order of the foils of $C$ is of type $\mathbb{N}$ or $\mathbb{Z}$, that is, there may or may not be a youngest foil in $C$.
We will see examples from each class in the next chapter. The above theorem when applied to Family Trees gives the following theorem, which will be used in the later chapters. Recall the notation that $F$ denotes the parent vertex-shift.

**Theorem 15** (Classification of unimodular Family Trees [7]). *A unimodular Family Tree almost surely belongs to one of the following three classes:*

1. Class $\mathcal{F}/\mathcal{F}$: the tree is finite.

2. Class $\mathcal{I}/\mathcal{I}$: every generation is infinite, each vertex has finitely many descendants, and there is no bi-infinite path, i.e., the tree is one-ended.

3. Class $\mathcal{I}/\mathcal{F}$: every generation is finite and the set of vertices that have infinitely many descendants form a unique bi-infinite $F$-path, i.e., the tree has two ends.

The following lemma gives a recipe to construct unimodular Family Trees. Recall that for a vertex-shift $f$ and a network $G$, $G^f$ denotes the $f$-graph of $G$ and for any vertex $u \in V(G)$, $G^f(u)$ denotes the component of $u$ in $G^f$.

**Lemma 16** ([7]). *Let $f$ be a vertex-shift and $[G,o]$ be a random rooted network. If $[G,o]$ is unimodular then the Family Tree $[G^f(o),o]$ is unimodular.*

### Unimodular ordered Eternal Galton-Watson Tree

We give an example of unimodular Family Tree of class $\mathcal{I}/\mathcal{I}$ originally introduced in [7].

Let $\pi$ be a probability distribution on $N \cup \{0\}$ with mean $m(\pi) = 1$, and $\hat{\pi}$ be its size-biased distribution defined by $\hat{\pi}(k) = k\pi(k)$, $\forall k \ge 0$.

The ordered unimodular Eternal Galton-Watson Tree with offspring distribution $\pi$, $EGWT(\pi)$, is a rooted ordered Eternal Family Tree $[T,o]$ with the following properties. The root $o$ and all of its descendants reproduce independently with the common offspring distribution $\pi$. For all $n \ge 1$, the ancestor $F^n(o)$ of $o$ reproduces with distribution $\hat{\pi}$. The descendants of $F^n(o)$ which are not the descendants of $F^{n-1}(o)$ (and not $F^{n-1}(o)$) reproduce independently with the common offspring distribution $\pi$, with the
convention $F^0(o) = o$. All individuals (vertices) reproduce independently. The order among the children of every vertex is uniform.

In particular, except for the vertices $F^n(o)$, $n \ge 1$, which reproduce independently with distribution $\hat{\pi}$, all the remaining vertices of the tree reproduce independently with distribution $\pi$. See Figure 2.2 for an illustration. It is proved in [7] that $EGWT(\pi)$ is unimodular if and only if the mean $m(\pi)$ is 1.

<figure><img src="image_6.png" /><figcaption>Figure 2.2: The Eternal Galton-Watson Tree with offspring distribution $\pi$. Notation: $GW(\pi)$ denotes the Galton-Watson Tree, $\hat{\pi}$ is the size-biased distribution of $\pi$. The order among the children of every vertex is from the left to the right.</figcaption></figure>

*Remark 17.* Let $[T,o]$ be an $EGWT(\pi)$ with mean $m(\pi) = 1$. Then, the descendant trees of all vertices, except for the ancestors of the root $o$, are independent critical Galton-Watson trees with offspring distribution $\pi$. Therefore, the descendant trees are finite. Hence, a realization of $EGWT(\pi)$ has the property that the descendant tree of every vertex of it is finite. So, it is of class $I/I$.

The following theorem characterizes a unimodular EGWT.

**Theorem 18 ([7]).** A unimodular Eternal Family Tree $[T,o]$ is an EGWT if and only if the number of children of the root $d_1(o)$ is independent of the non-descendant tree $D^c(o)$, i.e., the subtree induced by $(V(T)\setminus D(o))\cup\{o\}$.
### Unimodular Family Trees of class I/F

In the following, we describe a construction given in [7] used to generate unimodular Family Trees of class I/F.

Let $([T_i, o_i])_{i \in \mathbb{Z}}$ be a stationary sequence of finite random rooted Family Trees. Add a directed edge $(o_i, o_{i+1})$ for all $i \in \mathbb{Z}$, and denote this new Eternal Family Tree (EFT) by $T'$ and let $o' = o_0$. The EFT $[T', o']$ is called the **joining** of $([T_i, o_i])_{i \in \mathbb{Z}}$.

In addition, suppose that $\mathbb{E}[\#V(T_0)] < \infty$. Choose the root uniformly in $V(T_0)$ and bias the measure by the mean size of $V(T_0)$. Formally, define a measure $\sigma'$ by: for any measurable set $A$,

$$ \sigma'[A] = \frac{1}{\mathbb{E}[\#V(T_0)]} \mathbb{E} \left[ \sum_{v \in V(T_0)} 1_{[T',v]}(A) \right]. \quad (2.3.3) $$

An operator similar to $\sigma'$ is defined in [2]. An EFT $[T, o]$ whose distribution is $\sigma'$ is called the **typically rooted joining** of $([T_i, o_i])_{i \in \mathbb{Z}}$. Note that the assumption $\mathbb{E}[\#V(T_0)] < \infty$ is not needed in the joining operation, however, it is essential in order to define the typically rooted joining operation. We state the following results taken from [7].

**Theorem 19 ([7]).** Let $[T, o]$ be the typically rooted joining of a stationary sequence $([T_i, o_i])_{i \in \mathbb{Z}}$, where $\mathbb{E}[\#V(T_0)] < \infty$. Then, $[T, o]$ is unimodular.

**Theorem 20 ([7]).** Let $[T, o]$ be a unimodular EFT of class I/F a.s., and $[T', o']$ be the Family Tree obtained by conditioning $[T, o]$ on the event that $o$ belongs to the bi-infinite path of $T$. Then, $[T', o']$ is the joining of some stationary sequence of finite Family Trees $([T_i, o_i])_{i \in \mathbb{Z}}$ and $[T, o]$ is the typically rooted joining of $([T_i, o_i])_{i \in \mathbb{Z}}$.

### Typical re-rooting operation

**Definition 21.** Let $[T, o]$ be a random rooted finite Family Tree such that $\mathbb{E}[\#V(T)] < \infty$. A random rooted finite Family Tree $[T', o']$ is said to be obtained by **re-rooting to a typical vertex of $[T, o]$** if

$$ \mathbb{P}[[T', o'] \in A] = \frac{1}{\mathbb{E}[\#V(T)]} \mathbb{E} \left[ \sum_{u \in V(T)} 1_A([T, u]) \right], \quad (2.3.4) $$

for every measurable subset $A$ of $\mathcal{T}_*$.
<figure><img src="image_7.png" /></figure>
Chapter 3

Record vertex-shift for random
walk case

In this chapter, we define the record vertex-shift and study its f-graph
called record graph. The record vertex-shift is defined on the networks of
the form (Z, x), where x = (x_n)_{n∈Z is a sequence of integers in {-1, 0, 1, 2, ...}.
The record vertex-shift is defined by the record map defined as follows: for
each integer i, look at the sums Σ_n^{-1}_{k=i} x_k, starting from i, and assign i to
the smallest n > i for which Σ_n^{-1}_{k=i} x_k is non-negative. The randomness of
the network is introduced when we take i.i.d. sequence X = (X_n) with
a common distribution on {-1, 0, 1, ...} such that 0 < P[X_0 = -1] < 1 and
-∞ < E[X_0] < ∞. The f-graph of the record vertex-shift on (Z, X) is called
the record graph. The properties of the record map and the nature of the
random walk influence the distribution of the component of 0 of the record
graph. These properties are studied in Section 3.1. Using these properties,
we show, in Section 3.2, that the component of 0 in the record graph exhibits
phase transitions at 0 when the mean of increment E[X_0] is varied between
-∞ and ∞. These three phases of the component of 0 corresponding to
the region (-∞, 0), at 0, and the region (0, ∞) are namely Typically rooted
Galton-Watson Tree (TGWT), unimodular Eternal Galton-Watson Tree
EGWT and the unimodularised bi-variate Eternal Kesten Tree MEKT
respectively. The Family Tree EGWT was introduced in [7]. We introduce
the TGWT and MEKT in Subsection 3.2. All of these Family Trees are
unimodular.

(In French) Dans ce chapitre, nous définissons le décalage de sommet des records et étudions son f-graphe appelé graphe des records. Le décalage
de sommet des records est défini sur les réseaux de la forme $(\mathbb{Z}, x)$, où $x = (x_n)_{n \in \mathbb{Z}}$ est une suite d'entiers dans $\{-1, 0, 1, 2, \dots\}$. Le décalage de sommet des records est défini par la fonction record définie comme suit : pour chaque entier $i$, on regarde les sommes $\sum_{k=i}^{n-1} x_k$, en partant de $i$, et on assigne $i$ au plus petit $n > i$ pour lequel $\sum_{k=i}^{n-1} x_k$ est non négatif. L'aléa du réseau est introduit lorsque nous prenons une suite i.i.d. $X = (X_n)$ avec une loi commune sur $\{-1, 0, 1, \dots\}$ telle que $0 < \mathbb{P}[X_0 = -1] < 1$ et $-\infty < \mathbb{E}[X_0] < \infty$. Le f-graphe du décalage de sommet des records sur $(\mathbb{Z}, X)$ est appelé le graphe des records. Les propriétés de la fonction record et la nature de la marche aléatoire influencent la distribution de la composante de 0 du graphe des record. Ces propriétés sont étudiées dans la section 3.1. En utilisant ces propriétés, nous montrons, dans la section 3.2, que la composante de 0 dans le graphe des records présente des transitions de phase en 0 lorsque la moyenne des accroissements $\mathbb{E}[X_0]$ varie entre $-\infty$ et $\infty$. Ces trois phases de la composante de 0 correspondant à la région $(-\infty, 0)$, en 0, et à la région $(0, \infty)$ sont respectivement l'arbre généalogique typiquement enraciné de Galton-Watson (TGWT), l'arbre généalogique éternel unimodulaire de Galton-Watson (EGWT) et l'arbre éternel bivarié de Kesten unimodularisé (MEKT). L'arbre généalogique EGWT a été introduit dans [7]. Nous introduisons le TGWT et le MEKT dans la sous-section 3.2. Tous ces arbres généalogiques sont unimodulaires.

## 3.1 Record map

**Notations:** Given an integer valued sequence $x = (x_n)_{n \in \mathbb{Z}}$ with $x_n \ge -1$ for all $n \in \mathbb{Z}$, let

$$y(n, j) := \sum_{l=n}^{j-1} x_l, \qquad (3.1.1)$$

for all integers $n \le j$, with the convention that $\sum_{n}^{n-1} \equiv 0$.

For any integer $i$, the sequence $(-y(n, i))_{n<i}$ is called the sequence of sums in the past of $i$ seen from $i$, whereas, the sequence $(y(i, n))_{n \ge i}$ is called the sums in the future of $i$ seen from $i$. Similarly, the sequence $(n, -y(n, i))_{n<i}$ is called the trajectory in past of $i$ seen from $i$ and the sequence $(n, y(i, n))_{n \ge i}$ is called the trajectory in the future of $i$ seen from $i$.
Let $s^{(i)}$ denote the sequence $(s_n^{(i)})_{n \ge 0}$, where $s_n^{(i)} = y(i-n, i)$ for all $n \ge 0$. Let $s = (s_n)_{n \in \mathbb{Z}}$ be the sequence of locations associated to $x$, where $s_0 = 0$, $s_n = -y(n, 0)$, for all $n < 0$, and $s_n = y(0, n)$ for all $n > 0$. In particular, we have $s_n^{(0)} = -s_{-n}$ for all $n \ge 0$.

**Definition 22.** A sequence of i.i.d. random variables $X = (X_n)_{n \in \mathbb{Z}}$ with $X_n$ taking values in $\mathbb{N} \cup \{-1\}$ for all $n \in \mathbb{Z}$, such that $\mathbb{P}[X_0 = -1] > 0$ and $\mathbb{E}[X_0] < \infty$, are called i.i.d. increments of a skip-free to the left random walk.

We use capital letters to denote random variables. For instance, the sums associated to $X = (X_n)_{n \in \mathbb{Z}}$ are denoted by $S = (S_n)_{n \in \mathbb{Z}}$, and $S^{(i)} = (S_n^{(i)})_{n \ge 0}$ respectively.

*Remark 23.* Since $x_k \ge -1$ for all $k \in \mathbb{Z}$, an obvious observation is that if $y(n, j) = m < 0$ for any two integers $n < j$, then there exist integers $n = i_{-m+1} < i_{-m} < \cdots < i_2 < i_1 = j$ such that $y(i_{l+1}, i_l) = -1$ for all $1 \le l \le -m$.

Define the **record map** $R_x : \mathbb{Z} \to \mathbb{Z}$ to be the function that maps any $n \in \mathbb{Z}$ to

$$R_x(n) = \begin{cases} \inf\{j > n : y(n, j) \ge \max\{y(n, l) : n \le l \le j - 1\}\} & \text{if } \inf \text{ exists} \\ n & \text{otherwise,} \end{cases}$$

with the convention that $y(n, n) = 0$. Equivalently, we obtain

$$R_x(n) = \begin{cases} \inf\{j > n : y(n, j) \ge 0\} & \text{if the infimum exists} \\ n & \text{otherwise.} \end{cases}$$

Denote the $k$-th iterate of the record map by $R_x^k$.

Given a real valued sequence $x = (x_n)_{n \in \mathbb{Z}}$, we consider its associated network $(\mathbb{Z}, x)$ with label $x_i$ on the edge $(i, i+1)$, for all $i \in \mathbb{Z}$ (see [3] for the terminology on networks). For the random variables $X = (X_n)_{n \in \mathbb{Z}}$, we consider the random rooted network $[\mathbb{Z}, 0, X]$ associated to $X$ (with mark $X$ and where the network $(\mathbb{Z}, X)$ is rooted at 0). Note that $[\mathbb{Z}, 0, X]$ is unimodular since $X$ is stationary [3].

Consider networks of the form $(\mathbb{Z}, i, x)$, where $i \in \mathbb{Z}$ is the root and the mark $x = (x_n)_{n \in \mathbb{Z}}$ is a real-valued sequence which assigns label $x_n$ to edge $(n, n+1)$ for each $n \in \mathbb{Z}$. We know that any order preserving graph
isomorphism of $\mathbb{Z}$ is a shift map $T_i$, for some integer $i$, namely $T_i(n) = n + i$, $n \in \mathbb{Z}$. The map $T_i$ acts on a sequence $x = (x_n)_{n \in \mathbb{Z}}$ by $T_ix = (x_{n-i})_{n \in \mathbb{Z}}$. So, any network $(\mathbb{Z}, i, x)$ is root-isomorphic to $(\mathbb{Z}, 0, T_{-i}x)$.

Consider the collection of networks $\{(\mathbb{Z}, x) : x = (x_n)_{n \in \mathbb{Z}}, x_n \in \mathbb{Z}_{\ge -1}\}$. Then, by taking the record map $R$ on this collection and the identity map on the rest of the networks, we obtain a vertex-shift. Indeed, $R$ satisfies the first condition, i.e., $R$ is covariant for all $i$ because

$$
\begin{align*}
R_{T_i x}(k+i) &= \begin{cases} \inf\{j > k + i : \sum_{l=k+i}^{j-1} x_{l-i} \ge 0\} & \text{if infimum is defined,} \\ k + i & \text{otherwise} \end{cases} \\
&= \begin{cases} i + \inf\{j > k : \sum_{l=k}^{j-1} x_l\} & \text{if infimum is defined} \\ i + k & \text{otherwise} \end{cases} \\
&= i + R_x(k).
\end{align*}
$$

The record map $R$ also satisfies the measurability condition since the map $[\mathbb{Z}, i, j, x] \mapsto 1_{R_x(i)=j}$ is a function of $(x_i, x_{i+1}, \dots, x_{j-1})$.

## Properties of the record map

Let $x := (x_n)_{n \in \mathbb{Z}}$ be an arbitrary integer-valued sequence with $x_n \ge -1$, $\forall n \in \mathbb{Z}$, and let $(\mathbb{Z}, x)$ be its associated network with $x_n$ as the mark on the edge $(n, n+1)$ for $n \in \mathbb{Z}$. Define the function $L : \mathbb{R}^{\mathbb{Z}} \times \mathbb{Z} \to \mathbb{Z} \cup \{-\infty\}$ in the following way:

$$
L_x(i) = \begin{cases} \inf\{j < i : y(k,i) \ge 0, \forall j \le k < i\}, & \text{if inf exists;} \\ i & \text{otherwise.} \end{cases} \tag{3.1.2}
$$

The integer $L_x(i)$ is the largest integer (if it exists) up to which the sums in the past of $i$ and seen from $i$ are non-positive, equivalently, $L_x(i)$ is the largest integer up to which the trajectory in the past of $i$ seen from $i$ stays below level 1. Note that $-\infty \le L_x(i) < i$ if and only if the sum $-y(j,i) \le 0$ for all integers $j$ such that $L_x(i) \le j < i$. It could happen that $L_x(i) = i$. This is possible only if $x_{i-1} = -1$.

For the sequence $x$ and any integer $i \in \mathbb{Z}$, the set $D_1(i) := \{j < i : R_x(j) = i\}$ is called the set of children of $i$ and $D(i) := \{j < i : R_x^n(j) = i\}$ for some $n > 0$} is called the set of descendants of $i$. The following lemma shows that the set of descendants of any integer $i$ is the set of integers that lie between $L_x(i)$ and $i$ (including $L_x(i)$ and excluding $i$).
**Lemma 24.** Let $x = (x_n)_{n \in \mathbb{Z}}$ be an integer-valued sequence with $x_n \ge -1, \forall n \in \mathbb{Z}$, and $R$ be the record vertex-shift on the network $(\mathbb{Z}, x)$. The set of descendants of any integer $i$ is given by

$$D(i) = \{j \in \mathbb{Z} : L_x(i) \le j < i\}.$$

*Proof.* We first prove that $\{j \in \mathbb{Z} : L_x(i) \le j < i\} \subset D(i)$. If $L_x(i) = i$, then there is nothing to prove. So, assume that $L_x(i) < i$ (note that $L_x(i)$ can be $-\infty$). Consider any integer $j$ such that $L_x(i) \le j < i$. Since $y(j, i) \ge 0$, we have,

$$j < R_x(j) := \inf\{k > j : y(j, k) \ge 0\} \le i.$$

By iteratively applying the same argument to $R^l(j)$ for each $l > 0$, we find the smallest non-negative integer $m$ such that $R_x^m(j) = i$. Such an $m$ exists as there are only finitely many integers between $j$ and $i$. This implies that $j$ is a descendant of $i$. Therefore, $\{j : L_x(i) \le j < i\} \subseteq D(i)$.

We now prove that $D(i) = \{j \in \mathbb{Z} : L_x(i) \le j < i\}$, i.e., if $-\infty < j < L_x(i)$, then $j$ is not a descendant of $i$. For any $-\infty < j < L_x(i)$, we claim that, either $R_x(j) < L_x(i)$ or $R_x(j) > i$. Assume that the claim is true. If $R_x(j) < L_x(i)$, then by applying the claim again to $R_x(j)$, we obtain that, either $R_x^2(j) < L_x(i)$ or $R_x^2(j) > i$. Iterate this process several times until we find the largest non-negative integer $n$ such that $R_x^n(j) < L_x(i)$. Such an $n$ exists as there are only finitely many integers between $j$ and $L_x(i)$. As $n$ is the largest integer satisfying this condition, by applying the claim to $R_x^n(j)$, we obtain that $R_x^{n+1}(j) > i$. This implies that none of the descendants of $R_x^n(j)$ (including $j$) is a descendant of $i$, which completes the proof. We now prove the last claim. Let $k := L_x(i) - 1$ and let $j$ be as in the claim. Assume that $i \ge R_x(j) \ge L_x(i)$, i.e., $i \ge R_x(j) > k$. Then, $y(k, i) < 0$, by the definition of $L_x(i)$. Since $R_x(j) > k$, we have $y(j, k) \le 0$ (equality holds only if $j = k$). So, $y(j, i) = y(j, k) + y(k, i) < 0$. Therefore, for any $L_x(i) \le m \le i$, $y(j, m) = y(j, i) - y(m, i) < 0$, since $y(m, i) \ge 0$. So, $R_x(j) > i$ and the claim is proved. $\square$

**Lemma 25 (Interval property).** Let $x = (x_n)_{n \in \mathbb{Z}}$ be an integer-valued sequence with $x_n \ge -1, \forall n \in \mathbb{Z}$, and $R$ be the record vertex-shift on the network $(\mathbb{Z}, x)$. If $i \in \mathbb{Z}$ satisfies $R_x(i) > i$, then the set of descendants of $R_x(i)$ contains $\{j : i \le j < R_x(i)\}$. There could be more descendants of $R_x(i)$ that are less than $i$.
*Proof.* By Lemma 24, it is enough to show that $L_x(R_x(i)) \le i$. For any integer $m$ such that $i < m < R_x(i)$, since $y(i, m) < 0$ and $y(i, R_x(i)) \ge 0$, we have

$$y(m, R_x(i)) = y(i, R_x(i)) - y(i, m) \ge 0.$$

Thus, $L_x(R_x(i)) \le i$. □

*Remark 26.* Although, Lemma 24 and Lemma 25 are proved under the assumption that $x = (x_n)_{n \in \mathbb{Z}}$ is an integer-valued sequence satisfying the condition $x_n \ge -1 \forall n \in \mathbb{Z}$, the condition does not play any role in the proofs of these two lemmas. So the statements are indeed valid for any integer-valued sequence.

## Properties of the record map on skip-free to the left random walk

The following two lemmas focus on computing the probability of certain events of skip-free random walks. They are used in the later sections for describing distribution of the record graph associated to skip-free random walks. Although, these computations can be found in [18], we prove them here for the sake of completeness and notational consistency.

We use the following notation in this and the remaining sections thereafter. Let $X = (X_n)_{n \in \mathbb{Z}}$ be i.i.d. increments of a skip-free to the left random walk, and $[\mathbb{Z}, 0, X]$ be its associated network. Let $(S_n)_{n \in \mathbb{Z}}$ be the random walk associated to the increment sequence $X$, i.e., $S_0 = 0$, $S_n = S_0 + \sum_{i=0}^{n-1} X_i$ for $n \ge 1$ and $S_n = S_0 + \sum_{i=n}^{-1} X_i$ for $n \le -1$. Clearly, $(S_n)_{n \ge 0}$ is a skip-free to the left random walk, and $(S_{-n})_{n \ge 0}$ is a skip-free to the right random walk. For any $j \in \mathbb{Z}$, let

$$\eta_j := \begin{cases} \inf\{n \ge 0 : S_n = j\} & \text{if } S_n = j \text{ for some } n \ge 0 \\ \infty & \text{otherwise.} \end{cases} \qquad (3.1.3)$$

For an event $A$, let $\mathbb{P}_k[A]$ denote the probability of the event $A$ when the random walk starts at $k \in \mathbb{Z}$. Let $\mathbb{P} := \mathbb{P}_0$, and $c := \mathbb{P}[\eta_{-1} < \infty]$.

**Lemma 27.** For $0 \le j \le k$, $\mathbb{P}[\eta_{j-k} < \infty] = \mathbb{P}_k[\eta_j < \infty] = c^{k-j}$.

*Proof.* The first equality (in the statement) is obvious since the probability is invariant to shift of the starting point of the random walk. The second
equality follows because of the skip free property which prohibits the random walk from taking jumps smaller than $-1$. We prove it by induction on $k-j$. If $j=k$, then $\mathbb{P}_j[\eta_j < \infty] = 1$. So, assume that $0 \le j < k$. By induction, we have $\mathbb{P}_{k'}[\eta_{j'} < \infty] = c^{k'-j'}$ for all $0 \le j' \le k'$ such that $k' - j' < k - j$. Then,

$$ \mathbb{P}_k[\eta_j < \infty] = \mathbb{P}_k[\eta_{k-1} < \infty] \mathbb{P}_{k-1}[\eta_j < \infty] = \mathbb{P}[\eta_{-1} < \infty] c^{k-1-j} = c^{k-j}. $$

The second equality follows by applying the inductive statement to $k' = k-1$, and $j' = j$. $\square$

Let $\tau := \inf\{n > 0 : S_n \ge 0\}$, with $\tau = \infty$ if $S_n < 0$ $\forall n > 0$, be the weak upper record (epoch), $S_\tau$ be the weak upper record height, and $X_{\tau-1}$ be its last increment (both are defined to be arbitrary when $\tau = \infty$).

**Lemma 28 ([8]).** For all integers $j, k$ such that $0 \le j \le k$,

$$ \mathbb{P}[\tau < \infty, S_{\tau} = j, X_{\tau-1} = k] = \mathbb{P}[X_0 = k] c^{k-j}. $$

*Proof.* Note the equality of the following events:

$$ \{S_{\tau} = X_{\tau-1}, \tau < \infty\} = \{\tau = 1\} = \{S_1 \ge 0\}. $$

Therefore, for $0 \le j = k$, we have $\mathbb{P}[S_\tau = j, X_{\tau-1} = j, \tau < \infty] = \mathbb{P}[S_1 = j]$. So, for $0 \le j < k$,

$$ \begin{aligned} \mathbb{P}[\tau < \infty, S_{\tau} = j, X_{\tau-1} = k] &= \sum_{n=2}^{\infty} \mathbb{P}[\tau = n, S_n = j, X_{n-1} = k] \\ &= \sum_{n=2}^{\infty} \mathbb{P}[S_1 < 0, \dots, S_{n-1} < 0, S_n = j, S_n - S_{n-1} = k]. \end{aligned} $$

The sum in the first equation starts from $n=2$ since we assumed that $j < k$ ($\{\tau = 1\}$ occurs if and only $j=k$ which is already covered). By the duality principle (also known as reflection principle), the last expression is equal to

$$ \sum_{n=2}^{\infty} \mathbb{P}[S_n - S_{n-1} < 0, S_n - S_{n-2} < 0, \dots, S_n - S_1 < 0, S_n = j, S_n - (S_n - S_1) = k]. $$
So, we obtain:

$$
\begin{align*}
\mathbb{P}[\tau < \infty, S_{\tau} = j, X_{\tau-1} = k] &= \sum_{n=2}^{\infty} \mathbb{P}[S_n = j, S_{n-1} > j, S_{n-2} > j, \dots, S_1 > j, S_1 = k] \\
&= \sum_{n=2}^{\infty} \mathbb{P}[S_1 = k] \mathbb{P}_k[S_1 > j, \dots, S_{n-2} > j, S_{n-1} = j] \\
&= \mathbb{P}[S_1 = k] \sum_{n=2}^{\infty} \mathbb{P}_k[\eta_j = n-1] \\
&= \mathbb{P}[S_1 = k] \mathbb{P}_k[0 < \eta_j < \infty] \\
&= \mathbb{P}[S_1 = k] c^{k-j} = \mathbb{P}[X_0 = k] c^{k-j}.
\end{align*}
$$

The second equation follows by the Markov property. The second to last equation follows from Lemma 27 and the fact that $\mathbb{P}[\eta_{j-k} = 0] = \delta_j(k)$, where $\delta$ is the Dirac function. $\square$

Remark 29. If the random walk has positive drift, i.e., $0 < \mathbb{E}X_0 < \infty$, then $S_n \to \infty$ a.s. as $n \to \infty$. So, $\tau < \infty$ a.s.. Therefore, $\mathbb{P}[\tau < \infty, S_\tau = j, X_{\tau-1} = k] = \mathbb{P}[S_\tau = j, X_{\tau-1} = k]$ for $0 \le j \le k$.

If the random walk has negative drift, i.e., $\mathbb{E}[X_0] < 0$, then $S_n \to -\infty$ a.s. as $n \to \infty$. Therefore, $c=1$, which implies that $\mathbb{P}[\tau < \infty, S_\tau = j, X_{\tau-1} = k] = \mathbb{P}[X_0 = k]$, and

$$
\mathbb{P}[\tau < \infty, X_{\tau-1} = k] = \sum_{j=0}^{k} \mathbb{P}[\tau < \infty, S_{\tau} = j, X_{\tau-1} = k] = (k+1)\mathbb{P}[X_0 = k].
$$

Let us assume that $\mathbb{E}[X_0] > 0$. The following lemma shows that the random walk conditioned to hit $-1$ is also a random walk with a different increment distribution. Recall that $\eta_{-1}$ is the first time the random walk $(S_n)_{n \ge 0}$ hits $-1$ (see Eq. (3.1.3)). Let $\bar{S}$ has the conditional distribution of $(S_{n \wedge \eta_{-1}})_{n \ge 0}$ given that $\eta_{-1} < \infty$. Let $p_k := \mathbb{P}[X_0 = k], \forall k \ge -1$. Observe that $\sum_{k=-1}^{\infty} p_k c^{k+1} = c$, since the sum on the left can be written as

$$
\begin{align*}
\sum_{k=-1}^{\infty} p_k c^{k+1} &= \sum_{k=-1}^{\infty} \mathbb{P}[X_0 = k] c^{k+1} \\
&= \sum_{k=-1}^{\infty} \mathbb{P}[X_0 = k] \mathbb{P}_k[\eta_{-1} < \infty] \\
&= \mathbb{P}_0[\eta_{-1} < \infty] = c.
\end{align*}
$$
Therefore, we have

$$ \sum_{k=-1}^{\infty} p_k c^k = 1. \qquad (3.1.4) $$

Let $\hat{X} = (\hat{X}_n)_{n \ge 0}$ be i.i.d. sequence of a skip-free to the left random walk whose common distribution is given by:

$$ \mathbb{P}[\hat{X}_0 = k] = \mathbb{P}[X_0 = k]c^k = p_k c^k, \forall k \ge -1, \qquad (3.1.5) $$

which is a valid distribution by Eq. (3.1.4). Let $(\hat{S}_n)_{n \ge 0}$ be the random walk whose increment sequence is $\hat{X}$, i.e., $\hat{S}_n = \sum_{k=0}^{n-1} \hat{X}_k$ for all $k \ge 0$, and $\hat{S} = (\hat{S}_{n \wedge \hat{\eta}_{-1}})_{n \ge 0}$ be the stopped random walk.

**Remark 30.** In fact, the process $(\hat{S}_n)_{n \ge 0}$ is the Doob $h$-transform of $p$, where $p$ is the distribution of $X_0$ and $h$ is the harmonic function defined on $\mathbb{Z}_{\ge 0}$ by $h(i) = \mathbb{P}_i[\eta_{-1} < \infty]$ for all $i \ge 0$.

**Lemma 31.** Let $\mathbb{E}[X_0] > 0$. Then the process $\bar{S}$ has the same distribution as the stopped skip-free to the left random walk $\hat{S}$.

*Proof.* Let $(x_0, x_1, \dots, x_n)$ be the first $n+1$ increments of a sample of the process with $x_k \ge -1, \forall k \le n, x_1 + \dots + x_m \ge 0, \forall m < n$, and $x_1 + \dots + x_n \ge -1$. Then, for all such $n$ and $x$,

$$ \begin{aligned} & \mathbb{P}[S_0 = 0, S_1 = x_1, S_2 - S_1 = x_2, \dots, S_{(n \wedge \eta_{-1})} - S_{(n \wedge \eta_{-1} - 1)} = x_n, \eta_{-1} \ge n | \eta_{-1} < \infty] \\ &= \frac{\mathbb{P}[S_1 = x_1] \mathbb{P}_{x_1}[S_1 = x_2, S_2 - S_1 = x_3, \dots, S_{n-1} - S_{n-2} = x_n, \eta_{-1} < \infty]}{\mathbb{P}[\eta_{-1} < \infty]} \\ &= \frac{(\prod_{i=1}^n \mathbb{P}[S_1 = x_i]) \mathbb{P}_{x_1+\dots+x_n}[\eta_{-1} < \infty]}{\mathbb{P}[\eta_{-1} < \infty]} = \frac{(\prod_{i=1}^n \mathbb{P}[S_1 = x_i]) c^{x_1+x_2+\dots+x_{n+1}}}{c} \\ &= \prod_{i=1}^n (\mathbb{P}[X_0 = x_i] c^{x_i}) \\ &= \mathbb{P}[\hat{S}_1 = x_1, \hat{S}_2 - \hat{S}_1 = x_2, \dots, \hat{S}_{(n \wedge \eta_{-1})} - \hat{S}_{(n \wedge \eta_{-1} - 1)} = x_n, \hat{\eta}_{-1} \ge n]. \end{aligned} $$

Thus, the conditioned random walk is a stopped random walk, stopped at the stopping time $\hat{\eta}_{-1}$, whose increments are distributed as $\mathbb{P}[S_1 = j]c^j, \forall j \ge -1$. $\square$

We now show that the random walk $(\hat{S}_n)_{n \ge 0}$ has negative drift.
**Lemma 32.** Assume $\mathbb{E}[X_0] > 0$. Then the mean of $\hat{X}_0$ is negative.

*Proof.* Consider the function $\phi(x) = \sum_{k=0}^{\infty} (k+1)x^k p_k - 1$ on the interval $[0, 1]$. We have

$$ \phi(c) = \sum_{k=0}^{\infty} (k+1)c^k p_k - 1 = \sum_{k=0}^{\infty} kc^k p_k + \left( \sum_{k=0}^{\infty} c^k p_k \right) - 1 \\ = \sum_{k=0}^{\infty} kc^k p_k + 1 - \frac{p_{-1}}{c} - 1 = \sum_{k=-1}^{\infty} kc^k p_k = \mathbb{E}[\hat{X}]. $$

The function $\phi$ has the following properties on $[0, 1]$:

* $\phi(0) < 0$: Since $\phi(0) = p_0 - 1 < 0$.

* $\phi(1) > 0$: Since $\phi(1) = \sum_{k=0}^{\infty} (k+1)p_k - 1 = \sum_{k=0}^{\infty} k p_k + 1 - p_{-1} - 1 = \mathbb{E}[X] > 0$.

* $\phi$ is strictly increasing since $\phi'(x) > 0, \forall x \in (0, 1)$.

Therefore, there exists a unique $c' \in (0, 1)$ such that $\phi(c') = 0$. The proof is complete if we show that $c < c'$, as this implies that $\phi(c) < \phi(c') = 0$ by monotonicity of $\phi$, and the fact that $\phi(c) = \mathbb{E}[\hat{X}]$.

We now show that $c < c'$. Consider the function $\psi(x) = \sum_{k=0}^{\infty} x^{k+1} p_k + p_{-1} - x$ on the interval $[0, 1]$. Observe that $\psi'(x) = \sum_{k=0}^{\infty} (k+1)x^k p_k - 1 = \phi(x)$,

$$ \psi(c) = \sum_{k=0}^{\infty} c^{k+1} p_k + p_{-1} - c = c \left( \sum_{k=0}^{\infty} c^k p_k + \frac{p_{-1}}{c} - 1 \right) = 0, $$

and $\psi(1) = \sum_{k=0}^{\infty} p_k + p_{-1} - 1 = 0$. As $\psi(c) = \psi(1) = 0$, there exists a $d \in (c, 1)$ such that $\psi'(d) = 0$. Since $\phi(d) = \psi'(d) = 0$, we have $d = c'$. Thus, $c < c'$. $\square$

## Relation between RLS order and the order on integers

Let $X = (X_n)_{n \in \mathbb{Z}}$ be the i.i.d. increments of a skip-free to the left random walk (see Def. 22) with $\mathbb{E}[X_0] = 0$ and let $[\mathbb{Z}, 0, X]$ be its associated network. Let $[\mathbf{T}, 0]$ denote the connected component of 0 (rooted at 0) in the $\mathbf{R}$-graph (see notations of Chapter 2) of the network $[\mathbb{Z}, 0, X]$. Since the vertices of $\mathbf{T}$ are integers, we can order the children of every vertex using the total order $<$ of $\mathbb{Z}$. Then, the RLS order $<$ gives a total order on the vertices of $\mathbf{T}$. Thus, we have two total orders $<$ and $<$ on the vertices of $\mathbf{T}$. The former
is deterministic whereas the latter is random (it depends on the realization of $X$). Using the interval property (Lemma 25) of the record vertex-shift, we show in the following lemma that these two orders are in fact equivalent in the following sense:

**Lemma 33.** Let $x = (x_n)_{n \in \mathbb{Z}}$ be a real-valued sequence, $[\mathbb{Z}, 0, x]$ be its associated network. Let $i, j$ be two integers having a smallest common ancestor $w$, with $w = R^m(i) = R^k(j)$, where $m$ and $k$ are the smallest non-negative integers satisfying this property. Then, $i < j$ (with respect to the order on $\mathbb{Z}$) if and only if $i < j$.

*Proof.* ($i < j \implies i < j$): Since $R^n(i)$ is an increasing sequence for $0 < n < m$, there exists a largest $n_0 \le m$ such that $R^{n_0}(i) \le j$. If $R^{n_0}(i) = j$, then $i < j$, which is the desired relation. So, let us assume that $R^{n_0}(i) < j$ and $R^{n_0+1}(i) > j$. By Lemma 25, both $R^{n_0}(i)$ and $j$ are descendants of $R^{n_0+1}(i)$, which implies that $R^{n_0+1}(i) = w$. Hence, $R^{m_0}(j) = R^{n_0+1}(i) = w$ for some $m_0 > 0$. Since $R^{n_0}(i) < j \le R^{m_0-1}(j)$, we have $R^{n_0}(i) < R^{m_0-1}(j)$, and by Remark 5, we have $i < j$.

($i < j \implies i < j$): The case where $j$ is an ancestor of $i$ is trivial. So, let us assume that $j$ is not an ancestor of $i$. Then we have $k > 0$, and $R^{m-1}(i) < R^{k-1}(j)$. Since $R^{m-1}(i)$ is not a descendant of $R^{k-1}(j)$, but $j$ is a descendant of $R^{k-1}(j)$, by Lemma 24, we have $i < R^{m-1}(i) < L_x(R^{k-1}(j)) \le j$. $\square$

**Relation between offspring count and increment in the record graph**

Let $T$ be an ordered Family Tree, $o \in V(T)$, and $u_n < u_{n-1} < \dots < u_1$ be the children of $o$ (totally ordered by $<$). Define the order of any child $u_j$ among its siblings as $j$. That is, $u_j$ is the $j$-th child of $o$. Recall the notation $y(j, k) := \sum_{l=j}^{k-1} x_l$ for integers $j < k$ and for a given sequence $x = (x_n)_{n \in \mathbb{Z}}$.

The skip-free property of the increments of the random walk gives us the following lemma.

**Lemma 34.** Let $x = (x_k)_{k \in \mathbb{Z}}$ be a sequence where $x_k \in \mathbb{N} \cup \{0, -1\}$. Let $[\mathbb{Z}, 0, x]$ be the associated network of $x$, and $T$ be the $R$-graph of $[\mathbb{Z}, 0, x]$. Let $i$ be an integer such that $L_x(i) > -\infty$. Then,

1. The number of children $d_1(i)$ of $i$ in $T$ is given by $d_1(i) = x_{i-1} + 1$.
2. Let $d_1(i) = n > 0$ and $i_n < i_{n-1} < \cdots < i_1$ be the positions on $\mathbb{Z}$ of the $n$ children of $i$. Then, the position $i_m$ of the $m$-th child satisfies the relation $m = x_{i-1} + 1 - y(i_m, i)$.

3. Let $d_1(i) = n > 0$, and $m \in \{1, 2, \dots, n\}$. Then, an integer $i' < i$ is the $m$-th child of $i$ if and only if $i'$ is the largest integer among $\{L_x(i), \dots, i-1\}$ that satisfies $y(i', i) = x_{i-1} + 1 - m$.

*Proof.* If $x_{i-1} = -1$, then $L_x(i) = i$. So, by Lemma 24, $i$ has no descendant. Then, (1.) holds as $d_1(i) = x_{i-1} + 1 = 0$, whereas the other statements are empty.

So, let us assume that $x_{i-1} \ge 0$. Clearly $i-1$ is then a child of $i$ as $i$ is the record of $i-1$. Therefore, $d_1(i) \ge 1$. We show below that the sum of increments between any two successive children is $-1$.

Let $i_n < i_{n-1} < \cdots < i_1$ be the positions on $\mathbb{Z}$ of the children of $i$, with $i_1 = i-1$. Consider a child $i_m$ with $m < n$. If $i_{m+1} = i_m - 1$, then $x_{i_{m-1}} = -1$. Therefore, $y(i_{m+1}, i_m) = -1$. Consider now the case where $i_{m+1} < i_m - 1$, and let $i'$ be an integer with $i_{m+1} < i' < i_m$. As $i'$ is not a child of $i$, and $i_m$ is a child of $i$, by Lemma 25, we have $R_x(i') \le i_m$, and there exists a smallest $k > 0$ such that $R_x^k(i') = i_m$. Therefore, $y(i', i_m) = \sum_{l=0}^{k-1} y(R_x^l(i'), R_x^{l+1}(i')) \ge 0$.

In particular, $y(i_{m+1}+1, i_m) \ge 0$. But, $y(i_{m+1}, i_m) < 0$, because the record of $i_{m+1}$ is $i$ (not $i_m$). Therefore, the only possibility is that $x_{i_{m+1}} = -1$. This also implies that $y(i_{m+1} + 1, i_m) = 0$. Indeed, if $y(i_{m+1} + 1, i_m) \ge 1$, then $y(i_{m+1}, i_m) = x_{i_{m+1}} + y(i_{m+1} + 1, i_m) = -1 + y(i_{m+1} + 1, i_m) \ge 0$, which gives a contradiction that $i_m$ is the record of $i_{m+1}$. Hence, $y(i_{m+1}, i_m) = x_{i_{m+1}} + y(i_{m+1} + 1, i_m) = -1$. Thus, we have shown that the sum of increments between two successive children is $-1$. We now use this to prove the three statements of the lemma.

The proof of the second statement follows because, for any child $i_m$ of $i$, we have

$$y(i_m, i) = y(i_m, i_1) + x_{i-1} = y(i_m, i_{m-1}) + \cdots + y(i_2, i_1) + x_{i-1} = -(m-1) + x_{i-1}. \tag{3.1.6}$$

We now prove the third statement. Since $i_m$ is a child of $i$, $y(i_m, i) \ge 0$, $\forall 1 \le m \le n$. Further, for any $i_m < i' \le i-1$, we have $y(i', i) = y(i', i_j) + y(i_j, i)$, with $i_j \ge i'$ being the unique smallest integer which is a child of $i$. Such an $i_j$ always exists since $i-1$ is a child of $i$. Moreover, we have $j < m$. Since
$y(i', i_j) \ge 0$, we have

$$y(i', i) = y(i', i_j) + x_{i-1} + 1 - j \ge x_{i-1} + 1 - j > x_{i-1} + 1 - m,$$

where we used Eq. (3.1.6) to get the first equality. This proves the forward implication of the third statement: if $h$ is the $m$-th child of $i$ then $h < i$ is the largest integer that satisfies $y(h, i) = x_{i-1} + 1 - m$.

As for the backward implication of the third statement, if $i' < i$ is the largest integer satisfying $y(i', i) = x_{i-1} + 1 - m \ge 0$ for some $m \in \{1, 2, \dots, n\}$, then $y(i', j) = y(i', i) - y(j, i) < 0$, for all $i' < j \le i - 1$. So, $i'$ is a child of $i$. But, by Eq. (3.1.6), there is only one child that satisfies this condition, namely, the $m$-th child of $i$. This proves the third statement.

We now show that $y(L_x(i), i) = 0$. Indeed, from the definition of $L_x(i)$, it follows that $y(L_x(i) - 1, i) = x_{L_x(i)-1} + y(L_x(i), i) < 0$. But $y(L_x(i), i) \ge 0$, implying that $x_{L_x(i)-1} = -1$ (the only possibility for $x_{L_x(i)-1}$). Hence, $y(L_x(i), i) = 0$. This implies that $i_n = L_x(i)$ since no integer smaller than $L_x(i)$ can be a descendant of $i$ by Lemma 24. To prove the first statement, observe that

$$y(i_n, i) = x_{i-1} + \sum_{k=1}^{n-1} y(i_k, i_{k+1}) = x_{i-1} - (n-1).$$

Therefore, $y(i_n, i) = 0 = x_{i-1} + 1 - n$ which gives $d_1(i) = n = x_{i-1} + 1$, proving the first statement. $\square$

*Remark 35.* From the last part of the proof of Lemma 34, it follows that, if $L_x(i) > -\infty$, then $L_x(i)$ is the smallest child of $i$.

## The type function and its properties

Let $x = (x_n)_{n \in \mathbb{Z}}$ be an integer-valued sequence with $x_n \ge -1$ for all $n \in \mathbb{Z}$, $[\mathbb{Z}, 0, x]$ be the rooted network associated to $x$, and $T$ be the record graph of the network $(\mathbb{Z}, x)$. For any integer $i$, denote the number of children of $i$ in $T$ by $d_1(i, T)$.

The **type function** associated to $x$ is the map $t: \mathbb{Z} \to \mathbb{Z}$ that assigns to each integer $i \in \mathbb{Z}$ the integer $t(i) \in \{-1, 0, 1, \dots\}$ defined as

$$t(i) := t_x(i) = \inf\{n \ge -1 : y(m, i) = n \text{ for some } m < i\}. \quad (3.1.7)$$
The integer $t(i)$ is called the **type** of $i$. Note that the type function is a deterministic function of $x$. The type $t_x(i)$ of an integer $i$ can also be written

$$t_x(i) = \inf\{y(m, i) \lor -1 : m < i\}, \quad (3.1.8)$$

where $\lor$ is the max function.

The type function is analogous to the Loynes construction [5].

We show, in the later sections, that when $\mathbb{E}[X_0] > 0$ the record graph together with the type function encodes the trajectory of the random walk. This allows one to move back and forth between a trajectory of the random walk and its record graph together with the type function.

**Remark 36.** Let $X$ be the i.i.d. increments of a skip-free to the left random walk. Then, for any integer $i \in \mathbb{Z}$, the sequence $S^{(i)} = (S_m^{(i)})_{m \ge 0} := (\sum_{k=i-m}^{i-1} X_k)_{m \ge 0}$ is a skip-free to the left random walk. So, it can only take negative steps of size 1 at a time (i.e., $S_m^{(i)} < 0$ for some $m \ge 1$ if and only if $S_j^{(i)} = -1$ for some $j \le m$). The type of vertex $i$ is $-1$ if and only if $S_m^{(i)} = -1$ for some $m \ge 1$, and it is equal to $n \ge 0$ if and only if $\min_{m \ge 1} \{S_m^{(i)}\} = n$, i.e., the random walk $(S_m^{(i)})_{m \ge 1}$ reaches $n$ but stays above $n-1$. In particular, $t(i)$ is well-defined for all $i \in \mathbb{Z}$.

Define the function $l_x : \mathbb{Z} \to \mathbb{Z}$ that maps an integer $i$ to

$$l(i) := l_x(i) = \sup\{m < i : y(m, i) = t_x(i)\}. \quad (3.1.9)$$

Recall the function $L$ defined in Eq. (3.1.2). This function is related to the function $l$ in the following way. First note that for every $i \in \mathbb{Z}$, we have $-\infty < l(i) < i$ since $t_x(i) = \min\{y(m, i) \lor -1 : m < i\}$ and $l(i)$ is the largest $m$ for which $y(m, i)$ attains $t_x(i)$, when $m$ is varied in $\mathbb{Z}_{<i}$. If $t_x(i) = -1$, then $l(i) = L(i) - 1$. For any integer $i$, $t_x(i) \ge 0$ if and only if $L(i) = -\infty$.

**Lemma 37.** For any integer $i$, we have the following dichotomy:

* if $t_x(i) = -1$, then $L(i)$ is the smallest child of $i$ in $T$,

* if $t_x(i) \ge 0$, then $l(i)$ is the smallest child of $i$ in $T$.

*Proof.* If $t_x(i) = -1$, then $L(i) > -\infty$. So, by Remark 35, $L(i)$ is the smallest child of $i$ in $T$.

So, let us assume that $t_x(i) \ge 0$. In this case, $i$ is the record of $l(i)$, i.e., $i = R(l(i))$. This follows because, for any $l(i) < m < i$, we have $y(m, i) >$
$t_x(i)$ by the definition of $t_x(i)$ and $l(i)$. Since $y(l(i), i) = t_x(i)$, we have $y(l(i), m) = y(l(i), i) - y(m, i) < 0$. Thus, $R(l(i)) = i$. Further, if $t_x(i) \ge 0$, then $y(m, l(i)) \ge 0$ for all $m < l(i)$. Indeed, for $m < l(i)$, since $y(m, i) \ge t_x(i)$, we have $y(m, l(i)) = y(m, i) - y(l(i), i) \ge t_x(i) - t_x(i) = 0$. So, $R(m) \le l(i)$ for all $m < l(i)$. This implies that $l(i)$ is the smallest among the children of $i$ as none of the integers smaller than $l(i)$ are children of $i$. $\square$

The following lemma describes the relation between the number of chil-
dren of any integer $i$, its associated increment $x_i$ and its type $t_x(i)$ when
$t_x(i) \ge 0$. When $t_x(i) = -1$, the type does not play any role in determining
this relation.

**Lemma 38.** Let $i \in \mathbb{Z}$ be an integer. We have the following dichotomy:

* If $t_x(i) = -1$, then the number of children of $i$ in $T$ is given by $d_1(i, T) = x_{i-1} + 1$.

* If $t_x(i) \ge 0$, then the number of children of $i$ in $T$ is given by $d_1(i, T) = x_{i-1} + 1 - t_x(i)$.

<figure><img src="image_8.png" /><figcaption>Figure 3.1: The trajectories of $x = (x_n)_{n \in \mathbb{Z}}$ (in black) and $\bar{x} = (\bar{x}_n)_{n \in \mathbb{Z}}$ (in blue). The children of $i$ in $T$ are drawn in red, and the additional children of $i$ in $\bar{T}$ are drawn in green. See Lemma 38.</figcaption></figure>
*Proof.* If $t_x(i) = -1$, then $L_x(i) > -\infty$ (see the paragraph above Lemma 37), which is the condition needed to apply Lemma 34. The first part of the statement follows from part 1 of Lemma 34.

We now prove the second part of the statement. To follow the proof, see Fig. 3.1. Define a new sequence $\bar{x} = (\bar{x}_n)_{n \in \mathbb{Z}}$ by

$$ \bar{x}_n = \begin{cases} -1, & \forall n < l_x(i) \\ x_n, & \forall n \ge l_x(i). \end{cases} $$

Let $\bar{y}(j, k) = \sum_{l=j}^{k-1} \bar{x}_l$ for all integers $j < k$. Then, $y(j, k) = \bar{y}(j, k)$ for all $l_x(i) \le j < k$. Thus, we have

$$ \bar{y}(k, i) = y(k, i) \ge t_x(i) > 0 \quad \forall l_x(i) \le k < i, \quad (3.1.10) $$

and

$$ \bar{y}(k, i) = k - l_x(i) + t_x(i) \quad \forall k < l_x(i). $$

Therefore, (see Eq. (3.1.2) for the definition of $L$)

$$ L_{\bar{x}}(i) = l_x(i) - t_x(i) > -\infty. \quad (3.1.11) $$

Let $\bar{T}$ denote the record graph of the network $(\mathbb{Z}, \bar{x})$, $D_1(i, \bar{T})$ denote the set of children of $i$ in $\bar{T}$ and let $d_1(i, \bar{T}) = \#D_1(i, \bar{T})$. Then, by the first part of Lemma 34, we obtain that $d_1(i, \bar{T}) = \bar{x}_{i-1} + 1$. Since $l_x(i) < i$, we have $x_{i-1} = \bar{x}_{i-1}$ which implies that $d_1(i, \bar{T}) = x_{i-1} + 1$.

Note that $\bar{y}(l_x(i), i) = t_x(i)$ and $\bar{y}(j, i) > t_x(i)$ for all $l_x(i) < j < i$. Therefore, by the third part of Lemma 34, $l_x(i)$ is the $x_{i-1} + 1 - t_x(i)$-th child of $i$ in $\bar{T}$. Since $\bar{x}_j = -1$ for all $j < l_x(i)$, by (3) of Lemma 34, we obtain that

$$ \{j \in \mathbb{Z} : L_{\bar{x}}(i) \le j < l_x(i)\} \subseteq D_1(i, \bar{T}). $$

By Eq. (3.1.11), $\#\{j \in \mathbb{Z} : L_{\bar{x}}(i) \le j < l_x(i)\} = l_x(i) - L_{\bar{x}}(i) = t_x(i)$. Observe that $D_1(i, \bar{T}) \cap \{j \in \mathbb{Z} : l_x(i) \le j < i\} = D_1(i, T)$ by Eq. (3.1.10). Finally, Lemma 37 implies that $l_x(i)$ is the smallest child of $i$ in $T$. Thus, we have

$$ D_1(i, T) = D_1(i, \bar{T}) \setminus \{j \in \mathbb{Z} : L_{\bar{x}} \le j < l_x(i)\}, $$

which gives

$$ d_1(i, T) = d_1(i, \bar{T}) - t_x(i) = x_{i-1} + 1 - t_x(i). $$

□
## 3.2 Classification theorem and phase transitions

Recall the foil classification theorem 14. It states that a.s. any unimodular Family Tree belongs to either class $\mathcal{F}/\mathcal{F}$ or class $\mathcal{I}/\mathcal{F}$ or class $\mathcal{I}/\mathcal{I}$. These three classes are characterized by the following distinctive properties. Every Family Tree of class $\mathcal{F}/\mathcal{F}$ has finitely many vertices. Every Family Tree of class $\mathcal{I}/\mathcal{I}$ is eternal, one-ended and all of its vertices have finitely many descendants. In contrast, every Family Tree of class $\mathcal{I}/\mathcal{F}$ is eternal, two ended, and all the vertices that lie on its unique bi-infinite path have in-finitely many descendants and all the remaining vertices have finitely many descendants. In addition, if a unimodular Family Tree is of class $\mathcal{I}/\mathcal{F}$ a.s., then it is obtained by the operation called typically rooted joining of a stationary sequence of finite Family Trees.

In Subsection 3.2, we will use the typically rooted joining construction to define a unimodular Family Tree of class $\mathcal{I}/\mathcal{F}$.

We first describe the class (according to the classification theorem) of the connected component of 0 in the $R$-graph of $[\mathbb{Z}, 0, X]$, where $X = (X_n)_{n \in \mathbb{Z}}$ are the i.i.d. increments of a skip-free to the left random walk (see Def. 22). Let $(S_n)_{n \in \mathbb{Z}}$ be the two-sided random walk associated to $X$, where $S_0 = 0$, $S_n = \sum_{k=0}^{n-1} X_k$ for $n > 0$, and $S_n = \sum_{k=n}^{-1} -X_k$ for $n < 0$. Let $\mathbb{Z}^R$ be the record graph of $(\mathbb{Z}, X)$ and $\mathbf{T} = \mathbb{Z}^R(0)$ be the connected component of 0 in $\mathbb{Z}^R$. Since $[\mathbb{Z}, 0, X]$ is unimodular, $[\mathbf{T}, 0]$ is a unimodular Family Tree (see Lemma 16 taken from [7]).

The phase transitions occur not only for the i.i.d. sequence of random variables that have the support in $\mathbb{Z}_{\ge -1}$, but also for more general stationary and ergodic integer-valued sequence of random variables (See Theorem 119). In the i.i.d. case, the component of 0 in the record graph exhibits three phases ($\mathcal{F}/\mathcal{F}$, $\mathcal{I}/\mathcal{I}$ and $\mathcal{I}/\mathcal{F}$ resp.) corresponding to the conditions $\mathbb{E}[X_0] < 0$, $\mathbb{E}[X_0] = 0$ and $\mathbb{E}[X_0] > 0$ respectively. But for more general stationary and ergodic case, one can construct examples for which there are only two phases: $\mathcal{F}/\mathcal{F}$ when $\mathbb{E}[X_0] < 0$ and $\mathcal{I}/\mathcal{F}$ when $\mathbb{E}[X_0] \ge 0$ (see Example 120 and Theorem 119).

**Proposition 39.** If $\mathbb{E}[X_0] < 0$, then the unimodular Family Tree $[\mathbf{T}, 0]$ is of class $\mathcal{F}/\mathcal{F}$.

*Proof.* Since $\mathbb{E}[X_0] < 0$, the random walk $(S_n)_{n \ge 0}$ drifts to $-\infty$, i.e., $S_n \to$
$-\infty$ a.s.. So, a.s., 0 has finitely many ancestors in $\mathbf{T}$. However, the random walk $(S_n)_{n \ge 0}$ drifts to $\infty$. So, $L_X(0) > -\infty$. Therefore, by Lemma 24, 0 has finitely many descendants. Thus, $[\mathbf{T}, 0]$ is of class $\mathcal{F}/\mathcal{F}$. $\square$

**Proposition 40.** If $\mathbb{E}[X_0] = 0$, then the record graph $\mathbb{Z}^R$ is connected and the unimodular Family Tree $[\mathbf{T}, 0]$ is of class $\mathcal{I}/\mathcal{I}$.

*Proof.* Since $\mathbb{E}[|X_n|] < \infty$, by the Chung-Fuchs theorem [15], the random walk starting at 0 with increments $(X_n)_{n \ge i}$ is recurrent for any $i \in \mathbb{Z}$. This implies that for any $i \in \mathbb{Z}$, almost surely, the sequence $(R_X^n(i))_{n \in \mathbb{N}}$ (of higher order record epochs of $i$) is strictly increasing, i.e., $R_X^n(i) \neq R_X^n(i-1)$, $\forall n \ge 1$.

Let $A_i$ be the event that the integer $i$ is in the connected component of 0 in the $R$-graph. We claim that the event $A = \cap_{i \in \mathbb{Z}} A_i$ occurs with probability 1.

Let $i < 0$ (the proof for $i > 0$ is obtained by interchanging $i$ and 0). Since the sequence $(R_X^n(i))_{n \in \mathbb{Z}}$ is strictly increasing a.s., there exists a smallest (random) integer $k > 0$ such that $R_X^{k-1}(i) < 0 \le R_X^k(i)$ a.s.. By Lemma 25 (applied to $R_X^{k-1}(i)$), 0 is a descendant of $R_X^k(i)$ a.s.. Thus, a.s., 0 and $i$ are in the same connected component. The claim follows since $i$ is arbitrary.

The above argument also implies that, a.s., $[\mathbf{T}, 0]$ is an EFT, and Lemma 16 implies that it is unimodular. We prove that $[\mathbf{T}, 0]$ is of class $\mathcal{I}/\mathcal{I}$ by showing that the descendant tree of every vertex of $\mathbf{T}$ is finite. For any integer $i$, the random walk starting at 0 with increments $(-X_{(i-1-n)})_{n \ge 0}$ is recurrent by the Chung-Fuchs theorem. Therefore, $L_X(i) > -\infty$ a.s., implying that the set of descendants of $i$ is a.s. finite by Part 1 of Lemma 34. This completes the proof. $\square$

**Proposition 41.** If $0 < \mathbb{E}[X_0] < \infty$, then the record graph $\mathbb{Z}^R$ is connected and the unimodular Family Tree $[\mathbf{T}, 0]$ is of class $\mathcal{I}/\mathcal{F}$.

*Proof.* We show that there exists a vertex of $\mathbf{T}$ that has infinitely many descendants, which implies that $[\mathbf{T}, 0]$ is of class $\mathcal{I}/\mathcal{F}$. Since the random walk has positive drift $(0 < \mathbb{E}[X_0] < \infty)$, the positively indexed part of the random walk $(S_n)_{n \ge 0}$ drifts to $+\infty$ a.s.. So, a.s., the $n$-th record epoch of 0 is always larger than the $(n-1)$-th record epoch of 0 for all $n \ge 1$, i.e., $R^n(0) > R^{n-1}(0)$, $\forall n \ge 1$. This implies that 0 has an infinite number of ancestors. The negatively indexed part $(S_{-n})_{n \ge 0}$ drifts to $-\infty$ a.s.. In particular, a.s., the random variable $m_{-1} := \sup_{n \ge 1} \{S_{-n}\}$ is finite and the random non-positive integer $u^* := -\min\{n \ge 1 : S_{-n} = m_{-1}\}$ exists. Since
$R(u^*) \ge 0$, there exists the smallest ancestor $u \in \mathbb{Z}$ of 0 such that $R(u^*) = u$. Since $S_n \le m_{-1}$ for all $n \le u^*$, $u^*$ has infinitely many descendants by Lemma 24. Therefore, by the interval property (Lemma 25), it follows that the record graph $\mathbb{Z}^R$ is connected. Further, by the classification theorem of unimodular Family Trees [7], $[\mathbf{T}, 0]$ is of class $\mathcal{I}/\mathcal{F}$. $\square$

### Instances of unimodular Family Trees

In this subsection, we describe three instances of unimodular Family Trees, one from each of the classes $\mathcal{F}/\mathcal{F}, \mathcal{I}/\mathcal{F}$ and $\mathcal{I}/\mathcal{I}$, which will be used in the next sections. The first instance is the Eternal Galton-Watson tree with offspring distribution $\pi$. It was studied in [7], in which it is shown that the tree is unimodular if and only if the mean of $\pi$ is 1. It is of class $\mathcal{I}/\mathcal{I}$ when $\pi$ is non degenerate. We introduce two new unimodular Family Trees, namely, the typically rooted Galton-Watson tree; which is of class $\mathcal{F}/\mathcal{F}$; and the unimodularised marked ECS ordered bi-variate Eternal Kesten tree, which is of class $\mathcal{I}/\mathcal{F}$. The former is shown to be obtained from Galton-Watson Tree by re-rooting the root to a typically chosen vertex of the Galton-Watson Tree.

### Typically rooted Galton-Watson Tree (TGWT)

Let $\pi$ be a probability distribution on $\{0, 1, 2, 3, \dots\}$ such that its mean $0 < m(\pi) < 1$ and $\hat{\pi}$ be the size-biased distribution of $\pi$, given by $\hat{\pi}(k) = \frac{k\pi(k)}{m(\pi)}$ for all $k \in \{0, 1, 2, \dots\}$. The **Typically rooted Galton-Watson Tree** $(TGWT(\pi))$ with offspring distribution $\pi$ is a Family Tree $[\mathbf{T}, \mathbf{o}]$ defined in the following way.

* Add a parent to the root $\mathbf{o}$ with probability $m(\pi)$. Independently iterate the same to the parent of $\mathbf{o}$ and to all of its ancestors. So, the number of ancestors of the root $\mathbf{o}$ has a geometric distribution with the success probability $1 - m(\pi)$.

* Let $Z$ be a random variable that has distribution $\hat{\pi}$ (the size-biasing of $\pi$). To each of the ancestors of $\mathbf{o}$ attach independently children with distribution the same as that of $Z - 1$.

* To each of these new children and to the root $\mathbf{o}$, attach independently ordered Galton-Watson trees with offspring distribution $\pi$.
See Figure 3.2 for an illustration.

*Remark 42.* The TGWT($\pi$) is a finite unimodular ordered Family Tree (see Proposition 52).

<figure><img src="image_9.png" /><figcaption>Figure 3.2: Typically rooted Galton-Watson Tree with offspring distribution $\pi$ (**o** is the root), $\mathbb{E}[\pi]$ is the probability that the root **o** has a parent, $\hat{\pi}$ is the offspring distribution of the parent of **o**, $N$ is a geometric random variable with the success probability $1 - \mathbb{E}[\pi]$.</figcaption></figure>

The nomenclature “typically rooted” in the typically rooted Galton-Watson Tree suggests that it is obtained by re-rooting to a typical vertex of a Galton-Watson tree. It is indeed true, we prove this fact in Proposition 50. We also give a characterizing condition for TGWT in Proposition 52.

## Bi-variate Eternal Kesten Tree

In the following, we give an instance of a unimodular tree of class *I/F* using the typically rooted joining operation. We first introduce a Family Tree which we call it the bi-variate Eternal Kesten Tree *EKT*(α, β) with offspring distributions α and β. It is unordered, unlabelled and parametrized by α and β. Using this Family Tree, we introduce a class of marked and ordered Family Trees namely marked ECS ordered bi-variate Eternal Kesten
Trees. None of these trees are unimodular, but we can obtain a unimodularised version from them using an operation called typically rooted joining. In order to perform this operation, it is essential that the mean of offspring distribution $\beta$ satisfies $m(\beta) < 1$. But, to define EKT($\alpha, \beta$), it is sufficient that the mean of the offspring distributions satisfy $m(\alpha) < \infty$ and $m(\beta) \le 1$.

Let $\alpha, \beta$ be two probability distributions on $\{0, 1, 2, \dots\}$ such that their means satisfy $m(\alpha) < \infty$ and $m(\beta) \le 1$. A **bi-variate Eternal Kesten Tree** with offspring distributions $\alpha, \beta$, denoted as EKT($\alpha, \beta$), is a random Family Tree $[T', o']$ consisting of a unique bi-infinite $F$-path $(o_n)_{n \in \mathbb{Z}}$, where $o_0 = o'$, with the following property: the sequence of Family Trees $([D(o_n) \setminus D(o_{n-1}), o_n])_{n \in \mathbb{Z}}$ is i.i.d. with the following common distribution: the offspring distribution of the root is $\alpha$ and the descendant trees of the children of the root are i.i.d. Galton-Watson trees with offspring distribution $\beta$ (denoted as GW($\beta$)). The Family Trees $\{[D(o_n) \setminus D(o_{n-1}), o_n] : n \in \mathbb{Z}\}$ are called the bushes of EKT($\alpha, \beta$) and the Family Tree $[D(o_0) \setminus D(o_{-1}), o_0]$ is called the **bush of the root**.

Note that EKT($\alpha, \beta$) is the joining of the i.i.d. sequence $([T_i, o_i])_{i \in \mathbb{Z}}$, where $T_i = D(o_i) \setminus D(o_{i-1})$. Keep in mind that $d_1(o_i, T_i) = d_1(o_i, T') - 1$, where $d_1(o_i, T_i)$ denotes the offspring count of $o_i$ in $T_i$.

In addition, suppose that $m(\beta) < 1$. Then, GW($\beta$) is subcritical, which implies that $\mathbb{E}[\#V(T_0)] < \infty$. So, in this case, we can take the typically rooted joining of the i.i.d. Family Trees $([T_i, o_i])_{i \in \mathbb{Z}}$. Let $[T, o]$ be the typically rooted joining of $([T_i, o_i])_{i \in \mathbb{Z}}$ (as in Eq. (2.3.4)). Then, by Theorem 19, the EFT $[T, o]$ is unimodular. We call the distribution of $[T, o]$ the unimodularised bi-variate EKT($\alpha, \beta$). The unimodularised EKT($\alpha, \beta$) is of class $\mathcal{I}/\mathcal{F}$.

An **Every Child Succeeding (ECS) order** on $[T', o']$ is obtained by declaring that $o_n$ is the smallest among $D_1(o_{n+1})$ and using the uniform order on the remaining children for all $n \in \mathbb{Z}$. The name “ECS” order comes from the fact that the succession line (see Def. 87) starting from the root reaches all the vertices on the bi-infinite path (i.e., the succession line is an order preserving bijection from $\mathbb{Z}$ to the vertices of the tree). The unimodularised ECS ordered EKT($\alpha, \beta$) is an example of a unimodular ordered EFT of class $\mathcal{I}/\mathcal{F}$. Later, we show that the unimodularised ECS ordered EKT($\alpha, \beta$) is the record graph of the network $[\mathbb{Z}, 0, X]$, where $X$ is as in Def. 22 and satisfies $\mathbb{E}[X_0] > 0$.

We focus on the ordered Family Trees whose vertices have marks that take values in $\mathbb{Z}$, as will be shown in the later sections that they encode
information about the trajectory of a skip-free to the left random walk when the mean of the random walk is positive. Let $\hat{T}_*$ denote the space of equivalence classes of rooted ordered Family Trees whose mark function assigns $\mathbb{Z}$-valued labels to its vertices. The space $\hat{T}_*$ is Polish [3]. We give an instance of a unimodular marked ordered Family Tree of class $\mathcal{I}/\mathcal{F}$. It is important to note that the distribution of the marks need not be independent of the tree structure. For instance, marks can be a deterministic function of the structure of a tree.

Let $\alpha, \beta$ be probability distributions on $\{0, 1, 2, \dots\}$ such that their means satisfy $m(\alpha) < \infty$ and $m(\beta) < 1$. A **bi-variate ECS ordered marked Eternal Kesten Tree MEKT$(\alpha, \beta)$** with parameters $\alpha, \beta$ is a random ordered marked rooted Family Tree $[T', o', Z']$ that has the following properties:

1. The Family Tree $[T', o']$ obtained by forgetting the marks is the ECS ordered EKT$(\alpha, \beta)$. Let $([T_i, o_i])_{i \in \mathbb{Z}}$ be the i.i.d. sequence of Family Trees whose joining is $[T', o']$ (with $o' = o_0$).

2. The sequence of marked Family Trees $([T_i, o_i, Z_i])_{i \in \mathbb{Z}}$ is i.i.d., where $Z_i$ is the mark function on $T_i$ obtained by restricting $Z'$ to $T_i$.

<figure><img src="image_10.png" /><figcaption>Figure 3.3: Bi-variate ECS ordered EKT with distributions $\bar{\pi}, \tilde{\pi}$ ($o_0$ is the root), $\bar{\pi}$ is the offspring distribution of $o_0$ in $T_0$, $\tilde{\pi}$ is the offspring distribution of every child of $o_0$ in $T_0$, see Eq. (3.2.8) for the expressions of $\bar{\pi}, \tilde{\pi}$.</figcaption></figure>
Remark 43. Because of the independence condition involved in the second part of the construction of MEKT(α, β), it follows that EKT(α, β) is the ECS ordered joining of an i.i.d. sequence of finite marked Family Trees ([Tᵢ, oᵢ, Zᵢ])ᵢ∈Z, where the distribution of [T₀, o₀] is as follows: the root o₀ does not have parent, the offspring distribution of o₀ is α, the descendant trees of the children of o₀ are independent subcritical ordered Galton-Watson trees with offspring distribution β.

It follows, from the second part of the construction of MEKT(α, β), that the sequence of random variables (Zᵢ(oᵢ))ᵢ∈Z is i.i.d. (see the Figure 3.3). Note that Zᵢ need not be independent of [Tᵢ, oᵢ] for any i ∈ Z.

Remark 44. It is also clear from the construction of MEKT(α, β) that the distribution of [T₀, o₀, Z₀] characterizes MEKT(α, β).

Remark 45. Let [T', o', Z'] be an MEKT(α, β) with α, β same as the above, and let [T, o, Z] be the random ordered marked Family Tree obtained by taking σ' on [T', o', Z'], i.e., for any measurable subset A of $\hat{T}_*$,

$$ \sigma'[A] = \frac{1}{\mathbb{E}[\#V(T_0)]} \mathbb{E} \left[ \sum_{v \in V(T_0)} \mathbf{1}_{[T', v, Z']}(A) \right]. \quad (3.2.1) $$

Then, by Theorem 19, the marked Family Tree [T, o, Z] is unimodular.

The distribution of the marked Family Tree [T, o, Z] is called the **uni-modularised MEKT** (α, β).

## Distribution of the record graph in the three phases

An n + 1-tuple of integers of the form (0, s₁, ..., sₙ₋₁, 1) with sⱼ ≤ 0 for all 1 ≤ j ≤ n - 1 is called an **excursion set**. Consider the skip-free to the right random walk (S₋ₙ)ₙ≥₀ associated to the i.i.d. sequence X = (Xₙ)ₙ∈Z. The following proposition describes the relation between an excursion set of this random walk and the descendant tree of 0. Let $\delta = \max\{n < 0 : S_n \ge 1\} = \max\{n < 0 : S_n = 1\}$ (by the skip-free property).

**Proposition 46.** Assume $\mathbb{E}[X_0] \le 0$. Consider the rooted network [Z, 0, X]. Then, the descendant tree of the root 0 in the connected component of 0 of the R-graph of [Z, 0, X] is a sample of the ordered Galton-Watson tree with offspring distribution $\pi \stackrel{D}{=} X_0 + 1$.
*Proof.* Since the random walk $(S_{-n})_{n \ge 0}$ drifts to $\infty$, we have $\delta > -\infty$. It follows from the definition of $L_X(0)$ (see Eq. (3.1.2)) that $L_X(0) = \delta - 1$ since $y(\delta, 0) = -S_\delta = -1$ and for any $\delta - 1 \le j < 0$, $y(j, 0) = -S_j > -1$. Thus, $L_X(0) > -\infty$ a.s., so that the condition required to apply Lemma 34 is satisfied. The first part of Lemma 34 implies that $d_1(0) = X_{-1} + 1 \stackrel{D}{=} \pi$.

We now show that, conditioned on the number of children of 0, the subtrees of these children are jointly independent Galton-Watson trees with offspring distribution $\pi$.

For each $m \ge 1$, let $i_m = \max\{n < 0 : y(i_m, 0) = X_{-1} + 1 - m\}$ and let $i_0 = 0$. By the third part of Lemma 34, $i_1 > i_2 > \cdots > i_{X_{-1}+1}$ are the children of 0, and $i_{X_{-1}+1} = L_X(0)$. The fact that, for each $m \ge 1$, $i_m$ is a stopping time for the random walk $(S_{-n})_{n \ge 0}$, and the third part of Lemma 34, together imply the following: the excursions $((S_{i_k} - S_{i_{k-1}}, S_{i_{k-1}} - S_{i_k}, \cdots, S_{i_{k+1}} - S_{i_k}))_{k=1}^{X_{-1}}$, with the notation $S_{i_0} = 0$, are independent and identically distributed as $(S_0, S_{-1}, \cdots, S_\delta)$.

By Lemma 24, for any $1 \le k \le X_{-1} + 1$, the descendant tree of $i_k$ is completely determined by

$$ (S_{i_k} - S_{i_{k-1}}, S_{i_{k-1}} - S_{i_{k-1}}, \cdots, S_{i_{k+1}} - S_{i_{k-1}}) \stackrel{D}{=} (S_0, S_{-1}, \cdots, S_\delta). $$

This completes the proof. $\square$

<figure><img src="image_11.png" /></figure>

*Remark 47.* Consider the i.i.d. sequence $\hat{X} = (\hat{X}_n)_{n \in \mathbb{Z}}$ with the distribution of $\hat{X}_0$ given by Eq. (3.1.5). Since $\mathbb{E}[\hat{X}_0] < 0$ by Lemma 32, the assumption of Proposition 46 is satisfied. This implies that the descendant tree of 0 in the record graph of $[\mathbb{Z}, 0, \hat{X}]$ is a Galton-Watson tree with offspring distribution the same as that of $\hat{X}_0 + 1$. This will be used in the last part of Step 2 of Theorem 54.

## Negative mean

**Theorem 48.** Let $[T, o]$ be the connected component of 0 in the R-graph of $[\mathbb{Z}, 0, X]$ and rooted at $o = 0$. If $\mathbb{E}[X_0] < 0$, then $[T, o]$ is the Typically rooted Galton-Watson Tree with offspring distribution $\pi$, where $\pi$ is the distribution of $X_0 + 1$.

*Proof.* We prove the theorem in several steps.

In Step 1, we show that the descendant tree of the root $o$ is a Galton-Watson Tree with offspring distribution $\pi$. In Step 2, we compute the
probability that $o$ has a parent. One way to compute it is by using Kemperman's formula (see [9, Proposition 3.7]). Alternatively, one could use the unimodularity of $[T, o]$. We use the latter in this step. **Step 3** involves computing the offspring distribution of $F(o)$ conditioned that $o$ has a parent. In **Step 4**, we give the distribution of the order of $o$ among its siblings conditioned on the fact that $o$ has a parent. In **Step 5**, we show that the descendant trees of the siblings of $o$ conditioned on the fact that $o$ has a parent are independent Galton-Watson trees with offspring distribution $\pi$.

The final step (**Step 6**) involves showing that the offspring distribution of $F^2(o)$ conditioned on the fact that $o$ has an ancestor of order 2 is the same as the offspring distribution of $F(o)$ conditioned on the fact that $o$ has a parent. Similarly, we show that the descendant trees of siblings of $F(o)$ and its order among its siblings conditioned on the fact that $o$ has an ancestor of order 2 have the same distribution as that of $o$ conditioned on the fact that $o$ has a parent.

**Step 1:** Since the random walk $(S_{-n})_{n \ge 0}$ has positive drift, $-\infty < L(0)$. By Proposition 46, the descendant tree of $o$ is GW($\pi$).

**Step 2:** Since $[T, o]$ is the connected component of 0 in the $R$-graph of a unimodular network $[\mathbb{Z}, 0, X]$, it is also unimodular by Lemma 16. Therefore,

$$ 
\begin{aligned}
\mathbb{P}[o \text{ has a parent}] &= \mathbb{E}\left[\sum_{u \in V(T)} \mathbf{1}\{F(o) = u\}\right] = \mathbb{E}\left[\sum_{u \in V(T)} \mathbf{1}\{F(u) = o\}\right] \\
&= \mathbb{E}[d_1(o)] = m(\pi) = \mathbb{E}[X_0] + 1,
\end{aligned}
$$

where $m(\pi)$ is the mean of $\pi$. In particular,

$$ \mathbb{P}[S_n < 0 \quad \forall n > 0] = \mathbb{P}[o \text{ does not have parent}] = -\mathbb{E}[X_0]. $$

**Step 3:** Note that $o$ has a parent if and only if $\tau < \infty$ (see the paragraph above Lemma 28 for the definition of $\tau$). So, $\mathbb{P}[\tau < \infty] = m(\pi)$. Since $(S_{-n})_{n \ge 0}$ drifts to $+\infty$, part (1) of Lemma 34 implies the equality of the two events $\{d_1(F(o)) = n, \tau < \infty\} = \{X_{\tau-1} = n-1, \tau < \infty\}$, for any $n > 0$. Therefore, for any $n > 0$,

$$ 
\begin{aligned}
\mathbb{P}[d_1(F(o)) = n, \tau < \infty] &= \sum_{j=0}^{n-1} \mathbb{P}[\tau < \infty, X_{\tau-1} = n-1, S_{\tau} = j] \\
&= \sum_{j=0}^{n-1} \mathbb{P}[S_1 = n-1] c^{j-n+1} = n\pi(n). \quad (3.2.2)
\end{aligned}
$$
Eq. (3.2.2) follows from the previous equation by Lemma 28. The last equation follows since $c = \mathbb{P}[S_n = -1 \text{ for some } n > 0] = 1$ as the random walk $(S_n)_{n \ge 0}$ drifts to $-\infty$. Therefore,

$$ \mathbb{P}[d_1(F(o)) = n | \tau < \infty] = \frac{n\pi(n)}{m(\pi)} = \hat{\pi}(n), $$

for all $n > 0$.

**Step 4:** Let $c_k(u)$ denote $k$-th child of $u$ for any vertex $u$ and positive integer $k$. Note that the equality of the two events $\{\tau < \infty, c_k(F(o)) = o, d_1(o) = n\} = \{\tau < \infty, X_{\tau-1} = n-1, S_\tau = n-k\}$ for any $0 < k \le n$ follows from part (3) of Lemma 34 (with $i_m$ as 0 and $i$ as $F(0)$). Therefore, using Lemma 28 and $c=1$, we obtain for any $0 < k \le n$,

$$ \mathbb{P}[\tau < \infty, c_k(F(o)) = o, d_1(o) = n] = \mathbb{P}[X_0 = n-1]. $$

Thus, for any $0 < k \le n$

$$ \mathbb{P}[c_k(F(o)) = o | d_1(o) = n, \tau < \infty] = \frac{\mathbb{P}[X_0 = n-1]}{n\mathbb{P}[X_0 = n-1]} = \frac{1}{n}, $$

which is the uniform order among the siblings of $o$.

**Step 5:** On the event $\{\tau < \infty, d_1(F(o)) = n, c_k(F(o)) = o\}$, let $i_n < i_{n-1} < \dots < i_1$ be the positions of the children of $F(o)$. Then, conditioned on $\{\tau < \infty, d_1(F(o)) = n, c_k(F(o)) = o\}$, for each $1 \le j \le n-1$, the part of the random walk $(0, S_{i_{j-1}} - S_{i_j}, S_{i_{j-2}} - S_{i_j}, \dots, S_{i_{j+1}} - S_{i_j})$ is an excursion set by Lemma 34 (part 3). Further, these excursion sets are independent of one another because the times $i_j$ (for $1 \le j \le n$) are stopping times. Indeed, for all $1 \le j \le n-1$, $S_{i_{j+1}} - S_{i_j} = 1$ and $S_l < S_{i_{j+1}}$ for all $i_{j+1} < l \le i_j$. Therefore, for each $1 \le j \le n-1$, $(0, S_{i_{j-1}} - S_{i_j}, S_{i_{j-2}} - S_{i_j}, \dots, S_{i_{j+1}} - S_{i_j})$ is the skip-free to the right random walk $(S_{-n})_{n \ge 0}$ conditioned on $\eta_1 < \infty$, and stopped at $\eta_1$, where $\eta_1 = \min\{n > 0 : S_{-n} = 1\}$. But $(S_{-n})_{n \ge 0}$ drifts to $+\infty$. So, $\eta_1 < \infty$ a.s.. Hence, $(0, S_{i_{j-1}} - S_{i_j}, S_{i_{j-2}} - S_{i_j}, \dots, S_{i_{j+1}} - S_{i_j})$ has the same distribution as $(0, S_{-1}, \dots, S_{\eta_1})$. Therefore, by Proposition 46, for each $1 \le j \le n$, the descendant trees are independent $GW(\pi)$.

**Step 6:** Observe that the distribution of $(S_n - S_\tau)_{n \ge \tau}$ conditioned on $\tau < \infty$ is the same as that of $(S_n)_{n \ge 0}$ by the strong Markov property. Therefore,

$$ \mathbb{P}[F(o) \text{ has a parent } | \{o \text{ has a parent}\}] = \mathbb{P}[o \text{ has a parent}] = m(\pi). $$
Since $(S_{-n})_{n \ge 0}$ drifts to $+\infty$ a.s., it reaches $S_{R^2(0)+1}$ a.s.. Therefore, by part (1) of Lemma 34, the distribution of $d_1(F^2(o))$ conditioned on the event $\{o \text{ has a grandparent}\}$ is equal to the distribution of $X_{R^2(0)-1}+1$ conditioned on $\{R^2(0) > R(0)\}$ (i.e., $o$ has a grandparent) which has the same distribution as that of $X_{R(0)-1}+1$ conditioned on $R(0) > 0$ (i.e., $X_{\tau-1}$ conditioned on $\tau < \infty$). In particular, the distribution of $[D(F^2(o))\setminus D(F(o)), o]$ conditioned on $\{o \text{ has a grandparent}\}$ is the same as that of $[D(F(o))\setminus D(o), o]$ conditioned on $\{o \text{ has a parent}\}$. By induction, it follows that $[D(F^n(o))\setminus D(F^{n-1}(o)), o]$ conditioned on $\{o \text{ has } n-\text{th ancestor}\}$ has the same distribution as that of $[D(F(o))\setminus D(o), o]$ conditioned on $\{o \text{ has a parent}\}$. $\square$

We now show that the Typically rooted Galton-Watson Tree is obtained by re-rooting to a typical vertex of a Galton-Watson Tree. Let us continue to use the notations in Theorem 48 and let $\{F(o) = o\}$ denote the event that $o$ does not have a parent. Let $[T', o']$ be the Family Tree obtained from $[T, o]$ by conditioning on the event that $o$ does not have a parent. We first show that the distribution of $[T', o']$ is $GW(\pi)$. Since $m(\pi) < 1$, then $GW(\pi)$ has finite mean size. So, we could apply Eq. 2.3.4 to $GW(\pi)$. We then prove that $[T, o]$ is obtained from $[T', o']$ by re-rooting to a typical vertex of $T'$.

**Lemma 49.** With the notations as in the above paragraph, the distribution of $[T', o']$ is $GW(\pi)$.

*Proof.* Note that the events $\{F(o) = o\}$ and $\{S_n < 0 \forall n > 0\}$ are one and the same because the latter event is the same as $\{R(0) = 0\}$. The random variables $\{S_n : n \le 0\}$ are independent of the event $\{S_n < 0 \forall n > 0\}$, and the descendant tree of 0 is a measurable function of $\{S_n : n \le 0\}$. This implies that the distribution of $[D(o), o]$ conditioned on the event $\{F(o) = o\}$ is the same as $[[D(o), o]]$ (the unconditioned Family Tree). Therefore,

$$[T', o'] = [D(o), o]|\{F(o) = o\} \stackrel{D}{=} [D(o), o].$$

By Proposition 46, the distribution of $[D(o), o]$ is $GW(\pi)$. $\square$

**Proposition 50.** Let $\alpha$ be a probability measure on $\{0, 1, 2, \dots\}$ such that its mean $m(\alpha) < 1$. Then, the TGWT($\alpha$) is obtained by re-rooting to a typical vertex of $GW(\alpha)$.
*Proof.* Take an i.i.d. sequence of random variables $X' = (X'_n)_{n \in \mathbb{Z}}$ such that their common distribution is given by $\mathbb{P}[X'_0 = j] = \alpha(j+1)$ for all $j \in \{-1, 0, 1, 2, \dots\}$. Let $[\mathbf{T}, \mathbf{o}]$ be the component of 0 in the record graph of $[\mathbb{Z}, 0, X']$ and let $[\mathbf{T}', \mathbf{o}']$ be the Family Tree obtained from $[\mathbf{T}, \mathbf{o}]$ by conditioning on the event that $\mathbf{o}$ does not have a parent. By Theorem 48, the distribution of $[\mathbf{T}, \mathbf{o}]$ is TGWT($\alpha$), which is unimodular; and by Lemma 49, the distribution of $[\mathbf{T}', \mathbf{o}']$ is GW($\alpha$), which has finite mean size. We show that $[\mathbf{T}, \mathbf{o}]$ is obtained from $[\mathbf{T}', \mathbf{o}']$ by re-rooting to a typical vertex of $\mathbf{T}'$.

For any measurable subset $A$ of $\mathcal{T}_*$, consider the function $g_A : \mathcal{T}_* \to \mathbb{R}_{\ge 0}$ given by $g_A([T, u, v]) = \mathbf{1}_A([T, u])\mathbf{1}\{F(v) = v\}$. Then, for any measurable set $A$, we have,

$$ \mathbb{E}\left[\sum_{u \in V(\mathbf{T})} g_A([\mathbf{T}, \mathbf{o}, u])\right] = \mathbb{E}[\mathbf{1}_A([\mathbf{T}, \mathbf{o}])] = \mathbb{P}[[\mathbf{T}, \mathbf{o}] \in A], $$

since there is only one vertex that has no parent. Similarly,

$$ \begin{aligned} \mathbb{E}\left[\sum_{u \in V(\mathbf{T})} g_A([\mathbf{T}, u, \mathbf{o}])\right] &= \mathbb{E}\left[\mathbf{1}\{F(\mathbf{o}) = \mathbf{o}\} \sum_{u \in V(\mathbf{T})} \mathbf{1}_A([\mathbf{T}, u])\right] \\ &= \mathbb{E}\left[\sum_{u \in V(\mathbf{T}')} \mathbf{1}_A([\mathbf{T}', u])\right] \mathbb{P}[F(\mathbf{o}) = \mathbf{o}]. \end{aligned} $$

The last step follows since $[\mathbf{T}', \mathbf{o}']$ is the Family Tree obtained from $[\mathbf{T}, \mathbf{o}]$ by conditioning on the event $\{F(\mathbf{o}) = \mathbf{o}\}$.

By the unimodularity of $[\mathbf{T}, \mathbf{o}]$, we have

$$ \mathbb{P}[[\mathbf{T}, \mathbf{o}] \in A] = \mathbb{E}\left[\sum_{u \in V(\mathbf{T}')} \mathbf{1}_A([\mathbf{T}', u])\right] \mathbb{P}[F(\mathbf{o}) = \mathbf{o}]. $$

By taking $A = \mathcal{T}_*$, we obtain $\mathbb{P}[F(\mathbf{o}) = \mathbf{o}]\mathbb{E}[\#V(\mathbf{T})] = 1$. Thus, for any measurable set $A$, we have

$$ \mathbb{P}[[\mathbf{T}, \mathbf{o}] \in A] = \frac{1}{\mathbb{E}[\#V(\mathbf{T})]} \mathbb{E}\left[\sum_{u \in V(\mathbf{T}')} \mathbf{1}_A([\mathbf{T}', u])\right]. $$

□
We now give a characterizing condition for TGWT. The proof of this proposition depends on the following lemma which says that in order to completely describe a unimodular Family Tree, it is sufficient to describe the distribution of the descendant tree of the root.

**Lemma 51.** Let $[\mathbf{T}, \mathbf{o}]$ be a unimodular Family Tree. Then, $[\mathbf{T}, \mathbf{o}]$ is completely characterized by $[D(\mathbf{o}), \mathbf{o}]$.

*Proof.* Observe that $[D(F^n(\mathbf{o})), \mathbf{o}]$ converges weakly to $[\mathbf{T}, \mathbf{o}]$ as $n \to \infty$. Indeed, $[D(F^n(\mathbf{o})), \mathbf{o}]_r \stackrel{D}{=} [\mathbf{T}, \mathbf{o}]_r$ for all $n > r$.

We have, for any measurable set $A$,

$$ \mathbb{P}[[D(F^n(\mathbf{o})), \mathbf{o}] \in A] = \mathbb{E}\left[\sum_{u \in V(\mathbf{T})} \mathbf{1}_A[D(u), \mathbf{o}]\mathbf{1}\{u = F^n(\mathbf{o})\}\right]. $$

By unimodularity, the equation on the right-hand side is equal to

$$ \mathbb{E}\left[\sum_{u \in V(\mathbf{T})} \mathbf{1}_A[D(\mathbf{o}), u]\mathbf{1}\{\mathbf{o} = F^n(u)\}\right]. $$

Therefore, we have

$$ \mathbb{P}[[D(F^n(\mathbf{o})), \mathbf{o}] \in A] = \mathbb{E}\left[\sum_{u \in D_n(\mathbf{o})} \mathbf{1}_A[D(\mathbf{o}), u]\right]. $$

□

Lemma 51 is closely related to [2, Proposition 10]. In the language of this work, the latter proposition proves that if the descendant tree $[D(\mathbf{o}), \mathbf{o}]$ of a rooted Family Tree $[\mathbf{T}, \mathbf{o}]$ is a fringe distribution, then $[\mathbf{T}, \mathbf{o}]$ is completely described by $[D(\mathbf{o}), \mathbf{o}]$. Its connection to Lemma 51 follows from the observation: for any unimodular tree $[\mathbf{T}, \mathbf{o}]$ of class $\mathcal{I}/\mathcal{I}$, its descendant tree $[D(\mathbf{o}), \mathbf{o}]$ is a fringe distribution. However, Lemma 51 is also applicable to the unimodular Family trees of class $\mathcal{I}/\mathcal{F}$. For more details on this connection, see [7, Bibliographical Comments (Section 6.3)].

The following proposition and its proof are analogous to the characterization of Eternal Galton-Watson Tree of [7]. However, the following proposition differs from the former as its statement is about finite Family Trees, whereas the former is about EFTs.
In the following proposition, only the random objects are denoted in bold letters. We use the notations of Section 2.1, Chapter 2. For a (deterministic) Family Tree $[T, o]$, the non-descendant tree of the root $o$ is the Family Tree $[D^c(o), o]$, where $D^c(o)$ is the subtree induced by $(V(T)\setminus D(o)) \cup \{o\}$. For any vertex $u$ of $T$, let $c_j(u)$ denote the $j$-th child of $u$.

**Proposition 52** (Characterization of TGWT). A random finite Family Tree $[T, o]$ is a Typically rooted Galton-Watson Tree (TGWT) if and only if

1. it is unimodular, and

2. the number of children of the root $d_1(o)$ is independent of the non- descendant tree of the root $o$.

*Proof.* Let $[T, o]$ be a random Family Tree whose distribution is $TGWT(\pi)$, where $\pi$ is a probability measure on $\{0, 1, 2, 3, \dots\}$ with $m(\pi) < 1$. Consider an i.i.d. sequence $X = (X_n)_{n \in \mathbb{Z}}$ of random variables whose common distri- bution is given by $\mathbb{P}[X_0 = n] = \pi(n+1)$ for all $n \in \{-1, 0, 1, 2, \dots\}$, and let $[\mathbb{Z}, 0, X]$ be its network. Since $\mathbb{E}[X_0] < 0$, by Theorem 48, the connected component of 0 in the $R$-graph of $[\mathbb{Z}, 0, X]$ is $TGWT(\pi)$. Therefore, $[T, o]$ is unimodular by Lemma 16. The second condition is satisfied by TGWT, which follows from its construction.

We now show that if a random finite Family Tree $[T, o]$ satisfies the above conditions 1 and 2, then it is a TGWT.

Let $E$ denote the event that $o$ has a parent. For a positive integer $k$, let $A = (A'; A_1, A_2, \dots, A_k)$ be an event of the form

$$d_1(o) = k, D^c(o) \in A', D(c_1(o)) \in A_1, \dots, D(c_k(o)) \in A_k. \quad (3.2.3)$$

By Lemma 51, any unimodular Family Tree is characterized by the descen- dant tree of its root. So, it is sufficient to prove that

$$\mathbb{P}[A] = \mathbb{P}[d_1(o) = k] \mathbb{P}[D^c(o) \in A'] \left( \prod_{i=1}^{k} \mathbb{P}[D(o) \in A_i] \right), \quad (3.2.4)$$

for any such event $A$ of the form given by Eq (3.2.3). Assume further that the events $A_1, A_2, \dots, A_k$ depend only up to $n$-th generation of $o$, which is the union of $D_1(o), D_2(o), \dots, D_n(o)$. It suffices to show Eq. (3.2.4) for such events because of the local topology.
We prove the result by induction on $n$. For $n = 0$, we have $\mathbb{P}[A] = \mathbb{P}[d_1(\mathbf{o}) = k]\mathbb{P}[D^c(\mathbf{o}) \in A']$ by condition 2 of the hypothesis. So, assume that the result is true for $n-1$. Let $n \ge 1$ and $1 \le j \le k$. For any Family Tree $[T, o]$, let $h_j([T, o]) := \mathbf{1}_A[T, F(o)]\mathbf{1}\{o = c_j(F(o))\}$. Then, for any $1 \le j \le k$, we have

$$ \mathbf{1}_A[T, o] = \sum_{u \in D_1(o)} \mathbf{1}_A[T, F(u)]\mathbf{1}\{u = c_j(o)\} = \sum_{u \in D_1(o)} h_j([T, u]). \quad (3.2.5) $$

Note that, since $k \ge 1$, the event $\{[T, o] \in A\}$ is a subset of the event $\{D_1(o) \ne \emptyset\}$ Applying Eq. (3.2.5) for $j = 1$, we obtain

$$ \begin{aligned} \mathbb{P}[A] &= \mathbb{E} \left[ \sum_{u \in V(T)} \mathbf{1}_A[T, F(u)] \mathbf{1}\{u = c_1(\mathbf{o})\} \mathbf{1}\{u \in D_1(\mathbf{o})\} \right] \\ &= \mathbb{E} \left[ \sum_{u \in V(T)} \mathbf{1}_A[T, F(\mathbf{o})] \mathbf{1}\{\mathbf{o} = c_1(u)\} \mathbf{1}\{\mathbf{o} \in D_1(u)\} \right] \quad (3.2.6) \\ &= \mathbb{E}[\mathbf{1}_A[T, F(\mathbf{o})] \mathbf{1}\{\mathbf{o} \in E\} \mathbf{1}\{\mathbf{o} = c_1(F(\mathbf{o}))\}] \\ &= \mathbb{P}[\mathbf{o} \in E, \mathbf{o} = c_1(F(\mathbf{o})), [T, F(\mathbf{o})] \in A] \quad (3.2.7) \\ &= \mathbb{P}[D(\mathbf{o}) \in A_1, \mathbf{o} \in E, \mathbf{o} = c_1(F(\mathbf{o})), [T, F(\mathbf{o})] \in A(A'; \mathcal{T}_*, A_2, \dots, A_k)]. \end{aligned} $$

In the above, Eq. (3.2.6) follows from unimodularity. Note that $D(o) \in A_1$ depends on one generation less that of $[T, F(o)] \in A$. Therefore, by induction, we obtain,

$$ \begin{aligned} \mathbb{P}[A] &= \mathbb{P}[D(\mathbf{o}) \in A_1]\mathbb{P}[\mathbf{o} \in E, \mathbf{o} = c_1(F(\mathbf{o})), [T, F(\mathbf{o})] \in A(A'; \mathcal{T}_*, A_2, \dots, A_k)] \\ &= \mathbb{P}[D(\mathbf{o}) \in A_1]\mathbb{P}[A(A'; \mathcal{T}_*, A_2, \dots, A_k)]. \end{aligned} $$

The last equation is obtained by Eq. (3.2.7).

Applying Eq. (3.2.5) with $j = 2$ to $A(A'; \mathcal{T}_*, A_2, \dots, A_k)$, we obtain

$$ \begin{aligned} \mathbb{P}[A(A'; \mathcal{T}_*, A_2, \dots, A_k)] &= \mathbb{P}[D(\mathbf{o}) \in A_2]\mathbb{P}[\mathbf{o} \in E, \mathbf{o} = c_1(F(\mathbf{o})), [T, F(\mathbf{o})] \in A(A'; \mathcal{T}_*, \mathcal{T}_*, \dots, A_k)] \\ &= \mathbb{P}[D(\mathbf{o}) \in A_2]\mathbb{P}[A(A'; \mathcal{T}_*, \mathcal{T}_*, \dots, A_k)]. \end{aligned} $$
By iterating the same procedure for $j = 3, 4, \dots$, we obtain,

$$ \mathbb{P}[A] = \left( \prod_{i=1}^{k} \mathbb{P}[D(\mathbf{o}) \in A_i] \right) \mathbb{P}[d_1(\mathbf{o}) = k, D^c(\mathbf{o}) \in A'] \\ = \left( \prod_{i=1}^{k} \mathbb{P}[D(\mathbf{o}) \in A_i] \right) \mathbb{P}[d_1(\mathbf{o}) = k] \mathbb{P}[D^c(\mathbf{o}) \in A'] $$

Thus, we showed Eq. (3.2.4), which completes the proof. □

## Zero mean

**Theorem 53.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be a sequence of random variables as in Def. 22 with $\mathbb{E}[X_0] = 0$, $[\mathbb{Z}, 0, X]$ be its associated network, and $[\mathbf{T}, 0]$ be the connected component of 0 in the R-graph of $[\mathbb{Z}, 0, X]$. Then, $[\mathbf{T}, 0]$ is the ordered Eternal Galton-Watson Tree EGWT($\pi$) with offspring distribution $\pi \stackrel{D}{=} X_0 + 1$.

*Proof.* We apply Theorem 18. We show that $[\mathbf{T}, 0]$ satisfies the second condition of Theorem 18. Observe that $L_X(0)$ is a stopping time for the random walk with increments $(X_{-n})_{n \ge 1}$ and $-\infty < L_X(0)$ a.s.. By the strong Markov property, the random variables $Y = (X_{-n})_{n>-L_X(0)}$ are independent of $Z = (X_{-n})_{n=L_X(0)}$. Let $(\mathbf{T}', 0)$ denote the non-descendant tree of $o$, i.e., the tree generated by $(\mathbf{T} \setminus D(0)) \cup \{0\}$. By Lemma 24, the subtree $(D(0), 0)$ is a function of $Z$ and the subtree $(\mathbf{T}', 0)$ is a function of $Y \cup (X_n)_{n \ge 0}$. So, the unordered tree $(D(0), 0)$ is independent of the unordered tree $(\mathbf{T}', 0)$. The second part of Lemma 34 implies that, conditionally on the event that $0$ has children, the order of a child is independent of $Y \cup (X_n)_{n \ge 0}$, whereas the order of any vertex in $(\mathbf{T}', 0)$ is a function of $Y \cup (X_n)_{n \ge 0}$. Thus, the ordered subtree $(D(0), 0)$ is independent of the ordered subtree $(\mathbf{T}', 0)$. So, the sufficient condition of Theorem 18 is satisfied by $[\mathbf{T}, 0]$.

The first statement of Lemma 34 implies that $d_1(0) = X_{-1} + 1$, and thus completes the proof. □

## Positive mean

Let $X = (X_n)_{n \in \mathbb{Z}}$ be the i.i.d. increments of a skip-free random walk with mean $0 < \mathbb{E}[X_0] < \infty$, and $[\mathbb{Z}, 0, X]$ be its associated network.
Let $\eta_{-1} = \inf\{n > 0 : S_n = -1\}$ if the infimum exists and $\infty$ if $S_n > -1 \forall n \ge 1$, and let $c = \mathbb{P}[\eta_{-1} < \infty]$. Let $[\mathbf{T}, \mathbf{o}]$ be the connected component of 0 in the $R$-graph of $[\mathbb{Z}, 0, X]$, with root $0 = \mathbf{o}$.

Let $\tilde{\pi}, \bar{\pi}$ be the probability distributions on $\{0, 1, 2, \dots\}$ given by:

$$ \tilde{\pi}(k) = c^{k-1}\mathbb{P}[X_0 = k - 1], \quad (3.2.8) $$

$$ \bar{\pi}(k) = \mathbb{P}[X_0 \ge k]c^k. $$

Let $[\mathbf{T}_0, \mathbf{o}_0]$ be a Family Tree whose distribution is given by the following: the offspring distribution of $\mathbf{o}_0$ is $\bar{\pi}$. The descendant trees of the children of $\mathbf{o}_0$ are independent Galton-Watson trees with offspring distribution $\tilde{\pi}$, and they are independent of the offspring distribution of $\mathbf{o}_0$. Let $([\mathbf{T}_i, \mathbf{o}_i])_{i \in \mathbb{Z}}$ be an i.i.d. sequence of Family Trees. Recall that the distribution of the Family Tree obtained from the typically rooted joining of $([\mathbf{T}_i, \mathbf{o}_i])_{i \in \mathbb{Z}}$ is the unimodularised EKT$(\bar{\pi}, \tilde{\pi})$.

**Theorem 54.** If $0 < \mathbb{E}[X_0] < \infty$, then the distribution of $[\mathbf{T}, \mathbf{o}]$ is the unimodularised EKT$(\bar{\pi}, \tilde{\pi})$.

*Proof.* Since the random walk has a finite positive drift, the unimodular EFT $[\mathbf{T}, \mathbf{o}]$ is of class $\mathcal{I}/\mathcal{F}$, see Theorem 41. Let $\mathbf{o} \in \mathcal{A}$ denote the event that $\mathbf{o}$ belongs to the bi-infinite path of $\mathbf{T}$. Let $[\mathbf{T}', \mathbf{o}']$ denote the Family Tree obtained from $[\mathbf{T}, \mathbf{o}]$ by conditioning on the event $\mathbf{o} \in \mathcal{A}$, denoted as $[\mathbf{T}, \mathbf{o}]|\mathbf{o} \in \mathcal{A}$. By Theorem 20, $[\mathbf{T}', \mathbf{o}']$ is the joining of some stationary sequence of Family Trees $([\mathbf{T}'_i, \mathbf{o}'_i])_{i \in \mathbb{Z}}$. The proof is complete once we prove that this sequence is i.i.d., and $[\mathbf{T}'_1, \mathbf{o}'_1] \stackrel{D}{=} [\mathbf{T}_0, \mathbf{o}_0]$.

Step 1: $([\mathbf{T}'_i, \mathbf{o}'_i])_{i \in \mathbb{Z}}$ is an i.i.d. sequence: Since the increments have positive mean, $S_n \to +\infty$ as $n \to +\infty$ and $S_n \to -\infty$ as $n \to -\infty$. By Lemma 24, $\mathbf{o} \in \mathcal{A}$ if and only if $L_X(0) = \infty$, and the latter condition holds if and only if $S_n \le 0, \forall n \le -1$.

For any $u \in \mathbb{Z}$, let $\mathcal{S}(u)$ denote the (random) subtree of the descendants of $u$ (including $u$) in $\mathbf{T}$. The distribution of $([\mathbf{T}'_i, \mathbf{o}'_i])_{i \ge 1}$ is the same as that of

$$ ([\mathcal{S}(F^n(\mathbf{o})) \setminus \mathcal{S}(F^{n-1}(\mathbf{o})), F^n(\mathbf{o}))_{n \ge 1} | \mathbf{o} \in \mathcal{A} $$

(distribution obtained by conditioning on $\mathbf{o} \in \mathcal{A}$), where $F$ is the parent vertex-shift on $\mathbf{T}$ with the convention that $F^0(\mathbf{o}) = \mathbf{o}$ (and $F^n(\mathbf{o})$ is the parent of order $n$ of $\mathbf{o}$). On the event $\mathbf{o} \in \mathcal{A}$, each subtree $\mathcal{S}(F^n(\mathbf{o})) \setminus \mathcal{S}(F^{n-1}(\mathbf{o}))$ is completely determined by the part of the random walk

$$ (S_{R^{n-1}(0)+1} - S_{R^{n-1}(0)}, \dots, S_{R^n(0)} - S_{R^{n-1}(0)}), $$
for each $n \ge 1$ (see Figure 3.4 for an illustration). The distribution of the sequence

$$((S_{R^{n-1}(0)+1} - S_{R^{n-1}(0)}, \dots, S_{R^n(0)} - S_{R^{n-1}(0)}))_{n \ge 1}$$

conditioned on $\{S_n \le 0 : n \le -1\}$ is the same as that of the unconditioned sequence (the same sequence without the condition) because the sequence is independent of the event on which it is conditioned. Moreover, it is an i.i.d. sequence by the strong Markov property of the random walk. This implies that $([\mathbf{T}'_i, \mathbf{o}'_i])_{i \ge 1}$ is an i.i.d. sequence.

<figure><img src="image_12.png" /><figcaption>Figure 3.4: Illustration of the subtrees of ancestors of 0 on a trajectory conditioned on the event that $S_n \le 0$ for all $n \le 0$ when $\mathbb{E}[X_0] > 0$. Each box represents the subtrees $\mathbf{T}_1, \mathbf{T}_2, \mathbf{T}_3, \dots$ (see Step 1 of Theorem 54).</figcaption></figure>

Further, the stationarity of $([\mathbf{T}'_i, \mathbf{o}'_i])_{i \in \mathbb{Z}}$ implies that $([\mathbf{T}'_i, \mathbf{o}'_i])_{i \in \mathbb{Z}}$ is an i.i.d. sequence (the index set here is $\mathbb{Z}$, whereas in the previous sentence it is $i \ge 1$).

**Step 2:** $[\mathbf{T}'_1, \mathbf{o}'_1] \stackrel{D}{=} [\mathbf{T}_0, \mathbf{o}_0]$ : We first show that the offspring distribution of $\mathbf{o}'_1$ is $\bar{\pi}$. Let $\tau = \inf\{n > 0 : S_n \ge 0\}$ and $\infty$ if $S_n < 0, \forall n > 0$, and $X_{\tau-1}, S_\tau$ be the increment and location of the random walk at this time. Since the increments have positive mean, $\tau < \infty$ a.s., and therefore $R(0) = \tau$ a.s. (if $\tau = \infty$ then $R(0)$ is defined to be 0).
We also have the equality of the following events,

$$ \{d_1(F(\mathbf{o})) = 1\} = \{\tau = 1\} = \{X_{\tau-1} = S_{\tau}\} = \{S_1 \ge 0\}. $$

Therefore,

$$ \mathbb{P}[d_1(F(\mathbf{o})) = 1, \mathbf{o} \in \mathcal{A}] = \sum_{j=0}^{\infty} (\mathbb{P}[X_0 = j] \mathbb{P}[\mathbf{o} \in \mathcal{A}]) = \mathbb{P}[X_0 \ge 0] \mathbb{P}[\mathbf{o} \in \mathcal{A}]. $$

We now study the event $d_1(F(\mathbf{o})) = k$ with $k > 1$ (since 0 is the child of $\tau$, the event $\mathbb{P}[d_1(\tau) = 0] = 0$). Observe that, on the event $\mathbf{o} \in \mathcal{A}$, no negative integer is a child of $F(\mathbf{o})$. To see this, it is sufficient to show that $L_X(0) = -\infty$. Because, the latter condition implies that all the non-negative integers are the descendants of 0 by Lemma 24. So, none of them are the children of $\tau$ (see Figure 3.4). The latter condition is equivalent to $S_n \le 0, \forall n < 0$, which is further equivalent to $\mathbf{o} \in \mathcal{A}$. Thus, the observation follows. This observation implies that 0 is the last child of $\tau$. So, $l_X(\tau) = 0$ and $t_X(\tau) = S_\tau \ge 0$. Using Lemma 38, we obtain the relation $d_1(\tau) = X_{\tau-1} + 1 - S_\tau$. Use this relation to get

$$ \mathbb{P}[d_1(F(\mathbf{o})) = k, \mathbf{o} \in \mathcal{A}] = \sum_{j=k-1}^{\infty} \mathbb{P}[X_{\tau-1} = j, S_{\tau} = j - (k-1)] \mathbb{P}[\mathbf{o} \in \mathcal{A}]. $$

We apply Lemma 28 to the first term inside the sum to get

$$ \mathbb{P}[X_{\tau-1} = j, S_{\tau} = j - (k-1)] = \mathbb{P}[X_0 = j]c^{k-1}, 0 < k-1 \le j. $$

Using this, we obtain

$$ \begin{aligned} \mathbb{P}[d_1(F(\mathbf{o})) = k, \mathbf{o} \in \mathcal{A}] &= \sum_{j=k-1}^{\infty} \mathbb{P}[X_0 = j]c^{k-1}\mathbb{P}[\mathbf{o} \in \mathcal{A}] \\ &= \mathbb{P}[X_0 \ge k-1]c^{k-1}\mathbb{P}[\mathbf{o} \in \mathcal{A}]. \end{aligned} $$

Thus, the offspring distribution of $\mathbf{o}'_1$ in the tree $T'_1$ is given by: for any $k \ge 1$,

$$ \begin{aligned} \mathbb{P}[d_1(\mathbf{o}'_1, T'_1) = k-1] &= \mathbb{P}[d_1(\mathbf{o}'_1, T') = k] = \mathbf{P}[d_1(F(\mathbf{o})) = k | \mathbf{o} \in \mathcal{A}] \\ &= \mathbb{P}[X_0 \ge k-1]c^{k-1}, \end{aligned} $$

which proves the first result.
We now show that conditioned on {$d_1(\mathbf{o}'_1, T') = k$}, the descendant subtrees of the children of $\mathbf{o}'_1$ are independent Galton-Watson trees with offspring distribution $\tilde{\pi}$.

On {$d_1(F(\mathbf{o})) = k$}, let $0 = i_k < i_{k-1} < \dots < i_1$ be the children of $F(\mathbf{o})$. Observe that, on the event {$d_1(F(\mathbf{o})) = k$}, for each $1 \le j \le k$, the part of the random walk $(0, S_{i_{j-1}} - S_{i_j}, S_{i_{j-2}} - S_{i_j}, \dots, S_{i_{(j+1)}} - S_{i_j})$ is an excursion set because, by the third part of Lemma 34, $S_{i_{(j+1)}} - S_{i_j} = 1$ and $S_l \le S_{i_{(j+1)}}$ for all $i_{(j+1)} < l \le i_j$. Further, these excursion sets are mutually independent because the times $i_j$, for $1 \le j \le k$, are stopping times. Therefore, for each $j$ chosen above, $(0, S_{i_{j-1}} - S_{i_j}, S_{i_{j-2}} - S_{i_j}, \dots, S_{i_{(j+1)}} - S_{i_j})$ obtained by conditioning on {$d_1(F(\mathbf{o})) = k$} is the conditioned skip-free to the right random walk of $(S_{-n})_{n \ge 0}$ conditioned on $\eta_1 < \infty$ and stopped at $\eta_1$, where $\eta_1 = \min\{n > 0 : S_{-n} = 1\}$ and $-\infty$ if $S_{-n} < 1$ for all $n > 0$. By Lemma 31 (and applying the same to $(S_n)_{n \ge 0}$ and $\eta_{-1}$), the conditioned random walk is an unconditioned random walk $(\hat{S}_n)_{n \ge 0}$ whose increments $(\hat{X}_n)_{n \ge 1}$ have distribution $\mathbb{P}[\hat{X}_1 = k] = \mathbb{P}[X_1 = k]c^k$, for all $k \ge -1$. Moreover, by Lemma 32, the random walk $(\hat{S}_n)_{n \ge 0}$ has negative drift. Therefore, by Proposition 46, the descendant subtree of the children of $\mathbf{o}'_1$ is a Galton-Watson tree with offspring distribution $\tilde{\pi}$. In particular, the mean $m(\tilde{\pi}) < 1$ by Lemma 32. So, $GW(\tilde{\pi})$ is a.s. finite.

□

We now focus on the distribution of the type function associated to a trajectory of the random walk and on the order of the record graph when $\mathbb{E}[X_0] > 0$. We enrich the record graph by assigning the type function as the mark function to the record graph. It will be shown later that the knowledge of the type function and of the record graph of a trajectory is sufficient to construct the negative part of the trajectory. The following theorem shows that the distribution of the record graph with type function as its mark function is a bi-variate ECS ordered marked Eternal Kesten Tree. The latter is characterized by the joint distribution of the mark function restricted to the bush of the root and the distribution of the (unlabelled) bush of the root by Remark 44 and the discussion above it.

**Theorem 55.** Let $0 < \mathbb{E}[X_0] < \infty$. Let $[\mathbf{T}, \mathbf{o}, t]$ be the component of 0 in the record graph of $[\mathbb{Z}, 0, X]$ with $t$, the type function associated to $X$, as the mark function. Let $[\mathbf{T}', \mathbf{o}', t']$ be the marked Family Tree obtained from $[\mathbf{T}, \mathbf{o}, t]$ by conditioning on $\mathbf{o} \in \mathcal{R}$. Then, the distribution of $[\mathbf{T}', \mathbf{o}', t']$
is MEKT($\bar{\pi}$, $\tilde{\pi}$) where the marked bush $[\hat{T}_0, \hat{o}_0, m_0]$ of the root has the following distribution: the offspring distribution of $\hat{o}_0$ is $\bar{\pi}$; the descendant trees of the children of $\hat{o}_0$ are i.i.d. GW($\tilde{\pi}$) and they are independent of $d_1(\hat{o}_0)$ (see Eq. (3.2.8) for the definitions of $\bar{\pi}$ and $\tilde{\pi}$); the mark of every vertex other than $\hat{o}_0$ is -1; the mark of $\hat{o}_0$ is independent of the descendant subtrees of children of $\hat{o}_0$, i.e.,

$$ \mathbb{P}[m_0(\hat{o}_0)|[\hat{T}_0, \hat{o}_0]] = \mathbb{P}[m_0(\hat{o}_0)|d_1(\hat{o}_0)]; $$

and the joint distribution of the mark of $\hat{o}_0$ and $d_1(\hat{o}_0)$ is given by

$$ \mathbb{P}[m_0(\hat{o}_0) = n, d_1(\hat{o}_0) = k] = \mathbb{P}[X_0 = n + k]c^k, \forall n \ge 0, k \ge 0. \quad (3.2.9) $$

*Proof.* Forgetting the marks and the order of vertices of $T'$, it follows from Theorem 54 that $[T', o']$ is the joining of the i.i.d. sequence $([T_i, o_i])_{i \in \mathbb{Z}}$, where $[T_0, o_0]$ has the same distribution as that of $[\hat{T}_0, \hat{o}_0]$, the random Family Tree obtained after forgetting the marks of $V(\hat{T}_0)$. Let $t_i$ be the restriction of the type function $t'$ to $V(T_i)$ for all $i \in \mathbb{Z}$.

Observe that an integer $j$ belongs to the bi-infinite path of $T$ if and only if $t(j) \ge 0$. This follows because, for any $j \in \mathbb{Z}$, its type $t(j)$ is non-negative if and only if $y(n, j) \ge 0$ for all $n < j$. The latter condition is satisfied if and only if $L(j) = -\infty$. By Lemma 24, $L(j) = -\infty$ if and only if $j$ has infinitely many descendants. In view of this, it is sufficient to focus on the type of vertices that lie on the bi-infinite path since the remaining vertices have fixed type -1.

By the above argument, if the sequence of random variables $(t(o_i), d_1(o_i))_{i \in \mathbb{Z}}$ is i.i.d., then the sequence $([T_i, o_i, t_i])_{i \in \mathbb{Z}}$ is i.i.d.. So, the statement of the theorem is proved once we show that

* (Step 1:) the order of $o_i$ is the smallest among the children of $o_{i+1}$, and

* (Step 2:) the sequence $((t(o_i), d_1(o_i))_{i \in \mathbb{Z}})$ is i.i.d. with the common distribution given by Eq. (3.2.9).

Let $o \in \mathcal{O}$ denote the event that the root $o$ belongs to the bi-infinite path of $T$.

**Step 1:** For any $i \in \mathbb{Z}$ with $t(i) \ge 0$, let $l(i) := l_X(i) = \max\{m < i : y(m, i) = t(i)\}$ and $l^n(i) := l^{n-1}(i)$ for all $n > 1$. By Lemma 37, it follows that $l(i)$ is the smallest among the children of $i$.
On the event {$S_n \le 0 \quad \forall n < 0$} (which is equivalent to $\mathbf{o} \in \mathcal{A}$), we have $t(0) \ge 0$. Since $S_m \le S_{l^n(0)}$ for all $m \le l^n(0)$, $n \ge 1$, we have $t(l^n(0)) \ge 0$ for all $n \ge 1$. So, by the above discussion, on the event $\mathbf{o} \in \mathcal{A}$, we get that $R(l^n(0)) = l^{n-1}(0)$ for all $n \ge 1$ (with the notation $l^0(0) = 0$). Moreover, on the same event, the vertices of the bi-infinite F-path of $\mathbf{T}$ are {$l^n(0) : n \ge 1$} $\cup$ {$0$} $\cup$ {$R^m(0) : m \ge 1$}. Since, on the event $\mathbf{o} \in \mathcal{A}$, for any $m \ge 1$, $S_{R^m(0)} - S_n > S_{R^m(0)} - S_{R^{m-1}(0)}$ for all $R^{m-1}(0) < n < R^m(0)$, we have $l(R^m(0)) = R^{m-1}(0)$ (with the notation that $R^0(0) = 0$). Thus, $\mathbf{o}_i$ has the smallest order among the children of $\mathbf{o}_{i+1}$ for all $i \in \mathbb{Z}$. Since the order of $(\mathbf{o}_i)_{i \in \mathbb{Z}}$ characterizes the order on $[\mathbf{T}', \mathbf{o}']$, this completes Step 1.

**Step 2:** Firstly, we compute the joint distribution of $(t(\mathbf{o}_0), d_1(\mathbf{o}_0))$. Note that $d_1(\mathbf{o}_0) = d_1(\mathbf{o}') - 1 = (d_1(\mathbf{o}) - 1)|_{\mathbf{o} \in \mathcal{A}}$. By Lemma 38, we have, for $n \ge 0, k \ge 0$,

$$ \mathbb{P}[\mathbf{o} \in \mathcal{A}, t(\mathbf{o}) = n, d_1(\mathbf{o}) = k + 1] = \mathbb{P}[\mathbf{o} \in \mathcal{A}, X_{-1} = k + n, t(\mathbf{o}) = n]. $$

The right-hand term in the above is equal to

$$ \mathbb{P}[X_{-1} = k + n] \mathbb{P}_{-(k+n)}[S_m = -n \text{ for some } m \le 0] \mathbb{P}_{-n}[S_m \le -n \quad \forall m \le 0], $$

where the second term in the above product is the probability that the skip-free to the right random walk starting from $-(n+k)$ hits $-n$, whereas the third term is the probability that the same random walk starting from $-n$ never hits $-n+1$. Lemma 27 implies that the second term is equal to $c^k$ and the third term is equal to $(1-c)$. Therefore, for $n \ge 0$,

$$ \mathbb{P}[\mathbf{o} \in \mathcal{A}, t(\mathbf{o}) = n, d_1(\mathbf{o}) = k + 1] = \mathbb{P}[X_{-1} = n + k]c^k(1 - c). $$

Since $\mathbb{P}[\mathbf{o} \in \mathcal{A}] = 1-c$, we obtain, for $n \ge 0$,

$$ \begin{aligned} \mathbb{P}[t(\mathbf{o}_0) = n, d_1(\mathbf{o}_0) = k] &= \mathbb{P}[t(\mathbf{o}') = n, d_1(\mathbf{o}') = k + 1] \\ &= \mathbb{P}[t(\mathbf{o}) = n, d_1(\mathbf{o}) = k + 1 | \mathbf{o} \in \mathcal{A}] \\ &= \mathbb{P}[X_{-1} = n + k]c^k. \end{aligned} $$

Secondly, observe that the distribution of $(S_{-m+\mathbf{o}_{-1}} - S_{\mathbf{o}_{-1}})_{m \ge 0}$ conditioned on $\{\mathbf{o} \in \mathcal{A}, t(\mathbf{o}) = n\}$ is the same as that of $(S_{-m})_{m \ge 0}$ conditioned on $\mathbf{o} \in \mathcal{A}$. This follows because

$$ (S_{-m+\mathbf{o}_{-1}} - S_{\mathbf{o}_{-1}})_{m \ge 0} \cap \{\mathbf{o} \in \mathcal{A}, t(\mathbf{o}) = n\} $$
<figure><img src="image_13.png" /><figcaption>Figure 3.5: The conditioned part of the trajectory. An illustration showing that the distribution of $(S_{-m+\mathbf{o}_{-1}} - S_{\mathbf{o}_{-1}})_{m \ge 0}|\{\mathbf{o} \in \mathcal{L}, t(\mathbf{o}) = n\}$ is the same as that of $(S_{-m})_{m \ge 0}|\{\mathbf{o} \in \mathcal{L}\}$ and independent of $(S_{-1}, \dots, S_{\mathbf{o}_{-1}})|\{\mathbf{o} \in \mathcal{L}\}$.</figcaption></figure>

is a conditioned skip-free to the right random walk starting at 0 conditioned on the event that the random walk stays below 1 (see Figure 3.5). Further, this conditioned random walk is independent of $(S_0, S_{-1}, \dots, S_{\mathbf{o}_{-1}})|\mathbf{o} \in \mathcal{L}$ (the process conditioned on the event $\mathbf{o} \in \mathcal{L}$). The joint-distribution of $(t(\mathbf{o}_0), d_1(\mathbf{o}_0))$, however, is a function of $(S_0, S_{-1}, \dots, S_{\mathbf{o}_{-1}})$ Thus, by iteratively applying the above argument to $(S_{-m+\mathbf{o}_{-1}} - S_{\mathbf{o}_{-1}})_{m \ge 0}$ conditioned on $\{\mathbf{o} \in \mathcal{L}, t(\mathbf{o}) = n\}$, we obtain that the sequence of random variables $((t(\mathbf{o}_k), d_1(\mathbf{o}_k)))_{k \le 0}$ is i.i.d.

Thirdly, the distribution of the sequence of random variables $((t(\mathbf{o}_n), d_1(\mathbf{o}_n)))_{n \ge 1}$ (conditioned on $\mathbf{o} \in \mathcal{L}$) is same as that of

$$((S_{R^n(0)} - S_{R^{n-1}(0)}, X_{(R^n(0)-1)} - (S_{R^n(0)} - S_{R^{n-1}(0)})))_{n \ge 1}|\{\mathbf{o} \in \mathcal{L}\}$$

(conditioned on the event $\mathbf{o} \in \mathcal{L}$), with the notation that $R^0(0) = 0$. Note that the latter process has the same distribution as that of unconditioned process $((S_{R^n(0)} - S_{R^{n-1}(0)}, X_{(R^n(0)-1)} - (S_{R^n(0)} - S_{R^{n-1}(0)})))_{n \ge 1}$ as it is independent of the event $\mathbf{o} \in \mathcal{L}$. But $((S_{R^n(0)} - S_{R^{n-1}(0)}, X_{(R^n(0)-1)} - (S_{R^n(0)} - S_{R^{n-1}(0)})))_{n \ge 1}$
$S_{R^{n-1}(0))})_{n \ge 1}$ is i.i.d. by the strong Markov property (since $R(0)$ is a stopping time). Thus, $((t(\mathbf{o}_n), d_1(\mathbf{o}_n)))_{n \ge 1}$ is an i.i.d. sequence.

The proof is complete once we show that

$$ \mathbb{P}[t(\mathbf{o}_1) = n, d_1(\mathbf{o}_1) = k] = \mathbb{P}[t(\mathbf{o}_0) = n, d_1(\mathbf{o}_0) = k], $$

for all $n \ge 0$, $k \ge 0$. For $n \ge 0$, $k \ge 0$,

$$ \begin{aligned} \mathbb{P}[t(\mathbf{o}_1) = n, d_1(\mathbf{o}_1) = k] &= \mathbb{P}[S_{R(0)} = n, X_{(R(0)-1)} - S_{R(0)} = k | \mathbf{o} \in \mathcal{A}] \\ &= \mathbb{P}[S_{R(0)} = n, X_{(R(0)-1)} - S_{R(0)} = k] \quad (\text{by independence}) \\ &= \mathbb{P}[S_{R(0)} = n, X_{(R(0)-1)} = n + k] \\ &= \mathbb{P}[X_0 = n + k]c^k = \mathbb{P}[t(\mathbf{o}_0) = n, d_1(\mathbf{o}_0) = k]. \end{aligned} $$

We used Lemma 28 in the last equation. This concludes the proof. $\square$

<figure><img src="image_14.png" /></figure>

## 3.3 Record foil structure and a measure preserving map

In this section, we define the vertex-shift $R_\perp$ on $\mathbb{Z}, 0, X$], where $X$ is the i.i.d. sequence, such that its induced map $\theta_{R_\perp}$ preserves the distribution of $\mathbb{Z}, 0, X]$. This question is of great interest in the field of stochastic geometry, see [20] for more details.

**R-orthogonal map ($R_\perp$):** Let $\mathbb{Z}, 0, X$] be a network, where $X = (X_n)_{n \in \mathbb{Z}}$ as in Def. 22 and satisfies $\mathbb{E}[X_0] = 0$. Consider the $R$-foliation of $(\mathbb{Z}, X)$ (see Figure 3.6 for an illustration). Observe that the $R$-foliation is the same as the $F$-foliation of $\Psi_R([\mathbb{Z}, 0, X])$, where $F$ is the Parent vertex-shift and $\Psi_R([\mathbb{Z}, 0, X])$ is the connected component of 0 in the $R$-graph of $[\mathbb{Z}, 0, X]$. The order of $\mathbb{Z}$ naturally induces an order on an $R$-foil as the latter is a subset of the former. This order is the same as the RLS order by Lemma 33. This motivates us to define a new map $R_\perp$ on the vertices of $\mathbb{Z}$ in the following way: for an integer $u$, let $R_\perp(u)$ be the smallest integer of the $R$-foil of $u$ which is larger than $u$ (if no such integer exists then define $R_\perp(u) = u$). Since $R$ is a vertex-shift, $R_\perp$ is a vertex-shift.
On the random network $(\mathbb{Z}, X)$, the map $R_{\perp}$ is the same as the following map,

$$i \mapsto \begin{cases} \inf\{k > i : R_X^n(i) = R_X^n(k) \text{ for some } n \ge 1\} & \text{if infimum exists} \\ i & \text{otherwise,} \end{cases}$$

for all $i \in \mathbb{Z}$. In Proposition 56, we show that $R_{\perp}$ is measure preserving.

<figure><img src="image_15.png" /><figcaption>Figure 3.6: Illustration of $R$-foils in $R$-graph (above) and in trajectory (below) when the mean $\mathbb{E}[X_0] = 0$. Vertices that belong to the same $R$-foil are grouped together.</figcaption></figure>

**Proposition 56.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be the sequence of random variables as in Def. 22 and satisfies $\mathbb{E}[X_0] = 0$. The map $R_{\perp}$ preserves the distribution of $X$, i.e., $[\mathbb{Z}, R_{\perp}(0), X] \stackrel{D}{=} [\mathbb{Z}, 0, X]$.

*Proof.* We show that $R_{\perp}$ is bijective and use the fact that bijective maps preserve every unimodular measure (in our case, it is the distribution of $[\mathbb{Z}, 0, X]$). Firstly, we show that a.s. $R_{\perp}(i) \neq i$ for all $i \in \mathbb{Z}$. By Proposition
40, the component of 0 in the record graph of $[\mathbb{Z}, 0, X]$ is of class $I/\mathcal{I}$.
Therefore, all $R$-foils are infinite. In order to show that a.s., $R_⊥(i) > i$ for
all $i \in \mathbb{Z}$, it is enough to show that a.s., there does not exist an $R$-foil with
a largest element (i.e., for each integer $i$, there exists an integer $j$ such that
$j > i$ and $j$ belongs to the $R$-foil of $i$). There can be at most one largest
element in an $R$-foil as the foil is totally ordered. Let $S_T$ be the set of
integers that are the largest in their $R$-foils. Then, $S$ is a covariant subset.
The $R$-foliation $\Pi_X$ of $[\mathbb{Z}, 0, X]$ is a covariant partition. Since every foil
$E \in \Pi$ is infinite, and $E \cap S$ has at most one element, by No Infinite/Finite
inclusion Lemma 12, $E \cap S$ is empty. In particular, $R$-foils do not have any
largest element a.s..

Secondly, since each $R$-foil is totally ordered as it is a subset of $\mathbb{Z}$, the map $R_{\perp}$ is injective. Then, it is bijective almost surely by Proposition 11. Therefore, by Mecke-Thorisson Point Stationarity (Prop. 10) $R_{\perp}$ preserves the distribution of $[\mathbb{Z}, 0, X]$. $\square$

*Remark 57.* In the proof of Proposition 56, we showed that, almost surely, *R*-foils of $[\mathbb{Z}, 0, X]$ do not have the largest vertex (according to RLS order). Similarly, by taking $S_T$ to be set of vertices that are smallest in their *R*-foils, it can be shown that almost surely, none of the *R*-foils has the smallest vertex.

Note that it is not obvious to see that $R_{\perp}$ is a measure preserving map
without using the framework of *R*-foil structure and Mecke-Thorisson point
Stationarity.
# Chapter 4

## Vertex-shift probabilities

In this chapter, we consider vertex-shifts on random rooted networks and study the existence and uniqueness of certain limits induced by them on the random networks. These limits are called vertex-shift probabilities. In Section 4.1, we introduce them and study their properties. Results analogous to those in Section 4.2-4.4 for point-shifts can be found in [6]. Given a random network and a vertex-shift $f$, one obtains the $f$-graph of the random network. The component of the root in the $f$-graph is a random rooted Family Tree. One may study the existence and uniqueness of vertex-shift probabilities of this Family Tree under parent vertex-shift and may wonder if this study helps to understand the vertex-shift probabilities of the random network. This question is addressed by Lemma 61, which plays a role in the next chapter. Under different circumstances, discussed in the later sections, existence of vertex-shift probabilities can be shown. The last section focuses on computing the $F$-probabilities of examples discussed in the previous chapter. Some of these examples will be used in the next chapter to show the existence of a unique vertex-shift probability induced by the record vertex-shift on the network $[\mathbb{Z}, 0, X]$ when $X$ is an i.i.d. sequence as in Def. 22 and satisfy $\mathbb{E}[X_0] \ge 0$.

(In French) Dans ce chapitre, nous considérons les décalages de sommets sur les réseaux aléatoires enracinés et nous étudions l’existence et l’unicité de certaines limites induites par eux sur les réseaux aléatoires. Ces limites sont appelées probabilités de décalage de sommet. Dans la section 4.1, nous les introduisons et étudions leurs propriétés. Des résultats analogues à ceux de la section 4.2-4.4 pour les décalages de points peuvent être trouvés dans [6]. Étant donné un réseau aléatoire et un décalage de
sommet $f$, on obtient le $f$-graphe du réseau aléatoire. La composante de la racine dans le $f$-graphe est un arbre généalogique aléatoire enraciné. On peut étudier l'existence et l'unicité des probabilités de décalage de sommet de cet arbre généalogique associé au le décalage de sommet des parents et se demander si cette étude aide à comprendre les probabilités de décalage de sommet du réseau aléatoire. Cette question est abordée par le lemme 61, qui joue un rôle dans le chapitre suivant. Dans différentes circonstances, discutées dans les sections suivantes, l'existence des probabilités de décalage de sommet peut être montrée. La dernière section se concentre sur le calcul des $F$-probabilités des exemples discutés dans le chapitre précédent. Certains de ces exemples seront utilisés dans le chapitre suivant pour montrer l'existence d'une probabilité unique de décalage de sommet induite par le décalage de sommet des records sur le réseau $[\mathbb{Z}, 0, X]$ lorsque $X$ est une suite i.i.d. comme dans la définition 22 et qui satisfait la condition $\mathbb{E}[X_0] \ge 0$.

## 4.1 Vertex-shift probabilities

Let $[G, o]$ be a random network, i.e., $[G, o]$ is a measurable map from a probability space $(\Omega, \mathcal{F}, \mathbb{P})$ to the space of connected and locally finite rooted networks $\mathcal{G}_*$. Let $\mathcal{P}_0$ be the probability measure on $\mathcal{G}_*$ induced by the random network $[G,o]$. Let $f$ be a vertex-shift. The map $f$ induces a map $\theta_f: \mathcal{G}_* \to \mathcal{G}_*$, defined by $\theta_f([G, o]) = [G, f(o)]$. This determines an action of $\mathbb{N}$ on $\mathcal{G}_*$ defined by the iterates of $\theta_f$, i.e., for each $n \ge 1$, we have the map $\theta_f^n: \mathcal{G}_* \to \mathcal{G}_*$ defined by $\theta_f^n([G, o]) = [G, f^n(o)]$, for all $[G, o] \in \mathcal{G}_*$. The push-forward measures of $\mathcal{P}_0$ under the iterates of $\theta_f$ are called the **vertex-shift probabilities** of $[G, o]$ under $f$.

Let $\mathcal{P}_n$ be the push-forward measure of $\mathcal{P}_0$ under the $n$-th iterate $\theta_f^n$ of $\theta_f$, i.e., $\mathcal{P}_n = (\theta_f^n)_* \mathcal{P}_0$. Therefore, for any measurable subset $A \subset \mathcal{G}_*$, we have

$$ \mathcal{P}_n[A] = (\theta_f^n)_* \mathcal{P}_0[A] = \mathcal{P}_0[\{[G, o] : [G, f^n(o)] \in A\}] = \mathbb{P}[[G, f^n(o)] \in A]. $$

Given a random network $\mathcal{P}_0$, we are interested to study the conditions under which the weak limit points of the sequence $\mathcal{A}_{\mathcal{P}_0} = \{\mathcal{P}_0, \mathcal{P}_0^{f,1}, \mathcal{P}_0^{f,2}, ...\}$ exist. Any probability measure which is a weak limit of $\mathcal{A}_{\mathcal{P}_0}$ is called an $f$-**probability** of the random network $[G, o]$. If the sequence $(\mathcal{P}_0^{f,n})_{n \ge 0}$ (with the understanding that $\mathcal{P}_0 = \mathcal{P}_0^{f,0}$) converges weakly to a probability measure
$\mathcal{P}_0^f$ then, we call $\mathcal{P}_0^f$ **the f-probability** of $\mathcal{P}_0$. Note that a probability measure $\mathcal{P}$ on $\mathcal{G}_*$ is a weak limit point of $\mathcal{A}_{\mathcal{P}_0}$ if and only if there exists a subsequence $\{\mathcal{P}_0^{f,n_k}\}$ such that

$$ \int_{[G,u] \in \mathcal{G}_*} h([G,u]) \mathcal{P}_0^{f,n_k}(d[G,u]) \to \int_{[G,u] \in \mathcal{G}_*} h([G,u]) \mathcal{P}(d[G,u]) $$

for all continuous and bounded functions $h$ on $\mathcal{G}_*$.

In ergodic theory, one studies measure preserving transformations. Seen from this perspective, Mecke's Point Stationarity ([7]) tells that a vertex-shift is unimodular measure preserving if and only if the vertex-shift is bijective almost surely.

**Lemma 58.** Let $[\mathbf{G}, \mathbf{o}]$ be a unimodular network with distribution $\mathcal{P}$ and $f$ be a vertex-shift. Then, the distribution $\mathcal{P}_0^{f,n}$ of $[\mathbf{G}, f^n(\mathbf{o})]$ is absolutely continuous with respect to the initial distribution $\mathcal{P}_0$ with the Radon-Nikodym derivative

$$ \frac{d\mathcal{P}_0^{f,n}}{d\mathcal{P}}[G, \mathbf{o}] = d_n(\mathbf{o}). $$

*Proof.* Let $h$ be a non-negative function on $\mathcal{G}_*$. Then,

$$ \begin{aligned} \mathbb{E}[h([\mathbf{G}, f^n(\mathbf{o})])] &= \mathbb{E}\left[\sum_{u \in V(\mathbf{G})} h([\mathbf{G}, u])\mathbf{1}_{u=f^n(\mathbf{o})}\right] \\ &= \mathbb{E}\left[\sum_{u \in V(\mathbf{G})} h([\mathbf{G}, \mathbf{o}])\mathbf{1}_{\mathbf{o}=f^n(u)}\right] \quad (\text{by unimodularity}) \\ &= \mathbb{E}[h([\mathbf{G}, \mathbf{o}])d_n(\mathbf{o})]. \end{aligned} $$

<figure><img src="image_16.png" /></figure>

Observe that, $d_1(\mathbf{o}) = 1$ a.s. if and only if $f$ is bijective a.s.. Combining this observation with the above lemma, we obtain that a vertex-shift $f$ on a unimodular network $[\mathbf{G}, \mathbf{o}]$ is bijective a.s. if and only if it is measure preserving (i.e., $[\mathbf{G}, f(\mathbf{o})] \stackrel{\mathcal{D}}{=} [\mathbf{G}, \mathbf{o}$]). This is Mecke-Thorisson point stationarity (see Prop. 10).

Lemma 58 implies that the probability measure $\mathcal{P}_0^{f,n}$ is supported on the networks that have $n$-the descendants. The following proposition compares this measure with the measure obtained from $\mathcal{P}_0$ by conditioning on the event that the root has $n$-th descendants.
**Proposition 59.** Let $[G, o]$ be a unimodular network and $\mathcal{P}_0$ be the probability measure induced by $[G, o]$ on $\mathcal{G}_*$. Let $f$ be a vertex-shift and $\{\mathcal{P}_0^{f,n}\}_{n \in \mathbb{N}}$ be the vertex-shift probabilities of $\mathcal{P}_0$ under $f$. Then, for any measurable subset $A$ of $\mathcal{G}_*$,

$$ \mathcal{P}_0^{f,n}[A] = \mathcal{E}_0 \left[ \frac{d_n(o)}{\mathcal{E}_0[d_n(o)|d_n(o)>0]} \mathbf{1}_A \mid d_n(o)>0 \right], $$

where $\mathcal{E}_0$ is the expectation with respect to $\mathcal{P}_0$.

*Proof.* By Lemma 58,

$$ \mathcal{P}_0^{f,n}[A] = \mathcal{E}_0[d_n(o)\mathbf{1}_A] = \mathcal{E}_0[d_n(o)\mathbf{1}_A\mathbf{1}_{d_n(o)>0}]. $$

In particular, for $A = \mathcal{G}_*$, we obtain

$$ \mathcal{P}_0^{f,n}[\mathcal{G}_*] = \mathcal{E}_0[d_n(o)\mathbf{1}_{d_n(o)>0}]. $$

Since $\mathcal{P}_0^{f,n}[\mathcal{G}_*] = 1$, we obtain,

$$ 1 = \mathcal{E}_0[d_n(o)\mathbf{1}_{d_n(o)>0}] = \mathcal{E}_0[d_n(o)|d_n(o)>0]\mathcal{P}_0[d_n(o)>0]. $$

From this, we obtain,

$$ \mathcal{P}_0[d_n(o)>0] = \frac{1}{\mathcal{E}_0[d_n(o)|d_n(o)>0]}. $$

Therefore,

$$ \begin{aligned} \mathcal{P}_0^{f,n}[A] &= \mathcal{E}_0[d_n(o)\mathbf{1}_A\mathbf{1}_{d_n(o)>0}] = \mathcal{E}_0[d_n(o)\mathbf{1}_A|d_n(o)>0]\mathcal{P}_0[d_n(o)>0] \\ &= \mathcal{E}_0\left[\frac{d_n(o)}{\mathcal{E}_0[d_n(o)|d_n(o)>0]}\mathbf{1}_A \mid d_n(o)>0\right]. \end{aligned} $$

□

From the above proposition, $\mathcal{P}_0^{f,n}$ can be seen to be absolutely continuous with respect to the conditional probability $\mathcal{P}_0[.|d_n(o)>0]$.

**Corollary 60.** Consider the conditions mentioned in Proposition 59. If the $f$-probability $\mathcal{P}_0^f$ of $\mathcal{P}_0$ exists, then the following hold:
1. For any bounded and continuous function $h: G_* \to \mathbb{R}$,

$$ \int_{G_*} h([G, o]) d\mathcal{P}_0^f = \lim_{n \to \infty} \int_{G_*} h([G, o]) d_n(o) d\mathcal{P}_0. $$

2. For any measurable subset A of $G_*$ for which $\mathcal{P}_0^{f,n}[A]$ tends to $\mathcal{P}_0^f[A]$ as $n$ tends to infinity,

$$ \mathcal{P}_0^f[A] = \lim_{n \to \infty} \mathcal{E}_0 \left[ \frac{d_n(o)}{\mathcal{E}_0[d_n(o)|d_n(o) > 0]} \mathbf{1}_A \mid d_n(o) > 0 \right]. $$

*Proof.* Follows from the definition of the $f$-probability of $\mathcal{P}_0$. $\square$

<figure><img src="image_17.png" /></figure>

## Forward Backward Lemma

Consider a vertex-shift $f$ and a unimodular random network $[G, o]$. Recall that the map $\theta_f: G_* \to G_*$ takes $[G, o]$ to $[G, f(o)]$, and the forward map $\Psi_f: G_* \to T_*$ takes $[G, o]$ to $[G^f(o), o]$, where $G^f(o)$ is the connected component of $o$ (without any loops) in the $f$-graph $G^f$.

We know that $\Psi_f([G, o])$ is a unimodular Family Tree (Lemma 16). Consider the parent vertex-shift $F$ on this Family Tree. If $\Psi_f([G, o])$ admits an $F$-probability, does it imply the existence and uniqueness of the $f$-probability? The following lemma gives sufficient conditions, under which we obtain a unique $f$-probability from the $F$-probability.

**Lemma 61 (Forward Backward (FB)).** Let $\mathcal{P}$ be a unimodular measure on $G_*$, and $f$ be a vertex-shift. Let $\mathcal{P}_n := \mathcal{P} \circ \theta_f^{-n}, n \ge 1$, be the push-forward measure of $\mathcal{P}$ under the $n$-th iterate of the vertex-shift map $\theta_f$. Let $\mathcal{Q} := \mathcal{P} \circ \Psi_f^{-1}$ and $\forall n \ge 1$, let $\mathcal{Q}_n := \mathcal{Q} \circ \theta_F^{-n}$ be the push-forward measure of $\mathcal{Q}$ under the $n$-th iterate of the Parent vertex-shift map $\theta_F$.

Suppose there exists a map $\Phi_f: T_* \to G_*$ and a probability measure $\mathcal{Q}_F$ on $G'_*$ such that

1. $\Phi_f \circ \Psi_f = I$, $\mathcal{P}$-a.s., where $I$ is the identity map.

2. $\mathcal{Q}_F$ is the $F$-probability of $\mathcal{Q}$, i.e., $\mathcal{Q}_n \to \mathcal{Q}_F$ weakly as $n \to \infty$.

3. $\Phi_f$ is continuous $\mathcal{Q}_F$-a.s..

Then, $\mathcal{Q}_F \circ \Phi_f^{-1}$ is the $f$-probability of $\mathcal{P}$.
*Proof.* Observe that $\Psi_f \circ \theta_f = \theta_F \circ \Psi_f$. Indeed, for any $[G, o] \in \mathcal{G}_*$,

$$ \begin{aligned} \Psi_f \circ \theta_f([G, o]) &= \Psi_f([G, f(o)]) = [G^f(f(o)), f(o)] \\ &= [G^f(o), f(o)] = [G^f(o), F(o)] = \theta_F \circ \Psi_f([G, o]). \end{aligned} $$

The third equality in the above equation follows from the fact that the connected component of $o$ in $G^f$ is the same as that of $f(o)$. Using this inductively we obtain, for any $n \ge 1$,

$$ Q_n = Q \circ \theta_F^{-n} = P \circ \Psi_f^{-1} \circ \theta_F^{-n} = P \circ \theta_f^{-n} \circ \Psi_f^{-1} = P_n \circ \Psi_f^{-1}. $$

We know that $Q$ is unimodular because $P$ is unimodular by Lemma 16. By Lemma 58, $Q_n$ (resp. $P_n$) is absolutely continuous with respect to $Q$ (resp. $P$) for all $n \ge 1$. So, it follows from the first condition that $\Phi_f \circ \Psi_f = I$ $P_n$-a.s.. Using this, we obtain

$$ P_n = P_n \circ (\Phi_f \circ \Psi_f)^{-1} = P_n \circ \Psi_f^{-1} \circ \Phi_f^{-1} = Q_n \circ \Phi_f^{-1}. $$

Since $Q_n$ weakly converges to $Q_F$ and $\Phi_f$ is continuous $Q_F$-a.s., by the Mann-Wald theorem [9], $Q_n \circ \Phi_f^{-1}$ converges weakly to $Q_F \circ \Phi_f^{-1}$ as $n \to \infty$. Thus, $\lim_{n \to \infty} P_n = Q_F \circ \Phi_f^{-1}$. $\square$

In general, the existence of the map $\Phi_f$ is not guaranteed since the $f$-graph may not contain the needed information about the structure of the network. For instance, consider the identity vertex-shift. In this case, the connected components of its $f$-graph are just singletons. So, no information can be obtained from the $f$-graph. We may however attach more information of a network to its $f$-graph as marks. In the case of the record vertex-shift $R$ on the random network $[\mathbb{Z}, 0, X]$ (where $X$ is the sequence of i.i.d. increments of a skip-free to the left random walk), it suffices to consider the order of $\mathbb{Z}$ when $\mathbb{E}[X_0] = 0$ and both the order and the type function $t$ when $\mathbb{E}[X_0] > 0$ as we shall see in the next chapter. Note that, in FB Lemma 61, the backward map $\Phi_f$ may depend on the initial distribution $P$.

## 4.2 Finite orbits and relative compactness

We use the notations of Subsection 2.1. In this section, we are only focused on unlabelled graphs. Recall that $\hat{\mathcal{G}}_*$ denotes the space of rooted graphs.
**Definition 62.** A vertex-shift $f$ is said to have **finite orbits** on a random graph $[G, o]$ if the set $\{[G, f^n(o)], n \in \mathbb{N}\}$ is finite for $-\mathcal{P}_0$-a.s. $[G, o] \in \hat{\mathcal{G}}_*$, where $\mathcal{P}_0$ is the probability measure induced by $[G, o]$.

**Proposition 63.** Let $[G, o]$ be a random graph which induces the probability measure $\mathcal{P}_0$ on $\hat{\mathcal{G}}_*$, $f$ be a vertex-shift and $\mathcal{A}_{\mathcal{P}_0} = \{\mathcal{P}_0^{f,n}, n \in \mathbb{N}\}$ be the vertex-shift probabilities induced by $f$. If $f$ has finite orbits on $[G, o]$ then $\mathcal{A}_{\mathcal{P}_0}$ is relatively compact.

*Proof.* Let $r \ge 1$ be fixed. We show that,

$$ \limsup_{m \to \infty} \mathbb{P}[[G, f^n(o)]_r \notin K_m^r] = 0. \quad (4.2.1) $$

For any fixed $m \ge 1$ and for all $n \ge 1$, the event $\{[G, f^n(o)]_r \in \hat{\mathcal{G}}_* \setminus K_m^r\}$ is a subset of $\{\mathrm{orb}([G, o])_r \cap (\hat{\mathcal{G}}_* \setminus K_m^r) \neq \emptyset\}$, where $\mathrm{orb}([G, o])_r = \{[G, f^n(o)]_r, n \in \mathbb{N}\}$. This implies that

$$ \sup_{n \in \mathbb{N}} \mathbb{P}[[G, f^n(o)]_r \in \hat{\mathcal{G}}_* \setminus K_m^r] \le \mathbb{P}[\mathrm{orb}([G, o])_r \cap (\hat{\mathcal{G}}_* \setminus K_m^r) \ne \emptyset]. $$

Since $K_m^r$ is an increasing sequence in $m$, $\hat{\mathcal{G}}_* \setminus K_m^r$ is a decreasing sequence of sets, which implies that the events $\{\mathrm{orb}([G, o])_r \cap (\hat{\mathcal{G}}_* \setminus K_m^r) \neq \emptyset\}$ are decreasing in $m$. Therefore,

$$ \begin{aligned} & \limsup_{m \to \infty} \mathbb{P}[[G, f^n(o)]_r \in \hat{\mathcal{G}}_* \setminus K_m^r] \\ & \le \lim_{m \to \infty} \mathbb{P}[\mathrm{orb}([G, o])_r \cap (\hat{\mathcal{G}}_* \setminus K_m^r) \ne \emptyset] \\ & = \mathbb{P}\left[\bigcap_{m \in \mathbb{N}} \{\mathrm{orb}([G, o])_r \cap (\hat{\mathcal{G}}_* \setminus K_m^r) \ne \emptyset\}\right]. \end{aligned} $$

But $\mathrm{orb}([G, o])_r$ is a.s. finite. So, it can have non-empty intersection with $\hat{\mathcal{G}}_* \setminus K_m^r$ only for finitely many $m$. Therefore,

$$ \mathbb{P}\left[\bigcap_{m \in \mathbb{N}} \{\mathrm{orb}([G, o])_r \cap (\hat{\mathcal{G}}_* \setminus K_m^r) \neq \emptyset\}\right] = 0, $$

which gives the desired equality in Equation (4.2.1). $\square$

<figure><img src="image_18.png" /></figure>
## 4.3 Evaporation

The n-th vertex-shift-probability measure $P_0^{f,n}$ of a probability measure $P_0$ is supported on the rooted network $[G, o]$ whose root $o$ has n-th descendants, i.e., $d_n(o) > 0$. This leads us to ask, “are all f-probabilities, assuming they exist, supported only on the rooted networks whose root has infinitely many descendants, i.e., $d_n(o) > 0, \forall n \in \mathbb{N}$?”. The answer is affirmative under the sufficient conditions mentioned in Lemma 65 or in Lemma 66.

Let us denote $I := \{[G, o] \in \mathcal{G}_* \text{ such that } d_n(o) > 0 \ \forall n \ge 1\}$, the set of rooted networks whose root has infinitely many descendants. Let $A_m = \{[G, o] \in \mathcal{G}_* \text{ such that } d_m(o) = 0\}$ and $J = \cup_{m \ge 1} A_m$. Then, $J$ is the set of rooted networks whose root has finitely many descendants, and we have

$$J^c = \cap_{m \ge 1} A_m^c = \cap_{m \ge 1} \{[G, o] \in \mathcal{G}_* : d_m(o) > 0\} = I.$$

**Definition 64.** We say that a random network $[G, o]$ evaporates on a vertex-shift $f$ if $\mathbb{P}[[G, o] \in J] = 1$.

**Lemma 65.** Let $f$ be a vertex-shift and $[G, o]$ be a unimodular random network. If $Q$ is an f-probability of $[G, o]$, then $Q[I] = 1$.

*Proof.* For any $n \in \mathbb{N}$, let us denote $B_n = \{[G, o] \in \mathcal{G}_* \text{ such that } d_n(o) > 0\}$. Then $B_n$ is a non-increasing sequence of subsets whose intersection is $I$, i.e., $I = \cap_n B_n$ and $B_n \searrow I$. Therefore,

$$Q[I] = \lim_{n \to \infty} Q[B_n].$$

Since $Q$ is a f-probability, there exists a subsequence $\{P_0^{f,n_k}\}$ of the vertex-shift probabilities $\{P_0^{f,n_k}\}$ that converges weakly to $Q$. Equivalently, for any continuity set $B$, $P_0^{f,n_k}[B] \to Q[B]$ as $k$ tends to infinity.

For all $n \ge 1$, the map $[G, o] \mapsto 1_{d_n(o)>0}$ is continuous on $\mathcal{G}_*$ since for any sequence $([G_m, o_m])_{m \ge 1}$ that converges to a network $[G', o']$ as $m \to \infty$, the sequence $(d_n(o_m))_{m \ge 1}$ is eventually a constant sequence, i.e., there exists $k \ge 1$ such that $d_n(o_m) = d_n(o')$ for all $m \ge k$. Therefore, $B_n$ is a $Q$-continuity set, i.e., $P_0^{f,n_k}[B_n] \to Q[B_n]$ as $k$ tends to infinity. But, notice that $P_0^{f,n_k}[B_{n_k}] = 1$, as it is only supported on the roots that have $n_k$-th descendants, and $B_{n_k} \subseteq B_n$ for all $n_k \ge n$. So, $P_0^{f,n_k}[B_n] = 1$ for all $n_k \ge n$ which implies that $Q[B_n] = 1$. This gives the desired result that $Q[I] = 1$. □
**Lemma 66.** Let $f$ be a vertex-shift and $Q$ be a probability measure on $G_*$ which satisfies Mecke's invariant measure equation, i.e., $(\theta_f)^*Q = Q$. Then $Q[I] = 1$.

*Proof.* We show that $Q[J] = 0$. For any $m \in \mathbb{N}$, let us denote $A_m = \{[G, o] \in G_* : d_m(o) = 0\}$. Since $(\theta_f)_*Q = Q$, we have $(\theta_f^m)_*Q = Q$ for any $m \in \mathbb{N}$. Therefore,

$$Q[A_m] = (\theta_f^m)_*Q[A_m] = Q[(\theta_f^m)^{-1}(A_m)] = Q[[G, o] \in G_* : [G, f^m(o)] \in A_m] = 0 \text{ (since no element of } A_m \text{ has } m\text{-th descendant).}$$

Since $Q[A_m] = 0$ for all $m \in \mathbb{N}$, we have

$$Q[J] = Q\left[\bigcup_{m \in \mathbb{N}} A_m\right] = 0.$$

Therefore, $Q[I] = 1$. $\square$

<figure><img src="image_19.png" /></figure>

**Corollary 67.** Let $[G, o]$ be a random network which evaporates under the action of a vertex-shift $f$. Let $P_0^f$ be a $f$-probability of $P_0$ (the distribution of $[G, o]$) which satisfies Mecke's invariant measure equation, i.e., $(\theta_f)^*P_0^f = P_0^f$. Then, $P_0^f$ is singular with respect to the distribution $P_0$ of $[G, o]$.

*Proof.* Since $[G, o]$ evaporates under $f$, $P_0[J] = 1$. By Lemma 66, $P_0^f[J] = 0$. Therefore, $P_0^f$ is singular with respect to $P_0$. $\square$

<figure><img src="image_20.png" /></figure>

**Corollary 68.** Let $[G, o]$ be a random network which evaporates under the action of a vertex-shift $f$. Assume that the vertex-shift probabilities converge to a unique $f$-probability $P_0^f$ and $\theta_f$ is continuous at $P_0^f$. Then, $P_0^f$ is singular with respect to the distribution $P_0$ of $[G, o]$.

*Proof.* Let $\{P_0^{f,n}\}$ be the vertex-shift-probabilities of $P_0$. Since, for all $n \ge 1$, $(\theta_f)_*P_0^{f,n} = P_0^{f,n+1}$, the sequence $((\theta_f)_*P_0^{f,n})_n$ converges to $P_0^f$. Since $\theta_f$ is continuous at $P_0^f$, we have $(\theta_f)_*P_0^f = P_0^f$. The statement follows from Corollary 67. $\square$

<figure><img src="image_21.png" /></figure>

## 4.4 Periodicity

In the previous Section, we saw conditions under which an $f$-probability is singular with respect to the initial distribution. In this section, we show that
if the vertex-shift is periodic then f-probabilities are absolutely continuous with respect to the initial distribution (see Theorem 72, Remark 74).

**Definition 69.** A vertex-shift $f$ is said to be **periodic** if for all $G$ and $o \in V(G)$, there exists positive integers $k = k(o)$ and $p = p(o)$ such that

$$ \forall n \ge k, f_G^{n+p}(o) = f^n(o). $$

**Definition 70.** A vertex-shift $f$ is said to be **p-periodic** if $p$ does not depend on $[G, o]$.

A vertex $o \in V(G)$ is called a **trap** of $G$ with respect to a vertex-shift $f$ if $f_G(o) = o$. For the identity vertex-shift, every vertex of every network is a trap. Note that, for any vertex-shift $f$, the collection of set of traps of networks $S_G := \{u \in V(G) : f_G(u) = u\}$ is a covariant subset.

**Lemma 71.** If a vertex-shift $f$ is 1-periodic a.s. on a random network $[G, o]$ then the limit $\lim_{n \to \infty} [G, f^n(o)]$ exists and is supported on the traps, i.e., $\mathbb{P}[\lim_{n \to \infty} [G, f^n(o)] \in B] = 1$, where $B := \{[G, o] \in \mathcal{G}_* : o \text{ is a trap}\}$.

*Proof.* Since $f$ is 1-periodic a.s., for $\mathcal{P}_0$-a.s. $[G, o] \in \mathcal{G}_*$ there exists $k = k(o)$ such that

$$ \forall n \ge k, f_G^{n+1}(o) = f_G^n(o) = f_G^k(o). $$

Therefore, $f_G^k(o)$ is a trap. Hence, $\mathbb{P}[\lim_{n \to \infty} [G, f^n(o)] \in B] = 1$. $\square$

In view of the above lemma, for a random network $[G, o]$ and a 1-periodic vertex-shift $f$, let $[\bar{G}, \bar{o}] = \lim_{n \to \infty} [G, f^n(o)]$ and $\mathcal{P}_0^\infty$ be the distribution of $[\bar{G}, \bar{o}]$.

**Theorem 72.** Let $[G, o]$ be a random network, $\mathcal{P}_0$ be its distribution and $f$ be an a.s. 1-periodic vertex-shift on $[G, o]$. Then the f-probability $\mathcal{P}_0^f$ of $\mathcal{P}_0$ exists and $\mathcal{P}_0^f$ is the distribution of $[\bar{G}, \bar{o}]$.

In addition, if $[G, o]$ is unimodular then the f-probability $\mathcal{P}_0^f$ is absolutely continuous with respect to the initial distribution $\mathcal{P}_0$. The limit function $d_\infty(o) = \lim_{n \to \infty} d_n(o)$ exists and it is finite for $\mathcal{P}_0^f$-a.s. $[G, o]$. The Radon-Nikodym derivative of $\mathcal{P}_0^f$ with respect to $\mathcal{P}_0^f$ is given by

$$ \frac{d\mathcal{P}_0^f}{d\mathcal{P}_0}[G, o] = d_\infty(o)\mathbf{1}\{o \text{ is a trap}\}. $$
*Proof.* We prove that $\mathcal{P}_0^\infty$ (the distribution of $[\bar{\mathbf{G}}, \bar{\mathbf{o}}]$) is the $f$-probability of $\mathcal{P}_0$. For any bounded and continuous function $h: \mathcal{G}_* \to \mathbb{R}$,

$$ 
\begin{aligned}
\int_{\mathcal{G}_*} h[G, o] \, d\mathcal{P}_0^\infty &= \mathbb{E}[h[\bar{\mathbf{G}}, \bar{\mathbf{o}}]] = \mathbb{E}[h(\lim_{n \to \infty} [\mathbf{G}, f^n(\mathbf{o})])] \\
&= \mathbb{E}[\lim_{n \to \infty} h[\mathbf{G}, f^n(\mathbf{o})]] \quad (\text{by continuity of } h) \\
&= \lim_{n \to \infty} \mathbb{E}[h([\mathbf{G}, f^n(\mathbf{o})])].
\end{aligned}
$$

In the last step of the above equation, we used the boundedness of $h$ and the dominated convergence theorem. Thus, $\mathcal{P}_0^\infty$ is the $f$-probability of $\mathcal{P}_0$.

We now assume that $[\mathbf{G}, \mathbf{o}]$ is unimodular.

*The limit function $d_\infty$:*

The sequence of functions $(d_n(o))_{n \in \mathbb{N}}$ is non-decreasing on the set of traps due to the following reason. Let $o \in V(G)$ be a trap, and $u \in D_n(o)$ for some $n \in \mathbb{N}$. Then, since $f_G^{n+1}(u) = f_G^n(u) = o$, we have $D_n(o) \subseteq D_{n+1}(o)$ and $d_n(o) \le d_{n+1}(o)$.

Since the random network $[\bar{\mathbf{G}}, \bar{\mathbf{o}}]$ is supported on the traps, the random variable

$$ d_\infty([\bar{\mathbf{G}}, \bar{\mathbf{o}}]) = \lim_{n \to \infty} d_n([\bar{\mathbf{G}}, \bar{\mathbf{o}}]) $$

exists a.s.

As for the finiteness of the random variable $d_\infty([\bar{\mathbf{G}}, \bar{\mathbf{o}}])$, let

$$ \mathcal{A} := \{[G, o] \in \mathcal{G}_* : f_G^{n+1}(o) = f_G^n(o) \text{ for some } n = n(o) \in \mathbb{N}\}. $$

Then, for any $[G, o] \in \mathcal{A}$, the root $o$ has finitely many ancestors in the $f$-graph. Therefore, by the unimodular classification theorem ([7]), the connected component $C(o)$ of $o$ is of type $\mathcal{F}/\mathcal{F}$ as it is the only case in which vertices have finitely many ancestors. This implies that $C(o)$ is finite. But the connected component of $f^{n(o)}(o)$ in the $f$-graph is also $C(o)$ and $f^{n(o)}(o)$ is a trap. Thus, $d_\infty(\lim_{m \to \infty} [G, f^m(o)]) = \#D(f^{n(o)}(o)) = \#C(o)$ is finite.

*Radon-Nikodym derivation of $\mathcal{P}_0^f$ with respect to $\mathcal{P}_0$:*
Let $h: \mathcal{G}_* \to \mathbb{R}_{\ge 0}$ be any measurable function. Then,

$$
\begin{align*}
\int_{\mathcal{G}_*} h([G, o]) \, d\mathcal{P}_0^f &= \mathbb{E}[h([\bar{G}, \bar{o}])] = \mathbb{E} \left[ \sum_{u \in V(\bar{G})} h([\bar{G}, u]) \mathbf{1}\{\bar{o} = u\} \right] \\
&= \mathbb{E} \left[ \sum_{u \in V(\bar{G})} h([\bar{G}, u]) \mathbf{1}\{f^{n(o)}(\bar{o}) = u\} \mathbf{1}\{f^{n(o)}(\bar{o}) \text{ is a trap}\} \right] \\
&= \mathbb{E} \left[ \sum_{u \in V(\bar{G})} h([\bar{G}, o]) \mathbf{1}\{f^{n(u)}(u) = o\} \mathbf{1}\{f^{n(u)}(u) \text{ is a trap}\} \right] \tag{4.4.1} \\
&= \mathbb{E}[h([\bar{G}, o]) \#D(o) \mathbf{1}\{o \text{ is a trap}\}] \\
&= \mathbb{E}[h([\bar{G}, o]) \lim_{m \to \infty} d_m(o) \mathbf{1}\{o \text{ is a trap}\}] \\
&= \mathbb{E}[h([\bar{G}, o]) d_\infty(o) \mathbf{1}\{o \text{ is a trap}\}].
\end{align*}
$$

We used unimodularity to get Eq. (4.4.1). Thus, we obtain the Radon-Nikodym derivative of $\mathcal{P}_0^f$ with respect to $\mathcal{P}_0$,

$$
\frac{d\mathcal{P}_0^f}{d\mathcal{P}_0}[G, o] = d_\infty(o) \mathbf{1}\{o \text{ is a trap}\}.
$$

<figure><img src="image_22.png" /></figure>

Remark 73. From the proof of Theorem 72, it follows that $d_\infty(o) = \#D(o)$.

Remark 74. Let $p$ be a positive integer. If a vertex-shift $f$ is a.s. $p$-periodic on a random network $[\mathbf{G}, \mathbf{o}]$ then for $\mathcal{P}_0$-a.s. $[G, o] \in \mathcal{G}_*$, there exists a $k = k(o) \in \mathbb{N}$ such that $f_G^{n+p}(o) = f_G^n(o)$ for all $n \ge k$. In particular, $f_G^{np+i+p}(o) = f_G^{np+i}(o)$ for all $n \ge k$ and for any $i = 0, 1, \dots, p-1$. So, the vertex-shift $f^p$ is a.s. 1-periodic on the random networks $\{[\mathbf{G}, \mathbf{o}], [\mathbf{G}, f(\mathbf{o})], \dots, [\mathbf{G}, f^{p-1}(\mathbf{o})]\}$. By Theorem 72, for each $i = 0, 1, \dots, p-1$, $[\mathbf{G}, f^i(\mathbf{o})]$ has unique $f^p$-probability. So, $[\mathbf{G}, \mathbf{o}]$ can have at most $p$ $f$-probabilities. In addition, if $[\mathbf{G}, \mathbf{o}]$ is unimodular, then all of its $f$-probabilities are absolutely continuous with respect to $\mathcal{P}_0$ by Lemma 58 and by Theorem 72.

4.5 Examples and their F-probabilities

In this section, we compute the *F*-probabilities of some Family Trees. A
few remarks are given in the respective subsections about the application
of results of the previous section to the examples studied here. Among the examples, the Canopy tree and the unimodular Eternal Galton-Watson Tree are taken from [7]. We have already introduced two new unimodular Family Trees namely, the typically rooted Galton-Watson Tree and the unimodularised bi-variate Eternal Kesten Tree. The F-probability of the latter is shown to be the bi-variate Eternal Kesten Tree in Proposition 82. We introduce Eternal Kesten Tree, a special instance of bi-variate Eternal Kesten Tree, and prove that it is the F-probability of the Eternal Galton-Watson Tree (in Proposition 80). We also introduce the size-biased Galton-Watson Tree, and show that it is the F-probability of the typically rooted Galton-Watson Tree.

The results from this section together with FB Lemma 61 will be used in the next chapter to compute the R-probability.

## Canopy tree

The Canopy tree with the number of children d, $C_d$ is an Eternal Family Tree with vertices partitioned into infinitely many levels $L_0, L_1, L_2, \dots$ such that, for any $i > 0$, every vertex v in $L_i$ has d children in $L_{i-1}$, and a unique parent in $L_{i+1}$; the vertices of $L_0$ do not have any children but each vertex of $L_0$ has a unique parent in $L_1$. The tree is deterministic, but the root is chosen randomly to obtain a random rooted Family Tree $[C_d, \mathbf{o}]$.

Since, for any two vertices u, v of the same level $L_i$ (for any $i \ge 0$), the equivalent class of $(C_d, u)$ and $(C_d, v)$ are one and the same, the set of probabilities $\{p_i = \mathbb{P}[\mathbf{o} \in L_i] : i \ge 1\}$ fully characterizes the distribution of $[C_d, \mathbf{o}]$. Thus, in order to describe the distribution of the random root $\mathbf{o}$ of $C_d$, it is enough to define $\mathbb{P}[\mathbf{o} \in L_i]$. Let

$$p_i = \mathbb{P}[\mathbf{o} \in L_i], \quad i \ge 0.$$

Let $T_{d+1}$ be the directed tree whose vertices have one out-degree and d in-degree, i.e., $T_{d+1}$ is the d+1 regular tree with one selected end. Consider the parent vertex-shift on $C_d$. In Proposition 76, we show that the randomly rooted Canopy tree $[C_d, \mathbf{o}]$ has a unique F-probability $T_{d+1}$.

Recall the notations of Section 2.1 of Chapter 2.

**Lemma 75.** Let u be a vertex of the canopy tree $C_d$ that belongs to level $L_i$. Then

$$((C_d, u)_r, u) \sim ((T_{d+1}, v)_r, v) \text{ for all } 0 \le r \le i.$$
*Proof.* We prove the lemma by induction on $r$. For $r=0$, $((C_d, u)_r, u) \sim ((T_{d+1}, v)_r, v)$. Let us assume that the statement is true for $r-1 \ge 0$ and let $\rho: (C_d, u)_{r-1} \to (T_{d+1}, v)_{r-1}$ be a network isomorphism such that $\rho(u) = v$. To show $((C_d, u)_r, u) \sim ((T_{d+1}, v)_r, v)$, it is enough to extend the isomorphism $\rho$ to every vertex in $(C_d, u)_r \setminus (C_d, u)_{r-1}$.

If $w \in (C_d, u)_r \setminus (C_d, u)_{r-1}$ then $w$ can only be one of the three cases: an ancestor of $u$, or a descendant of $u$, or a descendant of an ancestor of $u$.

* If $w$ is an ancestor of $u$ then $w = F^r(u)$ and $F^{r-1}(u) \in (C_d, u)_{r-1}$. We extend $\rho$ to $w$ by assigning $\rho(w)$ to the parent of $\rho(F^{r-1}(u))$ in $T_{d+1}$.

* If $w$ is a descendant either of $u$ or, of an ancestor of $u$ then $F(w) \in (C_d, u)_{r-1}$. As $i \ge r$, the vertex $F(w) \notin L_0$. Therefore, $F(w)$ has $d$-children and we can obtain a bijection between the children of $F(w)$ and the children of $\rho(F(w))$. We extend $\rho$ to the children of $F(w)$ by using this bijection.

□

Let $[C_d, u_i]$ be the equivalence class of any $u_i$ vertex in $L_i$. By the above lemma, the distance between $[C_D, u_i]$ and $[T_{d+1}, v]$ in $\mathcal{T}_*$ is bounded above by $\frac{1}{2^i}$. Thus, $[C_d, u_i] \to [T_{d+1}, v]$ in $\mathcal{G}_*$ as $i$ tends to infinity. We now show that the $F$-probability of a randomly rooted Canopy tree $[C_d, \mathbf{o}]$ is $[T_{d+1}, v]$, for any vertex $v$ of $T_{d+1}$.

**Proposition 76.** Let $[C_d, \mathbf{o}]$ be the canopy tree with $\mathbf{o}$ the root $\mathbf{o}$ chosen randomly and $[C_d, \mathbf{o}_i] \in \mathcal{T}_*$ be the canopy tree with random root $\mathbf{o}_i$, where $\mathbf{o}_i = F^i(\mathbf{o})$, $i \ge 0$. Then $[C_d, \mathbf{o}_i]$ converges in distribution to $[T_{d+1}, v]$ as $i \to \infty$, for any vertex $v$ of $T_{d+1}$.

*Proof.* Let $g$ be a continuous bounded function on $\mathcal{G}_*$, $u_k \in L_k$ be a vertex of $C_d$, $g_k := g([C_d, u_k])$, and $a := g([T_{d+1}, v])$. As $[C_d, u_k] \to [T_d, v]$ in $\mathcal{G}_*$ when $k$ tends to infinity, and by the continuity of the function $g$, $g_k$ converges to $a$.

The probability, $\mathbb{P}[\mathbf{o}_i \in L_k] = \mathbb{P}[F^i(\mathbf{o}) \in L_k] = \mathbb{P}[\mathbf{o} \in L_{k-i}]$ is given by

$$ \mathbb{P}[\mathbf{o}_i \in L_k] = \begin{cases} 0 & k-i < 0 \\ p_{k-i} & k-i \ge 0. \end{cases} $$
and we have

$$ \mathbb{E}[g([C_d, \mathbf{o}_i])] = \sum_{k=0}^{\infty} g([C_d, u_k]) \mathbb{P}[\mathbf{o}_i \in L_k] = \sum_{k=i}^{\infty} g_k p_{k-i}. $$

Since $g_i$ converges to $a$ as $i$ tends to infinity, given $\epsilon > 0$ there exists $N$ such that for all $i \ge N$, $|g_i - a| < \epsilon$. Therefore, for such $i$,

$$ \begin{aligned} |\mathbb{E}[g([C_d, \mathbf{o}_i])] - g([T_{d+1}, v])| &= \left| \sum_{k=i}^{\infty} g_k p_{k-i} - a \right| = |p_0(g_i - a) + p_1(g_{i+1} - a) + \dots| \\ &\le p_0|g_i - a| + p_1|g_{i+1} - a| + \dots + p_k|g_{i+k} - a| + \dots \\ &< \epsilon \left( \sum_{k=0}^{\infty} p_k \right) < \epsilon. \end{aligned} $$

□

*Remark 77.* Observe that the map $\theta_F$ induced by the parent vertex-shift $F$ is continuous on $\mathcal{T}_*$. It is also clear that the randomly rooted Canopy tree $[C_d, \mathbf{o}]$ evaporates under $F$ as the root $\mathbf{o}$ has a.s. finitely many descendants. Therefore, by Corollary 68, the $F$-probability of $[C_d, \mathbf{o}]$ is singular with respect to the distribution of $[C_d, \mathbf{o}]$. This is indeed true since the directed regular tree $[T_{d+1}, u]$ has infinitely many descendants.

### Typically rooted Galton-Watson Tree (TGWT)

Let $\pi$ be a probability distribution on $\{0, 1, 2, \dots\}$ with mean $m(\pi) < 1$ and $[\mathbf{T}', \mathbf{o}']$ be a random Family Tree distributed as $GW(\pi)$. The **Size-Biased Galton-Watson Tree** with offspring distribution $\pi$, denoted as $SBGW(\pi)$ is a random Family Tree $[\bar{\mathbf{T}}, \bar{\mathbf{o}}]$ whose distribution is given by:

$$ \mathbb{P}[[\bar{\mathbf{T}}, \bar{\mathbf{o}}] \in A] = \frac{1}{\mathbb{E}[\#V(\mathbf{T}')]} \mathbb{E}[\#V(\mathbf{T}') \mathbf{1}_A([\mathbf{T}', \mathbf{o}'])], \quad (4.5.1) $$

for every measurable set $A$. Note that $\mathbb{E}[\#V(\mathbf{T})]$ is finite since $m(\pi) < 1$.

We show that the $F$-probability of $TGWT(\pi)$ is $SBGW(\pi)$ using Theorem 72.

**Proposition 78.** Let $m(\pi) < 1$. Then, the $F$-probability of $TGWT(\pi)$ is $SBGW(\pi)$.
*Proof.* Let $[\mathbf{T}, \mathbf{o}]$ be a random Family Tree distributed as $TGWT(\pi)$ and let $[\mathbf{T}', \mathbf{o}']$ be a random Family Tree distributed as $GW(\pi)$. Since, the root $\mathbf{o}$ has a.s. finitely many ancestors, $[\mathbf{T}, \mathbf{o}]$ is a.s. 1-periodic with respect to the parent vertex-shift $F$. By Theorem 72, the $F$-probability of $[\mathbf{T}, \mathbf{o}]$ exists. Let $[\bar{\mathbf{T}}, \bar{\mathbf{o}}]$ be the $F$-probability of $[\mathbf{T}, \mathbf{o}]$. Since $TGWT(\pi)$ is unimodular (see Proposition 52), by Theorem 72, we have

$$ \mathbb{P}[[\bar{\mathbf{T}}, \bar{\mathbf{o}}] \in A] = \mathbb{E}[\#V(\mathbf{T}) \mathbf{1}\{\mathbf{o} \text{ is a trap } \} \mathbf{1}_A([\mathbf{T}, \mathbf{o}])], $$

for every measurable set $A$. By Proposition 50, we have

$$ \mathbb{P}[[\mathbf{T}, \mathbf{o}] \in A] = \frac{1}{\mathbb{E}[\#V(\mathbf{T}')]} \mathbb{E} \left[ \sum_{u \in V(\mathbf{T}')} \mathbf{1}_A([\mathbf{T}', u]) \right], $$

for every measurable set $A$. Combining the above two equations, we obtain

$$ \begin{aligned} \mathbb{P}[[\bar{\mathbf{T}}, \bar{\mathbf{o}}] \in A] &= \frac{1}{\mathbb{E}[\#V(\mathbf{T}')]} \mathbb{E} \left[ \#V(\mathbf{T}') \sum_{u \in V(\mathbf{T}')} \mathbf{1}\{\mathbf{u} \text{ is a trap } \} \mathbf{1}_A([\mathbf{T}', \mathbf{u}]) \right] \\ &= \frac{1}{\mathbb{E}[\#V(\mathbf{T}')]} \mathbb{E}[\#V(\mathbf{T}') \mathbf{1}_A([\mathbf{T}', \mathbf{o}'])], \end{aligned} $$

for every measurable set $A$. The last step follows since the root is the only vertex that does not have a parent and thus the statement is proved. $\square$

## Unimodular Eternal Galton-Watson Tree

In the following, we introduce a new EFT called the Eternal Kesten Tree (EKT) and show that it is the $F$-probability of the unimodular Eternal Galton-Watson Tree. The EKT is an eternal version of Kesten's tree which was defined in [1].

Let $[\mathbf{T}, \mathbf{o}]$ be a rooted Family Tree. A vertex of $\mathbf{T}$ is called **common**($\pi$) if its offspring distribution is $\pi$ and all of its descendants reproduce independently with offspring distribution $\pi$. A vertex of $\mathbf{T}$ is **special**($\pi$) if it satisfies the following three properties: (1) its offspring distribution is $\hat{\pi}$ (the size-biased distribution of $\pi$), (2) all of its descendants reproduce independently, (3) for all $n \ge 1$, exactly one of its $n$-th descendants reproduces with distribution $\hat{\pi}$ and the rest (if any) are common($\pi$).

**The ordered Eternal Kesten Tree:** Let $\pi$ be a probability distribution on $\{0, 1, 2, \dots\}$ with mean $m(\pi) = 1$. The ordered Eternal Kesten Tree with
offspring distribution $\pi$, denoted as $EKT(\pi)$, is defined as follows: it is a rooted Eternal Family Tree $[S, u]$ containing two types of individuals (vertices) namely common($\pi$) and special($\pi$). It has a unique bi-infinite F-path $(o_n)_{n \in \mathbb{Z}}$ of special($\pi$) individuals with $o_0 = u$, i.e., $\forall n \in \mathbb{Z}$, $o_n$ is a parent of $o_{n-1}$ and $o_{n-1}$ is the special($\pi$) child of $o_n$. All the remaining vertices are common($\pi$). The order among the children of every vertex is uniform. All individuals reproduce independently.

The relation between the Eternal Kesten Tree and the bi-variate Eternal Kesten Tree (defined in Subsection 3.2) is as follows: Let $\pi$ be a probability distribution on $\{0, 1, 2, \dots\}$ with mean $m(\pi) = 1$, $\hat{\pi}$ be the size-biased distribution of $\pi$, and $\alpha$ be the distribution given by $\alpha(k) = \hat{\pi}(k+1)$ for all $k \ge 0$. Then, the unordered $EKT(\pi)$ is the same as the unordered $EKT(\alpha, \pi)$, and the ordered $EKT(\pi)$ is obtained by taking the uniform order on $EKT(\alpha, \pi)$.

<figure><img src="image_23.png" /><figcaption>Figure 4.1: The Eternal Kesten tree with distribution $\pi$. Notation: $GW(\pi)$ denotes Galton-Watson tree; $\hat{\pi}$ is the size-biased distribution of $\pi$.</figcaption></figure>

*Remark 79.* For all $n \in \mathbb{Z}$, the descendant trees of siblings of $o_n$ are independent critical Galton-Watson trees with offspring distribution $\pi$, and thus they are all finite trees. Therefore, every realization of $EKT(\pi)$ has
a unique bi-infinite F-path passing through the root. See Figure 4.1 for an illustration.

We follow the notations of Section 2.1, Chapter 2.

**Proposition 80.** The F-probability of the unimodular (ordered) Eternal Galton-Watson Tree [T, o] with offspring distribution π is the (ordered) Eternal Kesten Tree [S, u] with distribution EKT(π).

*Proof.* Let $r > 0$, and $u_{-r}, u_{-r+1}, \dots, u_{-1}$ be the special descendants of $u_0 = u$ in S. Note that $F^n(o)$ has at least one k-th descendant, for all $1 \le k \le n$. For all $n > r$, the distributions of $[T, F^n(o)]_r$ and $[S, u]_r$ are the same. Indeed, the offspring distribution of $F^n(o)$ is the same as that of u which is $\hat{\pi}$. The special child of u has the same offspring distribution $\hat{\pi}$ as that of $F^{n-1}(o)$ and the remaining other children of u follow the offspring distribution $\pi$. By induction, $F^{n-r+1}(o)$ has the same distribution as that of the special $n-r+1$-th descendant of u. The same is true for the remaining vertices of $[T, F^n(o)]_r$ and $[S, u]_r$. Therefore,

$$[S, u] \stackrel{D}{=} \lim_{n \to \infty} [T, F^n(o)].$$

In addition, if $[T, o]$ is an ordered EGWT($\pi$) and $[S, u]$ is an ordered EKT($\pi$), then the order of $F^i(o)$ is uniform among the children of $F^{i+1}(o)$ for $n-r+1 \le i \le n-1$, which has the same distribution as the order of $u_{i-n}$ among the children of $u_{i-n+1}$. The same is true for the order of the remaining vertices of $[T, F^n(o)]_r$ and $[S, u]_r$. Thus, the F-probability of the unimodular ordered EGWT($\pi$) is the ordered EKT($\pi$). $\square$

*Remark 81.* Consider a realization of EGWT($\pi$), where $\pi$ has mean $m(\pi) = 1$ and satisfies $\pi(1) < 1$. Then, its root has finitely many descendants, i.e., EGWT($\pi$) evaporates under the parent vertex-shift. In contrast, the root of a realization of EKT($\pi$) has infinitely many descendants. Therefore, EKT($\pi$) is singular with respect to EGWT($\pi$). This is another instance where the F-probability is singular with respect to the initial distribution. This fact can also be inferred from Lemma 66 and Corollary 68, since the parent vertex-shift is continuous on $T_*$.
Unimodularised bi-variate marked Eternal Kesten Tree

Let $\alpha, \beta$ be probability distributions on $\{0, 1, 2, \dots\}$ such that their means satisfy $m(\alpha) < \infty$ and $m(\beta) < 1$. Let $[\mathbf{T}', \mathbf{o}', Z']$ be a random marked Family Tree whose distribution is $\text{MEKT}(\alpha, \beta)$, where $Z'$ is a mark. Let $[\mathbf{T}', \mathbf{o}', Z']$ be the joining of $([\mathbf{T}_i, \mathbf{o}_i, Z_i])_{i \in \mathbb{Z}}$, the i.i.d. sequence of random marked Family Trees defined in Remark 43.

Let $[\mathbf{T}, \mathbf{o}, Z]$ denote the size-biased joining of $([\mathbf{T}_i, \mathbf{o}_i, Z_i])_{i \in \mathbb{Z}}$. Recall that the distribution of $[\mathbf{T}, \mathbf{o}, Z]$ is given by:

$$ \mathbb{P}[[\mathbf{T}, \mathbf{o}, Z] \in A] = \frac{\mathbb{E}[\sum_{u \in V(T_0)} \mathbf{1}_A([\mathbf{T}', u, Z'])]}{\mathbb{E}[\#V(T_0)]}, \quad (4.5.2) $$

for any measurable set $A$. Observe that $\mathbb{E}[\#V(T_0)] < \infty$ because $\beta < 1$, and the descendant trees of the children of $\mathbf{o}_0$ (in $T_0$) are subcritical Galton-Watson trees.

Recall that $\hat{T}_*$ denotes the space of rooted marked Family Trees. For any $[T, u, z] \in \hat{T}_*$ that has a unique bi-infinite F-path $\mathcal{L}(T)$, for any $w \in V(T)$, let

$$ M(w) := \inf\{n \ge 0 : F^n(w) \in \mathcal{L}(T)\}, $$

with the convention that $F^0(w) = w$ and let $w^* = F^{M(w)}(w)$ be the smallest ancestor of $w$ that lies on the unique bi-infinite F-path of $T$. Let $[T, u, z]_r$ denote the subtree induced by the vertices of $T$ that are at a graph distance of at most $r$ from $u$ and with the mark function restricted to these vertices.

**Proposition 82.** The F-probability of the unimodularized MEKT$(\alpha, \beta)$ is MEKT$(\alpha, \beta)$.

*Proof.* Fix $r > 0$. Let $A$ be a measurable subset of $\hat{T}_*$, and let $n > r$. Then,

$$ \mathbb{P}[[\mathbf{T}, F^n(\mathbf{o}), Z]_r \in A] = \mathbb{P}[[\mathbf{T}, F^n(\mathbf{o}), Z]_r \in A, M(\mathbf{o}) < n - r] + \mathbb{P}[[\mathbf{T}, F^n(\mathbf{o}), Z]_r \in A, M(\mathbf{o}) \ge n - r]. $$

The second sum is bounded by $\mathbb{P}[M(\mathbf{o}) \ge n - r]$. As $n \to \infty$, $\mathbb{P}[M(\mathbf{o}) \ge n - r] \to 0$ since $M(\mathbf{o})$ is a.s. finite, which follows from the finiteness of the tree $T_0$. Therefore, the second sum tends to 0 as $n \to \infty$.