# Genealogies of records of stochastic processes with stationary increments as
unimodular trees

François<EMAIL_ADDRESS>[ Bharath Roy
<EMAIL_ADDRESS>[ INRIA/ENS - PSL, Paris
presep=, ]e1,e2

###### Abstract

Consider a stationary sequence $X=(X_{n})$ of integer-valued random variables
with mean $m\in[-\infty,\infty]$. Let $S=(S_{n})$ be the stochastic process
with increments $X$ and such that $S_{0}=0$. For each time $i$, draw an edge
from $(i,S_{i})$ to $(j,S_{j})$, where $j>i$ is the smallest integer such that
$S_{j}\geq S_{i}$, if such a $j$ exists. This defines the record graph of $X$.

It is shown that if $X$ is ergodic, then its record graph exhibits the
following phase transitions when $m$ ranges from $-\infty$ to $\infty$. For
$m<0$, the record graph has infinitely many connected components which are all
finite trees. At $m=0$, it is either a one-ended tree or a two-ended tree. For
$m>0$, it is a two-ended tree.

The distribution of the component of $0$ in the record graph is analyzed when
$X$ is an i.i.d. sequence of random variables whose common distribution is
supported on $\\{-1,0,1,\ldots\\}$, making $S$ a skip-free to the left random
walk. For this random walk, if $m<0$, then the component of $0$ is a
unimodular typically re-rooted Galton-Watson Tree. If $m=0$, then the record
graph rooted at $0$ is a one-ended unimodular random tree, specifically, it is
a unimodular Eternal Galton-Watson Tree. If $m>0$, then the record graph
rooted at $0$ is a unimodularised bi-variate Eternal Kesten Tree.

A unimodular random directed tree is said to be record representable if it is
the component of $0$ in the record graph of some stationary sequence. It is
shown that every infinite unimodular ordered directed tree with a unique
succession line is record representable. In particular, every one-ended
unimodular ordered directed tree has a unique succession line and is thus
record representable.

60G10,

60C05,

60J80,

05C80,

unimodularity,

skip-free to the left random walks,

Galton-Watson Trees,

depth first search order,

###### keywords:

[class=MSC]

###### keywords:

,

##  1 Introduction

Consider a stationary sequence $X=(X_{n})_{n\in\mathbb{Z}}$ of integer-valued
random variables with common mean $m$ that exists and lies in
$[-\infty,\infty]$. Let $S=(S_{n})_{n\in\mathbb{Z}}$ be the stochastic process
starting at $0$ with increments $X$ namely,

$S_{0}=0,\,S_{n}=\sum_{k=0}^{n-1}X_{k},\,n>0\text{ and
}S_{n}=-\sum_{k=n}^{-1}X_{k},\,n<0.$ (1)

For each integer $i$, the _record_ (epoch) $R_{X}(i)$ of $i$ is given by

$R_{X}(i)=\begin{cases}\inf\\{n>i:S_{n}\geq S_{i}\\}\text{ if the infimum
exists,}\\\ i\text{ otherwise.}\end{cases}$ (2)

Construct the _record graph_ $\mathbb{Z}^{R}_{X}$ of $X$ on the vertex set
$\mathbb{Z}$ by drawing a directed edge from each integer $i$ to its record
$R_{X}(i)$ (see Fig. 1). Remove all the self loops, namely all directed edges
$i$ to $i$, if there are any. The record graph thus obtained is a random
directed graph, with $\mathbb{Z}$ as the vertex set and where the directed
edges are random. Let $T$ be the connected component of $0$ in the record
graph $\mathbb{Z}^{R}_{X}$, i.e., the subgraph induced on the subset of
integers $j$ such that there is either a directed path from $j$ to $0$ or from
$0$ to $j$. In other words, $T$ is the connected component of $0$ in the
undirected graph of $\mathbb{Z}^{R}_{X}$. The focus of this paper is on the
following two objects: the random directed graph $\mathbb{Z}^{R}_{X}$ and the
random rooted directed graph $[T,0]$, with $0$ as the root. In particular, the
following three questions are addressed:

  1. (Q1)

When is the record graph connected, and more generally how do the structural
properties of the record graph depend on the distribution of $X$?

  2. (Q2)

Are there instances of $X$ for which the distribution of $[T,0]$ can be
computed explicitly?

  3. (Q3)

When is a random rooted graph the component of $0$ in the record graph of a
stationary sequence?

Figure 1: (A) An illustration of the trajectory
$\\{(n,S_{n}):n\in\mathbb{Z}\\}$ and the record map. (B) The component of $0$
in the record graph.

The connectivity of the record graph depends only on the mean of the increment
$X_{0}$. Indeed, it is shown in the paper that the record graph is connected
(in which case $T$ is infinite) if and only if the mean is non-negative. Since
$R_{X}(i)\geq i$ for all $i\in\mathbb{Z}$ and since self loops if any were
removed, the record graph does not contain any cycle. Under the assumption
that $X$ is a stationary and ergodic, it is shown that $[T,0]$ exhibits a
phase transition at $0$ when the mean is varied in $[-\infty,\infty]$. In the
regions $[-\infty,0)$ and $(0,\infty]$, $T$ is a finite directed tree and a
two-ended directed tree, respectively. At $\mathbb{E}[X_{0}]=0$, $T$ is either
a two-ended or a one-ended directed tree.

The distribution of $[T,0]$ is explicitly computed when
$(X_{n})_{n\in\mathbb{Z}}$ is an i.i.d. sequence of random variables such that
their common mean exists, and the support of $X_{n}$ is
$\\{-1,0,1,2,\cdots\\}$ and non-degenerate, for all $n\in\mathbb{Z}$.

Concenring the last question on record representation of graphs, it is shown
that under a mild assumption, certain classes of ordered directed trees can be
represented as the component of $0$ in the record graph of some stationary
sequence. This includes the infinite trees associated to virtually all
dynamics on ordered networks. These results are now stated more precisely
after introducing some terminology from [5].

###  1.1 Some terminology

Informally, a random rooted graph is called _unimodular_ if for all the
covariant ways of sending mass, the average total mass sent from the root to
every vertex is the same as the average total mass received at the root from
every vertex (see Def. 2).

A _vertex-shift_ $f$ is a covariant collection of maps $\\{f_{G}:V(G)\to
V(G)\\}$ that are indexed by graphs and that satisfy a measurability condition
(see Def. 3). The map $f_{G}$ associated to a graph $G$ gives a deterministic
dynamic on the graph, i.e., it describes how to move from one vertex to the
next vertex on the graph according to the dynamic. One such example is the
record map given in Eq. (2). It is defined on the integer graph
$(\mathbb{Z},(x_{n})_{n\in\mathbb{Z}})$ in which every edge $(n,n+1)$ of the
integer line has the label $x_{n}$, where $(x_{n})_{n\in\mathbb{Z}}$ is a
realization of $(X_{n})_{n\in\mathbb{Z}}$. It describes how to move to the
next record starting from every integer. An instance of
$X=(X_{n})_{n\in\mathbb{Z}}$, which is given a special emphasis in the paper,
is a sequence of i.i.d. random variables satisfying the following conditions:
for all $n\in\mathbb{Z}$,

$X_{n}\in\\{-1,0,1,2,\cdots\\},\ \mathbb{E}[X_{n}]\text{ exists, }\text{ and
}0<\mathbb{P}[X_{n}=-1]\leq 1.$ (3)

The stochastic process $S$ (as in Eq. (1)) with the increment sequence $X$
satisfying Eq. (3) is known as _skip-free to the left random walk_ or _left-
continuous random walk_.

A _Family Tree_ is a (rooted) directed tree whose out-degree is at most $1$. A
Family Tree in which every vertex has out-degree $1$ is called an _Eternal
Family Tree (EFT)_. In a Family Tree $T$, a vertex $u\in V(T)$ is called a
child of a vertex $v\in V(T)$ if there is a directed edge from $u$ to $v$.

In this case, $v$ is called the parent of $u$. Similarly, for some $n\geq 1$,
a vertex $u$ is a descendant of order $n$ (or $n$-th descendant) of a vertex
$v$ if there is a directed path of length $n$ from $u$ to $v$, in which case
$v$ is called the ancestor of order $n$ (or $n$-th ancestor) of $u$.

######  Remark 1.

Observe that the record graph of a network $(\mathbb{Z},x)$ does not contain
cycles and that every vertex in the record graph has out-degree at most $1$.
The first observation follows from the fact that if $R_{x}(i)\not=i$, then
$R_{x}(i)>i$ and from the fact that self loops were removed. The second
observation is obvious since $R_{x}$ is a function. Thus, every component of
the record graph is a (non-rooted) Family Tree.

A Family Tree $T$ is said to be _ordered_ if the children of every vertex
$u\in V(T)$ are totally ordered. In this case, one obtains a total order on
$V(T)$ using the depth-first search order.

Given a vertex-shift $f$, construct a directed graph called the _$f$ -graph_
$G^{f}$ associated to each graph $G$ in the following way: the vertices of
$G^{f}$ are the same as those of $G$ and its directed edges are given by
$\\{(x,f_{G}(x)):x\in V(G),f_{G}(x)\not=x\\}$. Note that this definition of
$f$-graph does not allow self-loops which differs from the definition used in
[5].

Using the vertex-shift $f$, one obtains an equivalence relation on $V(G)$ by
declaring two vertices $u$ and $v$ to be equivalent if and only if there
exists some positive integer $n$ such that $f^{n}_{G}(u)=f^{n}_{G}(v)$. The
equivalence class of $u\in V(G)$ is called the _foil of $u$_ (denoted as
foil$(u)$). Since the connected component $G^{f}(u)$ of every vertex $u$ in
$G^{f}$ is the set $\\{v\in V(G):f^{n}_{G}(v)=f^{m}_{G}(u)\text{ for some
}n\geq 1,m\geq 1\\}$, it follows that foil$(u)\subseteq G^{f}(u)$.

####  1.1.1 Foil classification theorem of unimodular networks

This theorem [5, Theorem 3.9] states that, given a unimodular random rooted
network $[\mathbf{G},\mathbf{o}]$ and a vertex-shift $f$, a.s. every component
of $\mathbf{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.

In this case, the component is either a Family Tree or it has a unique cycle
of length $n$ (for some $n>1$). Moreover, in the former case, the component
has a single foil, whereas in the latter case, it has exactly $n$ foils; where
$n$ is the length of the cycle.

Components of either class $\mathcal{I}/\mathcal{I}$ or of class
$\mathcal{I}/\mathcal{F}$ are (non-rooted) EFTs. The class
$\mathcal{I}/\mathcal{I}$ corresponds to the component being infinite and all
foils of the component being infinite. Further, every EFT of this class is
characterised by the properties that it has one end and that all of its
vertices have finitely many descendants. The class $\mathcal{I}/\mathcal{F}$
corresponds to the component being infinite and all foils of the component
being finite. Every EFT of this class has a unique bi-infinite directed path,
characterised by the set of vertices with infinitely many descendants. The
remaining vertices have finitely many descendants.

Note that, in the statement of this theorem, the relation between the number
of foils and cycle length for class $\mathcal{F}/\mathcal{F}$ is slightly
modified compared to [5] due to the absence of self-loops in the definition of
$f$-graph here. The rest of the statement remains unchanged.

###  1.2 Statement of the results

Concerning (Q1), it is shown that when $X$ is assumed to be a stationary and
ergodic sequence of random variables whose common mean exists, the record
graph $\mathbb{Z}^{R}_{X}$ is a.s. connected if and only if
$\mathbb{E}[X_{0}]\geq 0$. Under the same assumptions, it is also shown that
the component $[T,0]$ of $0$ in this graph exhibits a phase transition when
$\mathbb{E}[X_{0}]$ is varied from $-\infty$ to $\infty$. If
$\mathbb{E}[X_{0}]\in[-\infty,0)$, then $[T,0]$ is a finite unimodular Family
Tree of class $\mathcal{F}/\mathcal{F}$ and all the components of the record
graph are finite. If $\mathbb{E}[X_{0}]\in(0,\infty]$, then $[T,0]$ is a
unimodular Family Tree of class $\mathcal{I}/\mathcal{F}$. At
$\mathbb{E}[X_{0}]=0$, $[T,0]$ is a unimodular Family Tree of either class
$\mathcal{I}/\mathcal{F}$ or class $\mathcal{I}/\mathcal{I}$. An example of
$X$ for which $\mathbb{E}[X_{0}]=0$ and $[T,0]$ is of class
$\mathcal{I}/\mathcal{I}$ is obtained when $X$ is i.i.d. and satisfies the
conditions in Eq. (3). Another example of $X$ for which $\mathbb{E}[X_{0}]=0$
but $[T,0]$ is of class $\mathcal{I}/\mathcal{F}$ is obtained using the
construction of a Loynes’ sequence [6] (see Example 31).

Concerning (Q2), the distribution of $[T,0]$ is explicitly computed when $X$
is i.i.d. and satisfies the conditions in Eq. (3). In this case, there are
three phases corresponding to $\mathbb{E}[X_{0}]<0$, $\mathbb{E}[X_{0}]=0$ and
$\mathbb{E}[X_{0}]>0$. Let $\pi$ be the distribution of $X_{0}+1$. When
$\mathbb{E}[X_{0}]<0$, it is shown in Theorem 46 that the distribution of
$[T,0]$ is (what is termed here as) the Typically re-rooted Galton-Watson Tree
($TGWT(\pi)$) with the offspring distribution $\pi$. It is obtained by re-
rooting to a root uniformly chosen in the size-biased version of the Galton-
Watson Tree ($GW(\pi)$), where $\pi$ is the offspring distribution. It is
shown in Proposition 50 that the following two properties: (i) unimodularity
and (ii) the independence between the offspring distribution of the root and
the non-descendant part of the tree, characterize a $TGWT$. When
$\mathbb{E}[X_{0}]=0$, the distribution of $[T,0]$ is the Eternal Galton-
Watson Tree ($EGWT(\pi)$) with the offspring distribution $\pi$ (see Theorem
51). This result is proved using the characterization of $EGWT$ given in [5].
When $\mathbb{E}[X_{0}]>0$, it is shown in Theorem 53 that $[T,0]$ is obtained
from a typical re-rooting operation of the bush of the root of (what is termed
here as) the bi-variate Eternal Kesten Tree ($EKT(\tilde{\pi},\bar{\pi})$)
with the offspring distributions $\tilde{\pi},\bar{\pi}$. The latter offspring
distributions are related to the increment $X_{0}$, the hitting probability
and the Doob transform of the random walk associated to $X$.

Concerning (Q3), it is useful to introduce the notion of succession line of an
ordered Family Tree passing through a vertex of the tree using the depth-first
search order, also called the Royal Line of Succession (RLS) order. It is
shown that a unimodular ordered EFT can have at most two succession lines. If
a unimodular ordered EFT $[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ has a
unique succession line, then, using the encoding of the number of children of
each vertex in the succession line, it is shown that there exists a stationary
sequence $Y$ such that the component of $0$ in the record graph of $Y$ is
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$. In this case,
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ is said to have a _record
representation_. Given a vertex-shift $f$ and a unimodular graph
$[\mathbf{G},\mathbf{o}]$, the component of $\mathbf{o}$ in the $f$-graph
$\mathbf{G}^{f}$ is a unimodular Family Tree
$[\mathbf{T}^{\prime\prime},\mathbf{o}^{\prime\prime}]$. Assign a uniform
order to the children of every vertex of $\mathbf{T}^{\prime\prime}$ to obtain
a unimodular ordered Family Tree. If it is infinite and has a unique
succession line, then the above result implies that it has a record
representation. In particular, if a vertex-shift $f$ on a network
$(\mathbb{Z},X)$ associated to a stationary sequence $X$ satisfies the
condition that the component of $0$ is infinite and has a unique succession
line, then $f$ has a record representation on $X$, i.e., there exists a
stationary sequence $Y$ such that the component of $0$ in the record graph of
$Y$ has the same distribution as that of the component of $0$ in the $f$-graph
of $(\mathbb{Z},X)$.

###  1.3 Literature and novelty

The statistics of records of time series have found many applications in
finance, hydrology and physics. See for instance the references in the survey
[12] 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 time gap between two consecutive records), and the age of
long-lasting records ([20], [12]). When the time series under consideration is
an i.i.d. sequence, it is shown in [19] that the mean of the height 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
stochastic processes that has stationary increments, with a special emphasis
on skip-free random walks. The structure has a natural family tree flavor with
an order, suggesting to term it as ‘genealogy of records’.

The relation between excursions of skip-free random walks and finite Galton-
Watson Trees was extensively discussed in, e.g., [7], [16], and [17]. In fact,
the authors of [7] encode the critical Galton-Watson Tree and show that the
encoding gives a correspondence between records of an excursion of the random
walk and ancestors of the root in the Galton-Watson Tree. In the present
paper, these ideas are extended to infinite trees using the succession line
and the RLS order. To the best of the authors’ knowledge, this complete
description of the record graph of skip-free random walks, the phase
transition in the stationary and ergodic case, and the record representation
of a class of unimodular Family Trees are new.

##  2 Preliminaries

###  2.1 Space of networks

The following framework for networks is adopted from [3]. A graph $G$ is a
pair $G=(V,E)$, where $V=V(G)$ is the vertex set of $G$ and $E=E(G)$ is the
edge set of $G$. The size of a graph is the cardinality of its vertices. A
network is a graph $G=(V,E)$ together with a complete separable space $\Xi$
and two maps, one from $V$ to $\Xi$ and the other from $E$ to $\Xi$. The space
$\Xi$ is called the mark space and the images under the two functions are
called marks. A graph is locally finite if every vertex of it has a finite
degree. All the graphs considered in this paper are locally finite. A rooted
network is a pair $(G,u)$, where $G$ is a (locally finite) connected network
and $u$ is a distinguished vertex of $G$. A rooted isomorphism
$\alpha:(G,u)\to(G^{\prime},u^{\prime})$ of two rooted networks
$(G,u),\,(G^{\prime},u^{\prime})$ is a bijective map $\alpha:V(G)\to
V(G^{\prime})$ satisfying the three conditions: (1) $(x,y)\in E(G)$ if and
only if $\left(\alpha(x),\alpha(y)\right)\in E(G^{\prime})$, (2)
$\alpha(u)=u^{\prime}$ and (3) marks of the vertices and the edges of $G$ are
the same as the marks of their images under $\alpha$. Two rooted networks are
said to be equivalent if and only if there exists a rooted isomorphism between
them. The equivalence class of a rooted network $(G,u)$ is denoted by $[G,u]$
and, for brevity, the latter is also called a rooted network. The space of all
equivalent classes of rooted networks is denoted by $\mathcal{G}_{*}$.
Similarly, one defines a doubly rooted network $(G,u,v)$, doubly rooted
isomorphism and an equivalence relation using the doubly rooted isomorphism.
The equivalence class of a doubly rooted network $(G,u,v)$ is denoted by
$[G,u,v]$, and the set of all equivalent classes of doubly rooted networks is
denoted by $\mathcal{G}_{**}$. For a rooted network $(G,u)$, for a doubly
rooted network $(G,u,v)$, and a non-negative integer $r$, the rooted network
$(G,u)_{r}$ is the subgraph (rooted at $u$) induced by all the vertices of $G$
that are at a graph distance of at most $r$ from $u$, and the doubly rooted
network $(G,u,v)_{r}$ (rooted at $u,v$) is the subgraph induced by all those
vertices of $G$ that are at a graph distance of at most $r$ from both $u$ and
$v$. Both the spaces $\mathcal{G}_{*},\,\mathcal{G}_{**}$ are complete
separable metric spaces respectively under the local metrics $d_{*},\,d_{**}$
defined in the following: for any two rooted networks
$[G,u],\,[G^{\prime},u^{\prime}]$ and for any two doubly rooted networks
$[G,u,v],[G^{\prime},u^{\prime},v^{\prime}]$,
$d_{*}([G,u],[G^{\prime},u^{\prime}])=2^{-r_{12}}$ and
$d_{**}([G,u,v],[G^{\prime},u^{\prime},v^{\prime}])=2^{-r^{\prime}_{12}}$,
where $r_{12}$ (resp. $r^{\prime}_{12}$) is the supremum of $r\geq 0$ such
that $(G,u)_{r},\,(G^{\prime},u^{\prime})_{r}$ (resp.
$(G,u,v)_{r},\,(G^{\prime},u^{\prime},v^{\prime})_{r}$) are isomorphic.
Similarly, the set of all equivalent classes of rooted Family Trees (resp.
doubly rooted Family Trees), denoted by $\mathcal{T}_{*}$ (resp.
$\mathcal{T}_{**}$), is a complete separable metric space with the above
respective metrics. A random rooted network $[\mathbf{G},\mathbf{o}]$ is a
measurable map from a probability space to $\mathcal{G}_{*}$.

###  2.2 Unimodularity and vertex-shifts

######  Definition 2 (unimodularity).

A random network $[\mathbf{G},\mathbf{o}]$ is _unimodular_ if it satisfies the
mass transport principle, i.e., for every measurable function
$h:\mathcal{G}_{**}\to\mathbb{R}_{\geq 0}$,

$\mathbb{E}\left[h_{+}([\mathbf{G},\mathbf{o}])\right]=\mathbb{E}\left[h_{-}([\mathbf{G},\mathbf{o}])\right],$
(4)

where $h_{+}([\mathbf{G},\mathbf{o}])=\sum_{u\in
V(\mathbf{G})}h([\mathbf{G},\mathbf{o},u])$, and
$h_{-}([\mathbf{G},\mathbf{o}])=\sum_{u\in
V(\mathbf{G})}h([\mathbf{G},u,\mathbf{o}])$.

An example of a (random) unimodular network is $[\mathbb{Z},0,X]$, where the
vertex set is $\mathbb{Z}$, edge set is $\\{(n,n+1):n\in\mathbb{Z}\\}$,
$X=(X_{n})_{n\in\mathbb{Z}}$ is a stationary sequence of integer-valued random
variables and $X_{n}$ is the mark of the edge $(n,n+1)$, for all
$n\in\mathbb{Z}$.

Dynamics on networks and some results on dynamics on unimodular networks
studied in [5] are now introduced.

######  Definition 3 (vertex-shift).

A _vertex-shift_ $f$ is a collection of maps $f_{G}:V(G)\to V(G)$, indexed by
locally-finite connected networks $G$, satisfying the following properties:

  1. 1.

Covariance: For any graph isomorphism $\alpha:G\rightarrow H$ of two graphs
$G$ and $H$, $f$ satisfies $f_{H}\circ\alpha=\alpha\circ f_{G}$,

  2. 2.

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

A trivial vertex-shift is the identity vertex-shift defined by $I_{G}(u)=u$,
for all $u\in V(G)$ and for all $G$. Given a subcollection of maps that are
defined on a subset of networks and that satisfy the above covariance and
measurability properties, this subcollection can be extended to obtain a
vertex-shift by defining it as identity on the rest of networks. This allows
one to define a vertex-shift on the support of a random rooted network. It is
easy to observe (see Subsection 2.5) that the record map gives a vertex-shift
and hence forth it is called the _record vertex-shift_ , denoted by $R$.

######  Example 4.

Another example of a vertex-shift is the _Parent vertex-shift $F$_. It is
indexed by Family Trees $T$ and defined by $u\mapsto F_{T}(u)$, for all $u\in
V(T)$, where $F_{T}(u)=u$ if $u$ does not have a parent, and $F_{T}(u)$ is the
parent of $u$ otherwise.

Consider the record vertex-shift $R$ and a network $(\mathbb{Z},x)$, where
$x=(x_{n})_{n\in\mathbb{Z}}$ is a sequence of integers. The following
convention is used in this paper. For a vertex $i\in\mathbb{Z}$ and any
positive integer $n\geq 1$, a vertex of the form $R^{n}_{x}(i)\not=i$, if it
exists, is called the _ancestor of order $n$ of $i$_ (also called the $n$-th
ancestor of $i$). Denote the set of _$n$ -th descendants_ (also called the
descendants of order $n$) of vertex $i\in\mathbb{Z}$ by
$D_{n}(i):=\\{k\in\mathbb{Z}\backslash\\{i\\}:R_{x}^{n}(k)=i\\}=\\{k<i:R_{x}^{n}(k)=i\\}$
and its cardinality by $d_{n}(i):=\\#D_{n}(i)$, with the convention that
$R^{0}_{x}(i)=D_{0}(i)=i$. Denote the set of all descendants of $i$ by
$D(i):=\\{i\\}\cup\bigcup_{n\geq 1}D_{n}(i)$ and its cardinality by
$d(i)=\\#D(i)$. For any vertex $i\in\mathbb{Z}$, its ancestor of order $1$, if
it exists, is called the _parent of $i$_; its descendants of order $1$ are
called the _children of $i$_; and the set
$\\{k\in\mathbb{Z}\backslash\\{i\\}:R_{x}(k)=R_{x}(i)\\}$ is called the _set
of siblings of $i$_. The notion of ancestors and descendants is consistent
with that of the Family Trees. This is useful because the components of the
record graph are Family Trees.

A _covariant_ subset is a collection of subsets $\mathfrak{S}_{G}$ indexed by
(locally-finite) connected networks $G$, where $\mathfrak{S}_{G}$ is a subset
of $V(G)$, that satisfy the following properties; (1) covariance property:
$\alpha(\mathfrak{S}_{G})=\mathfrak{S}_{\alpha(G)}$ for every network
isomporphism $\alpha$, (2) measurability: the map
$[G,o]\mapsto\mathbf{1}\\{o\in\mathfrak{S}_{G}\\}$ is measurable. A _covariant
partition_ is a collection of partitions $\Pi_{G}$ indexed by (locally-finite)
connected networks $G$, where $\Pi_{G}$ is a partition of $V(G)$ and the
collection satisfies the following two conditions, (1) every network
isomorphism $\alpha$ satisfies $\alpha\circ\Pi_{G}=\Pi_{\alpha(G)}$, (2) the
subset $\\{[G,o,u]:u\in\Pi_{G}(o)\\}$ is a measurable subset, where
$\Pi_{G}(o)$ is the element that contains $o$.

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

Vertex-shifts on unimodular networks have interesting properties. Some of the
properties which will be used in the later sections are stated below (see [5]
for their proofs).

######  Theorem 5 (Point-stationarity).

Let $f$ be a vertex-shift and $[\mathbf{G},\mathbf{o}]$ be a unimodular
measure. Then, the map $\theta_{f}$ preserves the distribution of
$[\mathbf{G},\mathbf{o}]$ if and only if $f$ is a.s. bijective.

######  Proposition 6.

Let $[\mathbf{G},\mathbf{o}]$ be unimodular and $f$ be a vertex-shift.

  * •

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

  * •

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

######  Lemma 7 (No Infinite/Finite Inclusion).

Let $[\mathbf{G},\mathbf{o}]$ be a unimodular network, $\mathbf{\mathfrak{S}}$
be a covariant subset and $\mathbf{\Pi}$ be a covariant partition. Almost
surely, there is no infinite element $E$ of $\mathbf{\Pi}_{\mathbf{G}}$ such
that $E\cap\mathbf{\mathfrak{S}}_{\mathbf{G}}$ is finite and non-empty.

######  Lemma 8.

Let $[\mathbf{G},\mathbf{o}]$ be a unimodular network, $\mathfrak{S}$ be a
covariant subset. Then, $\mathbb{P}[\mathfrak{S}_{\mathbf{G}}\text{ is non-
empty}]>0$ if and only if
$\mathbb{P}[\mathbf{o}\in\mathfrak{S}_{\mathbf{G}}]>0$.

Recall that for a vertex-shift $f$ and a network $G$, $G^{f}$ denotes the
$f$-graph of $G$. For any vertex $u\in V(G)$, denote the component of $u$ in
$G^{f}$ by $G^{f}(u)$. The following lemma follows because the map
$[G,o]\mapsto[G^{f}(o),o]$ is measurable.

######  Lemma 9.

Let $f$ be a vertex-shift and $[\mathbf{G},\mathbf{o}]$ be a random rooted
network. If $[\mathbf{G},\mathbf{o}]$ is unimodular, then
$[\mathbf{G}^{f}(\mathbf{o}),\mathbf{o}]$ is unimodular and conditioned on
being infinite, $[\mathbf{G}^{f}(\mathbf{o}),\mathbf{o}]$ is a unimodular EFT.

The results that are not stated here but, that are used in the later sections
are the foil classification theorem of unimodular networks (see Sec. 1.1.1)
[5, Theorem 3.9] and the classification theorem of unimodular Family Trees [5,
Proposition 4.3, Proposition 4.4]. The latter theorem states that any
unimodular (rooted) Family Tree is either of class $\mathcal{F}/\mathcal{F}$,
or of class $\mathcal{I}/\mathcal{F}$, or of class $\mathcal{I}/\mathcal{I}$.

###  2.3 Unimodular Eternal Galton-Watson Trees

Unimodular Eternal Galton-Watson Trees ($EGWT$s) are instances of unimodular
EFTs of class $\mathcal{I}/\mathcal{I}$. They are parametrized by a non-
trivial offspring distribution which has mean $1$. A characterizing property
of $EGWT$s is stated in Theorem 11, see [5] for more properties. In this work,
$EGWT$s show up as the record graph of skip-free to the left random walks when
the increments of the random walk have zero mean.

Let $\pi$ be a probability distribution on $\mathbb{Z}_{\geq 0}$ such that
mean $m(\pi)=1$ and $\pi(1)<1$, and let $\hat{\pi}$ be its size-biased
distribution defined by $\hat{\pi}(k)=k\pi(k),\forall k\geq 0$.

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

In particular, except for the vertices $F^{n}(\mathbf{o}),\,n\geq 1$, which
reproduce independently with distribution $\hat{\pi}$, all the remaining
vertices of the tree reproduce independently with the offspring distribution
$\pi$. See Figure 2 for an illustration.

Figure 2: The Eternal Galton-Watson Tree with offspring distribution $\pi$.
The Galton-Watson Tree with offspring distribution $\pi$ is denoted by
$GW(\pi)$, $\hat{\pi}$ is the size-biased distribution of $\pi$. The order
among the children of every vertex is considered to be increasing from left to
right.

######  Remark 10.

Let $[\mathbf{T},\mathbf{o}]$ be a unimodular $EGWT(\pi)$, where the mean
$m(\pi)=1$. Then, the descendant trees of all vertices, except for the
ancestors of the root $\mathbf{o}$, are independent critical Galton-Watson
Trees with the 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 is finite. So, $EGWT(\pi)$ is of class
$\mathcal{I}/\mathcal{I}$.

Similar construction exists for $EGWT(\pi)$ when the mean $m(\pi)\not=1$.
However, $EGWT(\pi)$ is unimodular if and only if the mean $m(\pi)$ is $1$;
and the following theorem characterizes unimodular $EGWT$s (see [5,
Proposition 6.5, Theorem 6.6]).

######  Theorem 11.

A unimodular Eternal Family Tree $[\mathbf{T},\mathbf{o}]$ is an $EGWT$ if and
only if the number of children $d_{1}(\mathbf{o})$ of the root is independent
of the non-descendant tree $D^{c}(\mathbf{o})$, i.e., the subtree induced by
$(V(\mathbf{T})\backslash D(\mathbf{o}))\cup\\{\mathbf{o}\\}$.

Note the emphasis on the Family Tree being eternal in Theorem 11. For a
similar characterisation result about finite Family Trees, see Proposition 50.

###  2.4 Typical re-rooting operation

The typical re-rooting operation is applied to the probability distribution of
a random Family Tree whose size is finite in mean, and the operation results
in another probability distribution.

######  Definition 12 (Typical re-rooting).

Let $[\mathbf{T},\mathbf{o}]$ be a random Family Tree that satisfies
$\mathbb{E}[\\#V(\mathbf{T})]<\infty$ and $\mathcal{P}$ be its distribution.
The typical re-rooting of $[\mathbf{T},\mathbf{o}]$ (or its distribution
$\mathcal{P}$) is the probability measure $\mathcal{P}^{\prime}$ defined by:

$\mathcal{P}^{\prime}[A]=\frac{1}{\mathbb{E}[\\#V(\mathbf{T})]}\mathbb{E}\left[\sum_{u\in
V(\mathbf{T})}\mathbf{1}_{A}([\mathbf{T},u])\right],$ (5)

for any measurable subset $A$ of $\mathcal{T}_{*}$.

A random Family Tree whose distribution is $\mathcal{P}^{\prime}$ is also said
to be a typically re-rooted $[\mathbf{T},\mathbf{o}]$. The following lemma
shows that the Family Tree obtained from the typical re-rooting of any Family
Tree that has finite mean size is unimodular. Since the unimodular Family Tree
thus obtained is also finite, it is of class $\mathcal{F}/\mathcal{F}$. So,
this operation can be used to generate unimodular Family Trees of class
$\mathcal{F}/\mathcal{F}$.

######  Lemma 13.

Let $[\mathbf{T},\mathbf{o}]$ be a random Family Tree that satisfies
$\mathbb{E}[\\#V(\mathbf{T})]<\infty$. Then, the random Family Tree
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ obtained by typically re-rooting
$[\mathbf{T},\mathbf{o}]$ is unimodular.

###### Proof.

For any measurable function $h:\mathcal{T}_{**}\to\mathbb{R}_{\geq 0}$,

$\displaystyle\mathbb{E}\left[h_{+}([\mathbf{T}^{\prime},\mathbf{o}^{\prime}])\right]$
$\displaystyle=\frac{1}{\mathbb{E}[\\#V(\mathbf{T})]}\mathbb{E}\left[\sum_{u\in
V(\mathbf{T})}h_{+}([\mathbf{T},u])\right]$
$\displaystyle=\frac{1}{\mathbb{E}[\\#V(\mathbf{T})]}\mathbb{E}\left[\sum_{u\in
V(\mathbf{T})}\sum_{v\in V(\mathbf{T})}h([\mathbf{T},u,v])\right]$
$\displaystyle=\frac{1}{\mathbb{E}[\\#V(\mathbf{T})]}\mathbb{E}\left[\sum_{v\in
V(\mathbf{T})}h_{-}([\mathbf{T},v])\right]$
$\displaystyle=\mathbb{E}\left[h_{-}([\mathbf{T}^{\prime},\mathbf{o}^{\prime}])\right].$

∎

A construction outlined in [5] offers a method for generating EFTs of class
$\mathcal{I}/\mathcal{F}$. In this paper, this construction is referred to as
the _typically re-rooted joining_ , and it is defined in the following way.

######  Definition 14 (Typically re-rooted joining).

Let $([\mathbf{T}_{i},\mathbf{o}_{i}])_{i\in\mathbb{Z}}$ be a stationary
sequence of random rooted Family Trees such that
$\mathbb{E}[\\#V(\mathbf{T}_{i})]<\infty$ for all $i\in\mathbb{Z}$. The
typically re-rooted joining of
$([\mathbf{T}_{i},\mathbf{o}_{i}])_{i\in\mathbb{Z}}$ is the probability
measure $\mathcal{P}^{\prime}$ given by the following: the EFT
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ is first obtained by joining
$(\mathbf{T}_{i})_{i\in\mathbb{Z}}$ by adding directed edges
$\\{(\mathbf{o}_{i},\mathbf{o}_{i+1}):i\in\mathbb{Z}\\}$, where
$\mathbf{o}^{\prime}=\mathbf{o}_{0}$, and one then defines

$\mathcal{P}^{\prime}[A]=\frac{1}{\mathbb{E}[\\#V(\mathbf{T}_{0})]}\mathbb{E}\displaystyle\left[\sum_{v\in
V(\mathbf{T}_{0})}\mathbf{1}_{A}([\mathbf{T}^{\prime},v])\right],$ (6)

for every measurable subset $A$ of $\mathcal{T}_{*}$.

The Family Tree $[\mathbf{T}_{i},\mathbf{o}_{i}]$ is called the $i$-th bush of
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ and
$[\mathbf{T}_{0},\mathbf{o}_{0}]$ is called the bush of the root.

Let $[\bar{\mathbf{T}},\bar{\mathbf{o}}]$ be the typical re-rooting of
$[\mathbf{T}_{0},\mathbf{o}_{0}]$, and $\mathbf{u}$ be the unique ancestor of
$\bar{\mathbf{o}}$ that does not have any parent. Let
$[\mathbf{T},\bar{\mathbf{o}}]$ be the EFT obtained by joining
$\\{[\mathbf{T}_{i},\mathbf{o}_{i}]:i\in\mathbb{Z}\backslash\\{0\\}\\}\cup\\{[\bar{\mathbf{T}},\bar{\mathbf{o}}]\\}$
by adding directed edges
$\\{(\mathbf{o}_{i},\mathbf{o}_{i+1}):i\in\mathbb{Z}\backslash\\{-1,0\\}\\}\cup\\{(\mathbf{o}_{-1},\mathbf{u}),(\mathbf{u},\mathbf{o}_{1})\\}$.
Observe that the distribution of $[\mathbf{T},\bar{\mathbf{o}}]$ is the same
as the probability measure $\mathcal{P}^{\prime}$.

The following results show that the typically re-rooted joining of a
stationary sequence is unimodular and belongs to class
$\mathcal{I}/\mathcal{F}$, and that every unimodular EFT of class
$\mathcal{I}/\mathcal{F}$ is obtained in this manner.

######  Theorem 15 ([5]).

Let $[\mathbf{T},\mathbf{o}]$ be the typically re-rooted joining of a
stationary sequence $([\mathbf{T}_{i},\mathbf{o}_{i}])_{i\in\mathbb{Z}}$,
where $\mathbb{E}[\\#V(\mathbf{T}_{0})]<\infty$. Then,
$[\mathbf{T},\mathbf{o}]$ is unimodular.

######  Theorem 16 ([5]).

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

###  2.5 The record vertex-shift and its properties

Observe that the record map defined in Eq. (2) is covariant. This property is
apparent when considering any two networks $(\mathbb{Z},x)$ and
$(\mathbb{Z},y)$ associated with the sequences $x=(x_{n})_{n\in\mathbb{Z}}$
and $y=(y_{n})_{n\in\mathbb{Z}}$, respectively. The two networks are
isomorphic, preserving the order on $\mathbb{Z}$, if and only if $y$ can be
obtained by shifting $x$, i.e., there exists an integer $i$ such that
$T_{i}x=y$, where $T_{i}x=(x_{n-i})_{n\in\mathbb{Z}}$.

In this case, the isomorphism $\alpha_{i}:(\mathbb{Z},x)\to(\mathbb{Z},y)$
associated to the integer $i$ is given by $\alpha_{i}(n)=n+i$, for all
$n\in\mathbb{Z}$. Therefore, the record map is covariant if and only if
$R_{T_{i}x}(k+i)=i+R_{x}(k)$, for all integers $k,i$ and for any integer-
valued sequence $x=(x_{n})_{n\in\mathbb{Z}}$. Indeed, for any integers $k,i$,

$\displaystyle R_{T_{i}x}(k+i)$
$\displaystyle=\begin{cases}\inf\\{j>k+i:\sum_{l=k+i}^{j-1}x_{l-i}\geq
0\\}\text{ if infimum is defined},\\\ k+i\text{ otherwise}\end{cases}$
$\displaystyle=\begin{cases}i+\inf\\{j>k:\sum_{l=k}^{j-1}x_{l}\\}\text{ if
infimum is defined}\\\ i+k\text{ otherwise}\end{cases}$
$\displaystyle=i+R_{x}(k).$

The record map also satisfies the measurability condition as the map
$[\mathbb{Z},i,j,x]\mapsto 1_{R_{x}(i)=j}$ is a function of
$(x_{i},x_{i+1},\cdots,x_{j-1})$. Therefore, the record map induces a vertex-
shift which is termed as the record vertex-shift.

The record vertex-shift possesses several key properties that play a crucial
role in determining the record graph. A key property is now described.

Let $x:=(x_{n})_{n\in\mathbb{Z}}$ be an arbitrary integer-valued sequence, and
$(\mathbb{Z},x)$ be its associated network. For the sequence $x$, it is
convenient to work with the partial sums
$y(k,i)=s_{i}-s_{k}=\sum_{j=k}^{i-1}x_{j}$, for any integers $k<i$. Define the
function
$L:\mathbb{R}^{\mathbb{Z}}\times\mathbb{Z}\rightarrow\mathbb{Z}\cup\\{-\infty\\}$
as

$L_{x}(i)=\begin{cases}\inf\\{j<i:y(k,i)\geq 0,\forall j\leq k<i\\}\text{, if
infimum exists;}\\\ i\text{ otherwise}.\end{cases}$ (7)

The integer $L_{x}(i)$ is the largest integer (if it exists) up to which all
the sums in the past of $i$ are at most equal to $s_{i}$. Note that
$-\infty\leq L_{x}(i)<i$ if and only if $-y(j,i)\leq 0$ for all integers $j$
such that $L_{x}(i)\leq j<i$. Therefore, $L_{x}(i)=i$ if and only if
$x_{i-1}<0$.

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 $i$).

Recall the notation: for a sequence $x$ and an integer $i\in\mathbb{Z}$,
$D_{1}(i):=\\{j<i:R_{x}(j)=i\\}$ is the set of children of $i$ and
$D(i):=\\{j<i:R^{n}_{x}(j)=i$ for some $n>0\\}\cup\\{i\\}$ is the set of
descendants of $i$.

######  Lemma 17.

Let $x=(x_{n})_{n\in\mathbb{Z}}$ be an integer-valued sequence 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)\leq j\leq i\\}.$

###### Proof.

It is first proved that $\\{j\in\mathbb{Z}:L_{x}(i)\leq j\leq 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)\leq j<i$. Since $y(j,i)\geq 0$, it follows that

$j<R_{x}(j):=\inf\\{k>j:y(j,k)\geq 0\\}\leq i.$

By iteratively applying the same argument to $R^{l}(j)$ for each $l>0$, one
finds the smallest non-negative integer $m$ such that $R^{m}_{x}(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)\leq
j\leq i\\}\subseteq D(i)$.

It is now proved that $D(i)=\\{j\in\mathbb{Z}:L_{x}(i)\leq j\leq i\\}$, i.e.,
if $-\infty<j<L_{x}(i)$, then $j$ is not a descendant of $i$. For any
$-\infty<j<L_{x}(i)$, the _claim_ is 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)$, one obtains that, either
$R^{2}_{x}(j)<L_{x}(i)$ or $R^{2}_{x}(j)>i$. Iterate this process several
times until one finds 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)$, one obtains 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.

The last _claim_ is now proved. Let $k:=L_{x}(i)-1$ and let $j$ be as in the
claim. Suppose that $R_{x}(j)\geq L_{x}(i)$, i.e., $R_{x}(j)>k$. Then,
$y(k,i)<0$, by the definition of $L_{x}(i)$. Since $R_{x}(j)>k$, one has
$y(j,k)\leq 0$ (equality holds only if $j=k$). So, $y(j,i)=y(j,k)+y(k,i)<0$.
Therefore, for any $L_{x}(i)\leq m\leq i$, $y(j,m)=y(j,i)-y(m,i)<0$, since
$y(m,i)\geq 0$ which follows by the definition of $L_{x}(i)$. So, $R_{x}(j)>i$
and the claim is proved. ∎

The following lemma shows that all the integers between an integer $i$ and its
record $R_{x}(i)$ are descendants of $R_{x}(i)$.

######  Lemma 18 (Interval property).

Let $x=(x_{n})_{n\in\mathbb{Z}}$ be an integer-valued sequence and $R$ be the
record vertex-shift on the network $(\mathbb{Z},x)$. For all $i\in\mathbb{Z}$,
the set of descendants of $R_{x}(i)$ contains $\\{j:i\leq j\leq R_{x}(i)\\}$.
There could be more descendants of $R_{x}(i)$ that are less than $i$.

###### Proof.

If $R_{x}(i)=i$, then it follows from the definition of descendants that
$i=R_{x}(i)\in D(R_{x}(i))$. So, let us assume that $i<R_{x}(i)$. By Lemma 17,
it is enough to show that $L_{x}(R_{x}(i))\leq i$. For any integer $m$ such
that $i<m<R_{x}(i)$, since $y(i,m)<0$ and $y(i,R_{x}(i))\geq 0$, one has

$y(m,R_{x}(i))=y(i,R_{x}(i))-y(i,m)\geq 0.$

Thus, $L_{x}(R_{x}(i))\leq i$. ∎

###  2.6 Royal Line of Succession (RLS) order

Let $T$ be an ordered Family Tree, where the children of every vertex are
totally ordered using $<$. The order on children can be extended to establish
a total order on the vertices of $T$ as follows.

Let $u,v$ be two distinct vertices of $T$. The vertex $v$ is said to have
precedence over $u$, denoted as $v\succ u$ (or $u\prec 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, as they are children of
$w$.

######  Remark 19.

For two vertices $u,v$ with common ancestor $w$, distinct from $u$ and $v$,
$u\prec v$ if and only if $y_{u}\prec y_{v}$ for every descendant $y_{u}$ of
$u$ and for every descendant $y_{v}$ of $v$.

The resulting total order $\prec$ is termed the _Royal Line of Succession
(RLS) order_ associated with $<$, and it is also known as the _Depth First
Search order_.

The immediate successor and the immediate predecessor of any vertex in an
ordered Family Tree are now defined using the RLS order.

######  Definition 20.

For any vertex $u$ of an ordered Family Tree $T$, let $B(u):=\\{v\in
V(T):v\prec u\\}$ and $A(u):=\\{v\in V(T):v\succ u\\}$. Define the _immediate
successor_ of $u$, $b(u)=\max\\{v\in B(u)\\}$ if it exists, and the _immediate
predecessor_ of $u$, $a(u)=\min\\{v\in A(v)\\}$ if it exists, where $\max$ and
$\min$ are taken with respect to $\prec$.

The immediate predecessor of a vertex may not exist, even though the vertex is
not the largest. For instance, consider the Family Tree whose vertices are
$\\{u_{n}:n\in\mathbb{Z}\\}$ and directed edges
$\\{(u_{n},u_{n+1}):n\in\mathbb{Z}\\}$. Add a new vertex $u$ to the Family
Tree and a directed edge $(u,u_{m})$, for some $m\in\mathbb{Z}$, such that
$u_{m-1}\succ u$. Then, $A(u)=\\{u_{k}:k\in\mathbb{Z}\\}$, and therefore
$a(u)$ does not exist.

However, the following lemma shows that the immediate successor of a vertex
always exists if the vertex is not the smallest.

######  Lemma 21.

Let $T$ be an ordered Family Tree, and $u\in V(T)$. If $u$ is not the smallest
vertex, then $b(u)$ exists.

###### Proof.

By hypothesis, $B(u)$ is non-empty. So, either of the following two cases
occurs:

  * •

If $u$ has children, then since it could only have finitely many children,
$b(u)$ is the largest (eldest) child of $u$.

  * •

If $u$ does not have any child, let $w=F^{m}(u)$ (for some $m\geq 1$) be the
smallest ancestor of $u$ that has a child smaller than $F^{m-1}(u)$, with the
notation $F^{0}(u)=u$. Such a vertex $w$ exists because $B(u)$ is non-empty.
Then, $b(u)$ is the largest among those siblings of $F^{m-1}(u)$ that are
smaller than $F^{m-1}(u)$.

∎

The iterates of the immediate successor and the immediate predecessor maps
$a,b$ starting from a vertex $u$ of an ordered Family Tree give the succession
line passing through the vertex $u$.

######  Definition 22.

Let $T$ be an ordered Family Tree and $o\in V(T)$. The _succession line_
passing through $o$ is the sequence of vertices
$U((T,o))=(u_{n})_{n\in\mathbb{Z}}$ iteratively defined as $u_{0}=o$ and,

$\displaystyle u_{n}$ $\displaystyle=\begin{cases}b(u_{n+1})\text{ if it
exists}\\\ u_{n+1}\text{ otherwise}\end{cases}\text{ for $n<0$},$ (8)
$\displaystyle u_{n}$ $\displaystyle=\begin{cases}a(u_{n-1})\text{ if it
exists}\\\ u_{n-1}\text{ otherwise}\end{cases}\text{ for $n>0$}.$

###  2.7 Relation between the RLS order and the integer order on the record
graph

Let $x=(x_{n})_{n\in\mathbb{Z}}$ be an integer-valued sequence and
$(\mathbb{Z},x)$ be its associated network. The components of the record graph
are ordered Family Trees, where the children of every vertex in the record
graph are ordered according to the integer order. The RLS order on each
component, which depends on $x$, gives a total order among the vertices of the
component. Since the vertices of the component are also totally ordered
according to the integer order, these two orders can be compared. The
following lemma demonstrates that these two orders are, in fact, equivalent.

######  Lemma 23.

Let $x=(x_{n})_{n\in\mathbb{Z}}$ be a real-valued sequence, $(\mathbb{Z},x)$
be its associated network. Let $i,j$ be two integers that belong to the same
connected component of the record graph. Then, $i<j$ (with respect to the
order on $\mathbb{Z}$) if and only if $i\prec j$.

###### Proof.

Since $i,j$ belong to the same component of the record graph, there exists an
integer $w=R^{m}(i)=R^{k}(j)$ which is their smallest common ancestor, i.e.,
$m$ and $k$ are the smallest non-negative integers satisfying this property.

($i<j\implies i\prec j$): Since $R^{n}(i)$ is an increasing sequence for
$0<n<m$, there exists a largest $n_{0}\leq m$ such that $R^{n_{0}}(i)\leq j$.
If $R^{n_{0}}(i)=j$, then $i\prec j$, which is the desired relation. So,
assume that $R^{n_{0}}(i)<j$ and $R^{n_{0}+1}(i)>j$. By Lemma 18, 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\leq R^{m_{0}-1}(j)$, one has $R^{n_{0}}(i)\prec
R^{m_{0}-1}(j)$, and by Remark 19, one has $i\prec j$.

($i\prec j\implies i<j$): The case where $j$ is an ancestor of $i$ is trivial.
So, assume that $j$ is not an ancestor of $i$. Then, $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 17, one has
$i<R^{m-1}(i)<L_{x}(R^{k-1}(j))\leq j$. ∎

##  3 Phase transition of the record graph of a stationary and ergodic
sequence

The framework of stationary sequences is adopted from [6] and [9]. Let
$X=(X_{n})_{n\in\mathbb{Z}}$ be a stationary sequence of random variables
whose common mean exists and $(\mathbb{Z},X)$ be its associated network. For
all $i\in\mathbb{Z}$, let $\mathbb{Z}^{R}_{X}(i)$ denote the component of $i$
in the record graph of $(\mathbb{Z},X)$. The foil classification theorem (see
Sec. 1.1.1) implies that, for each $i\in\mathbb{Z}$, a.s.
$\mathbb{Z}^{R}_{X}(i)$ is either of class $\mathcal{F}/\mathcal{F}$ or of
class $\mathcal{I}/\mathcal{F}$ or of class $\mathcal{I}/\mathcal{I}$. Recall
that the record graph is a directed forest (see Remark 1).

The main result of this section is Theorem 29 which shows that under the
assumption that $X$ is ergodic, a.s. every component of the record graph
belongs to one of the above-mentioned three classes depending on the mean of
the increment $X_{0}$. When the mean is negative, the record graph has
infinitely many components and every component is of class
$\mathcal{F}/\mathcal{F}$. When the mean is positive, the record graph is
connected, and it is of class $\mathcal{I}/\mathcal{F}$. When the mean is $0$,
the record graph is connected and it is either of class
$\mathcal{I}/\mathcal{F}$ or of class $\mathcal{I}/\mathcal{I}$. A family of
examples for the latter are the i.i.d. sequences of random variables with mean
$0$, in which case the record graphs are of class $\mathcal{I}/\mathcal{I}$.
This result follows from Chung-Fuchs recurrence theorem for random walks, see
Proposition 30.

Theorem 29 is proved after establishing several lemmas.

The following proposition and corollary show that the event that the component
of any fixed integer in the record graph belonging to one of the classes
$\\{\mathcal{F}/\mathcal{F},\mathcal{I}/\mathcal{I},\mathcal{I}/\mathcal{F}\\}$
has trivial probability.

######  Proposition 24.

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be a stationary and ergodic sequence of
random variables. Then,

$\displaystyle\mathbb{P}[\mathbb{Z}^{R}_{X}(0)\text{ is of class
}\mathcal{I}/\mathcal{I}]\in\\{0,1\\},$
$\displaystyle\mathbb{P}[\mathbb{Z}^{R}_{X}(0)\text{ is of class
}\mathcal{I}/\mathcal{F}]\in\\{0,1\\}.$

######  Corollary 25.

Under the assumptions of Proposition 24, the event $\\{\mathbb{Z}^{R}_{X}(0)$
is of class $\mathcal{F}/\mathcal{F}\\}$ has trivial probability measure.

###### Proof.

By the foil classification theorem (Sec. 1.1.1), $\mathbb{Z}^{R}_{X}(0)$ is
either of class $\mathcal{I}/\mathcal{I}$ or $\mathcal{I}/\mathcal{F}$ or
$\mathcal{F}/\mathcal{F}$. By Proposition 24, the first two events have
trivial probability measure which implies that the third event has trivial
probability measure. ∎

Let $T$ be the shift map that maps every sequence $x=(x_{n})_{n\in\mathbb{Z}}$
to $Tx=(x_{n+1})_{n\in\mathbb{Z}}$. The shift map naturally maps any rooted
network of the form $[\mathbb{Z},0,x]$ to
$T([\mathbb{Z},0,x])=[\mathbb{Z},0,Tx]$.

###### Proof of Proposition 24.

For any integer $i\in\mathbb{Z}$, consider the following events:

$\displaystyle E_{i}$
$\displaystyle:=\\{[\mathbb{Z},0,x]:\mathbb{Z}^{R}_{x}(i)\text{ is of class
}\mathcal{I}/\mathcal{I}\\}$ $\displaystyle F_{i}$
$\displaystyle:=\\{[\mathbb{Z},0,x]:\mathbb{Z}^{R}_{x}(i)\text{ is of class
}\mathcal{I}/\mathcal{F}\\},$

and let $T^{-1}E_{i}:=\\{[\mathbb{Z},0,x]:[\mathbb{Z},0,Tx]\in E_{i}\\}$,
$T^{-1}F_{i}:=\\{[\mathbb{Z},0,x]:[\mathbb{Z},0,Tx]\in F_{i}\\}$. Then, for
any $i\in\mathbb{Z}$, one has

$\displaystyle T^{-1}E_{i}$
$\displaystyle=\\{[\mathbb{Z},0,x]:\mathbb{Z}_{Tx}^{R}(i)\text{ is of class
}\mathcal{I}/\mathcal{I}\\}$
$\displaystyle=\\{[\mathbb{Z},0,x]:\mathbb{Z}_{x}^{R}(i+1)\text{ is of class
}\mathcal{I}/\mathcal{I}\\}$ (9) $\displaystyle=E_{i+1},$

where in Eq.(9), the fact that $[\mathbb{Z},i,Tx]=[\mathbb{Z},i+1,x]$ was
used. Similarly, it can be shown that $T^{-1}F_{i}=F_{i+1}$.

Observe that if $[\mathbb{Z},0,x]\in E_{i}$ (similarly $F_{i}$), then, by the
interval property (Lemma 18), $i+1$ and $i$ are in the same connected
component, i.e., $\mathbb{Z}^{R}_{x}(i)=\mathbb{Z}^{R}_{x}(i+1)$, which
implies that $[\mathbb{Z},0,x]\in E_{i+1}$ (similarly $F_{i+1}$). Thus,
$E_{i}\subseteq T^{-1}(E_{i})$. Similarly, $F_{i}\subseteq T^{-1}(F_{i})$.
Applying the following fact to $E_{0}$ and $F_{0}$ completes the proof: if
$(\mathbb{P},T)$ is ergodic and $A$ is a measurable subset such that
$A\subseteq T^{-1}A$, then $\mathbb{P}[A]\in\\{0,1\\}$ (see [9, Theorem
16.1.9]). ∎

The following lemma is an application of Poincare’s recurrence lemma.

######  Lemma 26.

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be a stationary sequence of random variables,
$(\mathbb{Z},X)$ be its associated network, and for all $n\in\mathbb{Z}$,
$\mathbb{Z}^{R}_{X}(n)$ be the component of $n$ in the record graph of
$(\mathbb{Z},X)$. Then,

$\displaystyle\mathbb{P}[\mathbb{Z}^{R}_{X}(0)\text{ is finite}]$
$\displaystyle=\mathbb{P}[\mathbb{Z}^{R}_{X}(n)\text{ is finite, }\forall
n\geq 1]=\mathbb{P}[\mathbb{Z}_{X}^{R}(n)\text{ is finite, }\forall n\leq-1].$
(10)

###### Proof.

Consider the event $A=\\{\mathbb{Z}^{R}_{X}(0)\text{ is finite}\\}$. By
Poincaré’s recurrence lemma,
$\mathbb{P}[A]=\mathbb{P}\left[\\{\mathbb{Z}_{T^{n}X}^{R}(0)\text{ is finite
for infinitely many }n\geq 1\\}\right]$. For any $\omega\in A$, if
$\mathbb{Z}_{T^{n}X(\omega)}^{R}(0)$ is finite for infinitely many $n\geq 1$,
then $\mathbb{Z}_{X(\omega)}^{R}(n)$ is finite for all $n\geq 1$. This fact,
proved below, together with Poincare’s recurrence lemma give the first
equality in Eq. (10).

The second equality of Eq. (10) follows by taking the shift
$\widetilde{T}:=T^{-1}$ instead of $T$, and by using the equality of the
events $\\{\mathbb{Z}_{\widetilde{T}^{n}X}^{R}(0)\text{ is
finite}\\}=\\{\mathbb{Z}_{X}^{R}(-n)\text{ is finite}\\}$ for all $n\geq 1$.

The aforementioned fact will now be proved.

Since $X$ is stationary, the network $[\mathbb{Z},0,X]$ is unimodular. So,
apply the foil classification theorem (Sec. 1.1.1) to the record graph
$\mathbb{Z}_{X}^{R}$ to obtain the following result: for any integer $n$, its
component $\mathbb{Z}_{X}^{R}(n)$ is finite if and only if there exists an
integer $i\in V(\mathbb{Z}_{X}^{R}(n))$ that has only finitely many ancestors.
In particular, if a vertex has finitely many ancestors then it must have
finitely many descendants.

The _claim_ is that if $\mathbb{Z}_{X(\omega)}^{R}(n_{1})$ is finite for any
positive integer $n_{1}$, then $\mathbb{Z}_{X(\omega)}^{R}(k)$ is finite for
all $k<n_{1}$. This follows because $\mathbb{Z}_{X(\omega)}^{R}(n_{1})$ is
finite if and only if the sequence $(S_{n+n_{1}})_{n\geq 0}$ attains a maximum
value $a_{n_{1}}$ finitely many times, i.e., $S_{n^{\prime}+n_{1}}=a_{n_{1}}$
for some $n^{\prime}\geq 0$ and $S_{n+n_{1}}<a_{n_{1}}$ for all $n>n^{\prime}$
(equivalently, from the discussion in the above paragraph, $n_{1}$ has
finitely many ancestors). So, if $k\leq n^{\prime}+n_{1}$, then the sequence
$(S_{n+k})_{n\geq 0}$ attains the maximum value $a_{n_{1}}$ at
$N=n^{\prime}+n_{1}-k$ and never attains it for all $n>N$. Therefore, $k$ has
finitely many ancestors. By the discussion in the above paragraph,
$\mathbb{Z}_{X(\omega)}^{R}(k)$ is finite, and the claim is proved.

The above claim implies that if there exists a subsequence $(n_{k})_{k\geq 1}$
of non-negative integers such that $n_{k}\to\infty$ as $k\to\infty$ and
$\mathbb{Z}^{R}_{X(\omega)}(n_{k})$ is finite for all $k\geq 1$, then
$\mathbb{Z}^{R}_{X(\omega)}(n)$ is finite for all $n\geq 1$. Using this and
the fact that $\mathbb{Z}^{R}_{T^{n}X}(0)=\mathbb{Z}^{R}_{X}(n)$ for all
$n\geq 0$, it follows that the events $\\{\mathbb{Z}_{T^{n}X}^{R}(0)$ is
finite for infinitely many $n\geq 1\\}$ and $\\{\mathbb{Z}_{X}^{R}(n)\text{ is
finite for all }n\geq 1\\}$ are one and the same. ∎

The following lemma gives a sufficient condition for the connectedness of the
record graph. The proof is an application of the interval property of the
record vertex-shift.

######  Lemma 27.

Let $X$ be a stationary sequence of random variables, and $(\mathbb{Z},X)$ be
its associated network. If $0$ has a.s. infinitely many ancestors in the
record graph $\mathbb{Z}^{R}_{X}$, then $\mathbb{Z}^{R}_{X}$ is a.s.
connected.

###### Proof.

For any $i\in\mathbb{Z}$, let $A_{i}$ be the event that $i$ has infinitely
many ancestors in $\mathbb{Z}^{R}_{X}$. By the stationarity of $X$, every
event $A_{i}$ occurs with probability $1$ for each $i\in\mathbb{Z}$ since
$A_{0}$ occurs with probability $1$. Therefore, the event
$A=\cap_{i\in\mathbb{Z}}A_{i}$ occurs with probability $1$.

The next step consists in showing that every integer $i<0$ belongs to the
component of $0$ in $\mathbb{Z}^{R}_{X}$. Similarly, by interchanging the role
of $i$ and $0$, it can be shown that every integer $i>0$ belongs to the
component of $0$.

Let $i<0$. Since $A$ occurs with probability $1$, the sequence
$(R^{n}_{X}(i))_{n\in\mathbb{Z}}$ is strictly increasing a.s.. So, there
exists a smallest (random) integer $k>0$ such that $R_{X}^{k-1}(i)<0\leq
R^{k}_{X}(i)$ a.s.. By Lemma 18 (applied to $R_{X}^{k-1}(i)$), $0$ is a
descendant of $R^{k}_{X}(i)$ a.s.. Thus, a.s., $0$ and $i$ are in the same
connected component. ∎

######  Corollary 28.

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be a stationary and ergodic sequence of
random variables, and $(\mathbb{Z},X)$ be its associated network. Then, the
following dichotomy holds: either

  1. 1.

the record graph is a.s. connected, or

  2. 2.

a.s., every component of the record graph is finite.

###### Proof.

By Proposition 24, the event that $0$ has infinitely many ancestors has
trivial probability. If a.s., $0$ has finitely many ancestors, then by Lemma
26, every component of the record graph is finite. Otherwise, by Lemma 27, the
record graph is a.s. connected. ∎

The main result is:

######  Theorem 29 (Phase transition of the record graph).

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be a stationary and ergodic sequence of
random variables such that their common mean exists. Let
$[\mathbb{Z}^{R}_{X}(0),0]$ be the component of $0$ in the record graph
$\mathbb{Z}_{X}^{R}$ of the network $(\mathbb{Z},X)$.

  1. 1.

If $\mathbb{E}[X_{0}]<0$, then a.s. every component of $\mathbb{Z}^{R}_{X}$ is
of class $\mathcal{F}/\mathcal{F}$.

  2. 2.

If $\mathbb{E}[X_{0}]>0$, then $\mathbb{Z}^{R}_{X}$ is connected, and it is of
class $\mathcal{I}/\mathcal{F}$ a.s.

  3. 3.

If $\mathbb{E}[X_{0}]=0$, then a.s., $\mathbb{Z}^{R}_{X}$ is connected, and it
is either of class $\mathcal{I}/\mathcal{F}$ or of class
$\mathcal{I}/\mathcal{I}$.

###### Proof.

(Proof of 1.) Let $\mathbb{E}[X_{0}]<0$. Since, by ergodicity,
$\frac{S_{n}}{n}\to\mathbb{E}[X_{0}]$ a.s., it follows that $S_{n}\to-\infty$
a.s. Therefore, the sequence $(S_{n})_{n\geq 0}$ attains a maximum value
$a_{0}$ at some (random) $n^{\prime}\geq 0$ and $S_{n}<a_{0}$ for all
$n>n^{\prime}$. This implies that $\mathbb{Z}^{R}_{X}(0)$ is finite a.s. and
hence it is of class $\mathcal{F}/\mathcal{F}$. By Lemma 26, every component
of $\mathbb{Z}^{R}_{X}$ is finite and hence it is of class
$\mathcal{F}/\mathcal{F}$.

(Proof of 2.) Let $\mathbb{E}[X_{0}]>0$. Since, by ergodicity,
$\frac{S_{n}}{n}\to\mathbb{E}[X_{0}]$ a.s., it follows that $S_{n}\to\infty$
a.s. and $S_{-n}\to-\infty$ a.s. The former implies that $0$ has infinitely
many ancestors. The latter implies that there exists $n_{0}\leq 0$ such that
$(S_{n})_{n\leq 0}$ attains maxima at $n_{0}$, i.e., $S_{n}\leq S_{n_{0}}$,
for all $n\leq n_{0}$. Therefore, $L_{X}(n_{0})=-\infty$, and by Lemma 17, it
follows that $n_{0}$ has infinitely many descendants. By Lemma 27,
$\mathbb{Z}^{R}_{X}$ has a single component and thus, it is of class
$\mathcal{I}/\mathcal{F}$.

(Proof of 3.) Let $\mathbb{E}[X_{0}]=0$ and $A$ be the event defined as

$A:=\\{\mathbb{Z}^{R}_{X}(0)\text{ is of class }\mathcal{F}/\mathcal{F}\\}.$

In order to prove that $\mathbb{P}[A]=0$, _suppose_ that $\mathbb{P}[A]>0$.
Then, by Corollary 25, $\mathbb{P}[A]=1$. Lemma 26 implies that
$\mathbb{P}[\mathbb{Z}^{R}_{X}(n)\text{ is finite }\forall n\in\mathbb{Z}]=1$.
Note that $\mathbb{Z}^{R}_{X(\omega)}(n)$ is finite for all $n\in\mathbb{Z}$
if and only if there exists a (random) subsequence
$(n^{\prime}_{k})_{k\in\mathbb{Z}}$ of $\mathbb{Z}$ such that
$n^{\prime}_{k}\to+\infty$, $n^{\prime}_{-k}\to-\infty$ as $k\to\infty$ and
for every $k\in\mathbb{Z}$, $S_{n}(\omega)<S_{n^{\prime}_{k}}(\omega)$ for all
$n>n^{\prime}_{k}$. In particular, a.s., $S_{n}\to-\infty$ and
$S_{-n}\to\infty$ as $n\to\infty$. Consider the covariant subset $Q$
consisting of peak points

$Q:=\left\\{k\in\mathbb{Z}:\sum_{i=k}^{k+n}X_{i}\leq-1\,\forall n\geq
0\right\\}.$

The covariant set $Q$ is a subset of integers such that the sums starting from
these integers are always negative. The integers of the set $Q$ can be
enumerated as $Q=(n_{i})_{i\in\mathbb{Z}}$, where $n_{i}<n_{i+1}$ for all
$i\in\mathbb{Z}$ and $n_{0}>0$ is the smallest positive integer that belongs
to the set $Q$. Such an enumeration is possible because $S_{n}\to-\infty$ and
$S_{-n}\to\infty$; thus, $n_{i}\to\infty$ as $i\to\infty$. Note that the
intermediate sums between two consecutive integers of $Q$ satisfy

$\sum_{k=n_{i}}^{n_{i+1}-1}X_{k}\leq-1,\,\forall i\in\mathbb{Z}.$ (11)

Since $\mathbb{P}[Q\text{ is non-empty}]=\mathbb{P}[A]=1$, the intensity
$\mathbb{P}[0\in Q]$ of the set $Q$ is positive (by Lemma 8). Birkhoff’s
pointwise ergodic theorem implies that a.s.,
$\frac{S_{n}}{n}\to\mathbb{E}[X_{0}]$ as $n\to\infty$. Since $n_{i}\to\infty$
as $i\to\infty$, it follows that a.s.,

$\lim_{i\to\infty}\frac{S_{n_{i}}}{n_{i}}=\lim_{n\to\infty}\frac{S_{n}}{n}=\mathbb{E}[X_{0}].$

For all $i\geq 1$,

$\displaystyle\frac{S_{n_{i}}}{n_{i}}$
$\displaystyle=\frac{X_{0}+\cdots+X_{n_{0}-1}+\sum_{k=0}^{i-1}(X_{n_{k}}+\cdots+X_{n_{k+1}-1})}{n_{i}}$
$\displaystyle\leq\frac{X_{0}+\cdots+X_{n_{0}-1}+\sum_{k=0}^{i-1}(-1)}{n_{i}}$
(12)
$\displaystyle=\frac{X_{0}+\cdots+X_{n_{0}-1}}{n_{i}}+\left(\frac{-i}{n_{i}}\right),$

where Eq. (12) is obtained using Eq. (11). Taking the limit $i\to\infty$ on
both sides of Eq. (12), one obtains that a.s.,

$\mathbb{E}[X_{0}]\leq-\mathbb{P}[0\in Q],$

since $\frac{-i}{n_{i}}=-\left(\frac{\left(\sum_{k=1}^{n_{i}}\mathbf{1}\\{k\in
Q\\}\right)-1}{n_{i}}\right)$ and the latter converges a.s. to
$-\mathbb{P}[0\in Q]$ as $i\to\infty$ by the cross-ergodic theorem for point
processes (see [6, Section 1.6.4]). Since, the intensity $\mathbb{P}[0\in
Q]>0$ and $\mathbb{E}[X_{0}]=0$, one gets a contradiction. Hence,
$\mathbb{P}[[\mathbb{Z}^{R}(0),0]\text{ is of class
}\mathcal{F}/\mathcal{F}]=0$. ∎

Instances of $X=(X_{n})_{n\in\mathbb{Z}}$ for which $\mathbb{E}[X_{0}]=0$, but
the record graph is of class $\mathcal{I}/\mathcal{I}$ occur when
$X=(X_{n})_{n\in\mathbb{Z}}$ is an i.i.d. sequence of random variables. This
result is proved in the following proposition.

######  Proposition 30.

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be an i.i.d. sequence of random variables
such that their common mean exists and $(\mathbb{Z},X)$ be its associated
network. If $\mathbb{E}[X_{0}]=0$, then the record graph of $(\mathbb{Z},X)$
is of class $\mathcal{I}/\mathcal{I}$.

###### Proof.

By Theorem 29, the record graph is either of class $\mathcal{I}/\mathcal{I}$
or of class $\mathcal{I}/\mathcal{F}$. So, it is sufficient to show that every
vertex of the record graph has finitely many descendants, which implies that
the record graph is of class $\mathcal{I}/\mathcal{I}$.

Let $i$ be an integer. Consider the i.i.d. sequence $(X_{i-1-n})_{n\geq 0}$ of
random variables. By the Chung-Fuchs theorem [15], the random walk
$\left(y(i-n,i)\right)_{n\geq 0}$ associated to the increment sequence
$(X_{i-1-n})_{n\geq 0}$ is recurrent, where
$y(i-n,i)=\sum_{k=i-n}^{i-1}X_{k}$, for all $n\geq 0$. Therefore, a.s.,
$y(i-n_{0},i)<0$ for some $n_{0}\geq 1$. This implies that $L_{X}(i)>-\infty$.
By Lemma 17, the number of descendants of $i$ in the record graph of
$(\mathbb{Z},X)$ is finite. Since this is true for any integer $i$, the event
that every integer (vertex) of the record graph has finitely many descendants
occurs almost surely. ∎

The following construction gives an example of a stationary and ergodic
sequence of random variables whose mean is $0$ but the record graph associated
to the sequence is of class $\mathcal{I}/\mathcal{F}$.

######  Example 31 (stationary, ergodic, mean $0$ but the record graph is of
class $\mathcal{I}/\mathcal{F}$).

See Figure 3 for an illustration of this example. Consider an $M/M/1/\infty$
queue with arrival rate $\lambda$ and service rate $\mu$ satisfying
$\lambda<\mu$. Let $(N_{n})_{n\geq 1}$ be the number of customers in the queue
observed at all changes of state. The Markov chain $(N_{n})_{n\geq 1}$ has a
unique stationary distribution $\eta$ (see [4]). The Markov chain
$(N_{n})_{n\geq 1}$ starting with the stationary distribution $\eta$ is
ergodic and $N_{n}=0$ for infinitely many $n\geq 1$. Note that $N_{n}\geq 0$
and $N_{n+1}-N_{n}\in\\{-1,+1\\}$, for all $n\geq 1$. Consider the stationary
version $(-N_{n})_{n\in\mathbb{Z}}$ of $(-N_{n})_{n\geq 1}$ (which can be done
by extending the probability space, see [9, Theorem 5.1.14]). Let
$Z_{n}=-N_{n}$ and $X_{n}=Z_{n+1}-Z_{n}$, for all $n\in\mathbb{Z}$. The
sequence $X=(X_{n})_{\in\mathbb{Z}}$ is a stationary sequence of random
variables taking values in $\\{-1,+1\\}$ and with mean
$\mathbb{E}[X_{0}]=\mathbb{E}[Z_{1}-Z_{0}]=0$ (since the sequence
$(Z_{n})_{n\in\mathbb{Z}}$ is stationary). Consider the record vertex-shift on
the network $(\mathbb{Z},X)$. Let $(S_{n})_{n\in\mathbb{Z}}$ be the sums of
$X$ starting at $0$ as in Eq. (1). The relation between $S_{n}$ and $N_{n}$ is
given by $S_{n}=-N_{n}+N_{0}$, for all $n\in\mathbb{Z}$. Since $N_{n}\geq 0$
for all $n\in\mathbb{Z}$ and $N_{n}=0$ a.s. for infinitely many $n\geq 1$,
$S_{n}\leq N_{0}$ for all $n\in\mathbb{Z}$ and $S_{n}=N_{0}$ for infinitely
many $n\geq 1$. Therefore, $0$ has infinitely many ancestors (since some
$k$-th record epoch of $0$ satisfies $S_{R^{k}(0)}=N_{0}$ and
$S_{R^{(k+i)}(0)}=N_{0}$, for all $i\geq 1$). Similarly, since $S_{n}\leq
N_{0}$ for all $n<0$, some ancestor of $0$ has infinitely many descendants (by
the interval property of the record vertex-shift). Thus, the component
$[\mathbb{Z}_{X}^{R}(0),0]$ of the record graph of $(\mathbb{Z},X)$ is of
class $\mathcal{I}/\mathcal{F}$.

Figure 3: An Illustration of Example 31 for constructing a stationary sequence
$X=(X_{n})_{n\in\mathbb{Z}}$ with $\mathbb{E}[X_{0}]=0$ such that the
component of $0$ of the record graph of the network $(\mathbb{Z},X)$ is of
class $\mathcal{I}/\mathcal{F}$. Figure A depicts the stationary sequence
$(N_{n})_{n\in\mathbb{Z}}$, Figure B gives the stationary sequence
$(-N_{n})_{n\in\mathbb{Z}}$, and Figure C is obtained from Figure B by
shifting the x-axis to $-N_{0}$. In Figure C, the increment sequence of
$(S_{n})_{n\in\mathbb{Z}}$ is $X$, the record graph is drawn in red and the
sequence of top most arrows is the bi-infinite path in the record graph.

##  4 Record vertex-shift on skip-free to the left random walks

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be an i.i.d. sequence of random variables
satisfying the conditions of Eq. (3) and $S=(S_{n})_{n\in\mathbb{Z}}$ be the
skip-free to the left random walk starting at $0$ with the increment sequence
$X$, as in Eq. (1).

The main objective of this section is to describe the distribution of the
component of $0$ in the record graph of the network $(\mathbb{Z},X)$ for the
three phases associated to $\mathbb{E}[X_{0}]<0$, $\mathbb{E}[X_{0}]=0$ and
$\mathbb{E}[X_{0}]>0$. This is described in Subsection 4.4.

This section is organised as follows. The first subsection describes the
relation between the number of offsprings of a vertex in the record graph and
the increment associated to it, the second subsection focuses on the
properties of skip-free to the left random walks, which will be used to
compute the distributions of the record graphs. Two new families of unimodular
random rooted networks are introduced in the third subsection. Finally, the
fourth subsection focuses on the aforementioned main objective.

###  4.1 Relation between offspring count in the record graph and the
respective increment of the sequence

For a sequence $x=(x_{k})_{k\in\mathbb{Z}}$, where
$x_{k}\in\\{-1,0,1,2,\ldots\\}$ for all $k\in\mathbb{Z}$, the number of
children of every vertex $i\in\mathbb{Z}$ in the record graph of
$(\mathbb{Z},x)$ depends on the values of the three functions $L_{x}$, $l_{x}$
and the type function $t_{x}$ at $i$.

This subsection elaborates on these relationships, which are instrumental in
characterizing the distribution of the component of $0$ in the record graph.

Recall the notation, $y(j,k):=\sum_{l=j}^{k-1}x_{l}$ for all integers $j<k$
and for the sequence $x=(x_{n})_{n\in\mathbb{Z}}$. The function $L_{x}$ is
defined in Eq. (7).

######  Definition 32 (Type function).

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

$t_{x}(i)=\inf\\{n\geq-1:y(m,i)=n\text{ for some }m<i\\}.$ (13)

The integer $t_{x}(i)$ is called the type of $i$. The type $t_{x}(i)$ of an
integer $i$ can also be written as

$t_{x}(i)=\inf\\{y(m,i)\vee-1:m<i\\},$ (14)

where $\vee$ is the max function. The type function is analogous to the
Loynes’ construction of the work load process [6].

The function $l_{x}:\mathbb{Z}\to\mathbb{Z}$ is the map that assigns every
integer $i$ to

$l_{x}(i)=\sup\\{m<i:y(m,i)=t_{x}(i)\\}.$ (15)

The relation between the functions $L_{x}$ and $l_{x}$ is as follows: first
note that for every $i\in\mathbb{Z}$, $-\infty<l_{x}(i)<i$ holds since
$t_{x}(i)=\min\\{y(m,i)\vee-1:m<i\\}$ and $l_{x}(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_{x}(i)=L_{x}(i)-1$. For any integer $i$, $t_{x}(i)\geq
0$ if and only if $L_{x}(i)=-\infty$.

The following lemma relates the offspring count of any vertex $i$ in the
record graph of $(\mathbb{Z},x)$ and its associated increment $x_{i-1}$ when
$L_{x}(i)<-\infty$. Note that, skip-free to the left condition is necessary
for this lemma to hold.

######  Lemma 33.

Let $x=(x_{k})_{k\in\mathbb{Z}}$ be a sequence such that
$x_{k}\in\\{-1,0,1,2,\ldots\\}$ for all $k\in\mathbb{Z}$. Let $(\mathbb{Z},x)$
be the network associated to $x$, and $T$ be the record graph of
$(\mathbb{Z},x)$. Let $i$ be an integer such that $L_{x}(i)>-\infty$ (see Eq.
(7)). Then,

  1. 1.

The number of children $d_{1}(i)$ of $i$ in $T$ is given by
$d_{1}(i)=x_{i-1}+1$.

  2. 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. 3.

Let $d_{1}(i)=n>0$, and $m\in\\{1,2,\cdots,n\\}$. Then, an integer
$i^{\prime}<i$ is the $m$-th child of $i$ if and only if $i^{\prime}$ is the
largest integer among $\\{L_{x}(i),\cdots,i-1\\}$ that satisfies
$y(i^{\prime},i)=x_{i-1}+1-m$.

###### Proof.

If $x_{i-1}=-1$, then $L_{x}(i)=i$. So, by Lemma 17, $i$ has no descendant.
Then, $(1.)$ holds as $d_{1}(i)=x_{i-1}+1=0$, whereas the other statements are
empty.

So, assume that $x_{i-1}\geq 0$. Clearly $i-1$ is then a child of $i$ as $i$
is the record of $i-1$. Therefore, $d_{1}(i)\geq 1$. It is shown 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^{\prime}$ be an
integer with $i_{m+1}<i^{\prime}<i_{m}$. As $i^{\prime}$ is not a child of
$i$, and $i_{m}$ is a child of $i$, by Lemma 18, one has
$R_{x}(i^{\prime})\leq i_{m}$, and there exists a smallest $k>0$ such that
$R_{x}^{k}(i^{\prime})=i_{m}$. Therefore,
$y(i^{\prime},i_{m})=\sum_{l=0}^{k-1}y(R_{x}^{l}(i^{\prime}),R_{x}^{l+1}(i^{\prime}))\geq
0$.

In particular, $y(i_{m+1}+1,i_{m})\geq 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})\geq 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})\geq 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, it was shown that
the sum of increments between two successive children is $-1$. This is now
used to prove the three statements of the lemma.

The proof of the _second statement_ follows because, for any child $i_{m}$ of
$i$, one has

$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}.$
(16)

The proof of the third statement is as follows. Since $i_{m}$ is a child of
$i$, $y(i_{m},i)\geq 0$, for all $1\leq m\leq n$. Further, for any
$i_{m}<i^{\prime}\leq i-1$, $y(i^{\prime},i)=y(i^{\prime},i_{j})+y(i_{j},i)$
holds, with $i_{j}\geq i^{\prime}$ 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, $j<m$. Since $y(i^{\prime},i_{j})\geq 0$, one has

$y(i^{\prime},i)=y(i^{\prime},i_{j})+x_{i-1}+1-j\geq x_{i-1}+1-j>x_{i-1}+1-m,$

where Eq. (16) was used 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^{\prime}<i$
is the largest integer satisfying $y(i^{\prime},i)=x_{i-1}+1-m\geq 0$ for some
$m\in\\{1,2,\cdots,n\\}$, then $y(i^{\prime},j)=y(i^{\prime},i)-y(j,i)<0$, for
all $i^{\prime}<j\leq i-1$. So, $i^{\prime}$ is a child of $i$. But, by Eq.
(16), there is only one child that satisfies this condition, namely, the
$m$-th child of $i$. This proves the third statement.

The next step consists in proving 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)\geq 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 17. 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_. ∎

######  Remark 34.

From the last part of the proof of Lemma 33, it follows that, if
$L_{x}(i)>-\infty$, then $L_{x}(i)$ is the smallest child of $i$.

The following lemma describes the smallest child of a vertex in the record
graph.

######  Lemma 35.

Let $x=(x_{k})_{k\in\mathbb{Z}}$ be a sequence such that
$x_{k}\in\\{-1,0,1,2,\ldots\\}$ for all $k\in\mathbb{Z}$. Let $(\mathbb{Z},x)$
be the network associated to $x$, and $T$ be the record graph of
$(\mathbb{Z},x)$. For any integer $i$, the following dichotomy holds:

  * •

if $t_{x}(i)=-1$, then $L_{x}(i)$ is the smallest child of $i$ in $T$,

  * •

if $t_{x}(i)\geq 0$, then $l_{x}(i)$ is the smallest child of $i$ in $T$.

###### Proof.

If $t_{x}(i)=-1$, then $L_{x}(i)>-\infty$. So, by Remark 34, $L_{x}(i)$ is the
smallest child of $i$ in $T$.

So, assume that $t_{x}(i)\geq 0$. In this case, $i$ is the record of
$l_{x}(i)$, i.e., $i=R(l_{x}(i))$. This follows because, for any
$l_{x}(i)<m<i$, one has $y(m,i)>t_{x}(i)$ by the definition of $t_{x}(i)$ and
$l_{x}(i)$. Since $y(l_{x}(i),i)=t_{x}(i)$, it follows that
$y(l_{x}(i),m)=y(l_{x}(i),i)-y(m,i)<0$. Thus, $R(l_{x}(i))=i$. Further, if
$t_{x}(i)\geq 0$, then $y(m,l_{x}(i))\geq 0$, for all $m<l_{x}(i)$. Indeed,
for $m<l_{x}(i)$, since $y(m,i)\geq t_{x}(i)$, one has
$y(m,l_{x}(i))=y(m,i)-y(l_{x}(i),i)\geq t_{x}(i)-t_{x}(i)=0$. So, $R(m)\leq
l_{x}(i)$ for all $m<l_{x}(i)$. This implies that $l_{x}(i)$ is the smallest
among the children of $i$ as none of the integers smaller than $l_{x}(i)$ are
children of $i$. ∎

The following lemma describes the relation between the number of children of
any integer $i$, its associated increment $x_{i}$ and its type $t_{x}(i)$ when
$t_{x}(i)\geq 0$. When $t_{x}(i)=-1$, the type does not play any role in
determining this relation.

######  Lemma 36.

Let $i\in\mathbb{Z}$ be an integer. The following dichotomy holds:

  * •

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)\geq 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 4: 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 36.

###### Proof.

If $t_{x}(i)=-1$, then $L_{x}(i)>-\infty$ (see the paragraph after Eq. (15)),
which is the condition needed to apply Lemma 33. The first part of the
statement follows from part 1 of Lemma 33.

The second part of the statement will now be proved. To follow the proof, see
Fig. 4. 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\geq
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)\leq j<k$. Thus,

$\bar{y}(k,i)=y(k,i)\geq t_{x}(i)>0\quad\forall l_{x}(i)\leq k<i,$ (17)

and

$\bar{y}(k,i)=k-l_{x}(i)+t_{x}(i)\quad\forall k<l_{x}(i).$

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

$L_{\bar{x}}(i)=l_{x}(i)-t_{x}(i)>-\infty.$ (18)

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 33,
it follows that $d_{1}(i,\bar{T})=\bar{x}_{i-1}+1$. Since $l_{x}(i)<i$, one
has $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 33, $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 33, one gets that

$\\{j\in\mathbb{Z}:L_{\bar{x}}(i)\leq j<l_{x}(i)\\}\subseteq
D_{1}(i,\bar{T}).$

By Eq. (18), $\\#\\{j\in\mathbb{Z}:L_{\bar{x}}(i)\leq
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)\leq j<i\\}=D_{1}(i,T)$ by Eq.
(17). Finally, Lemma 35 implies that $l_{x}(i)$ is the smallest child of $i$
in $T$. Thus,

$\displaystyle D_{1}(i,T)$
$\displaystyle=D_{1}(i,\bar{T})\backslash\\{j\in\mathbb{Z}:L_{\bar{x}}\leq
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).$

∎

###  4.2 Properties of skip-free to the left random walks

The lemmas in this subsection can be found in [10, Chapter 5]. They are
presented here utilizing the notations established in this paper for the sake
of completeness and to maintain consistency. Before delving into the proofs of
the lemmas, the following notations are introduced.

For any $j\in\mathbb{Z}$, let $\eta_{j}$ be the hitting time of the random
walk $S$ defined as

$\eta_{j}:=\begin{cases}\inf\\{n\geq 0:S_{n}=j\\}\text{ if }S_{n}=j\text{ for
some }n\geq 0\\\ \infty\text{ otherwise.}\end{cases}$ (19)

Let $\tau$ be the _weak upper record_ (epoch) of the random walk $S$ defined
as

$\tau:=\begin{cases}\infty\text{ if }S_{n}<0\ \forall n>0,\\\
\inf\\{n>0:S_{n}\geq 0\\}\text{ otherwise,}\end{cases}$ (20)

$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$). 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]$. The last condition of Eq. (3) implies that
$0<c\leq 1$.

######  Lemma 37.

For $0\leq j\leq 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 left
invariant by a 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$. It is proved by induction on $k-j$.

If $j=k$, then $\mathbb{P}_{j}[\eta_{j}<\infty]=1$. So, assume that $0\leq
j<k$. By induction,
$\mathbb{P}_{k^{\prime}}[\eta_{j^{\prime}}<\infty]=c^{k^{\prime}-j^{\prime}}$
for all $0\leq j^{\prime}\leq k^{\prime}$ such that
$k^{\prime}-j^{\prime}<k-j$. Then,

$\displaystyle\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},$

where the second equation is obtained by applying the inductive statement to
$k^{\prime}=k-1$, and $j^{\prime}=j$. ∎

######  Lemma 38 ([7]).

For all integers $j,k$ such that $0\leq j\leq 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}\geq 0\\}.$

Therefore, for $0\leq j=k$, one has
$\mathbb{P}[S_{\tau}=j,X_{\tau-1}=j,\tau<\infty]=\mathbb{P}[S_{1}=j]$.

So, for $0\leq j<k$,

$\displaystyle\mathbb{P}[\tau<\infty,S_{\tau}=j,X_{\tau-1}=k]$
$\displaystyle=\sum_{n=2}^{\infty}\mathbb{P}[\tau=n,S_{n}=j,X_{n-1}=k]$
$\displaystyle=\sum_{n=2}^{\infty}\mathbb{P}[S_{1}<0,\cdots,S_{n-1}<0,S_{n}=j,S_{n}-S_{n-1}=k].$

The sum in the first equation starts from $n=2$ since it is assumed that $j<k$
($\\{\tau=1\\}$ occurs if and only if $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,\cdots,S_{n}-S_{1}<0,S_{n}=j,S_{n}-(S_{n}-S_{1})=k].$

So, one gets:

$\displaystyle\mathbb{P}[\tau<\infty,S_{\tau}=j,X_{\tau-1}=k]$
$\displaystyle=\sum_{n=2}^{\infty}\mathbb{P}[S_{n}=j,S_{n-1}>j,S_{n-2}>j,\cdots,S_{1}>j,S_{1}=k]$
$\displaystyle=\sum_{n=2}^{\infty}\mathbb{P}[S_{1}=k]\mathbb{P}_{k}[S_{1}>j,\cdots,S_{n-2}>j,S_{n-1}=j]$
$\displaystyle=\mathbb{P}[S_{1}=k]\sum_{n=2}^{\infty}\mathbb{P}_{k}[\eta_{j}=n-1]$
$\displaystyle=\mathbb{P}[S_{1}=k]\mathbb{P}_{k}[0<\eta_{j}<\infty]$
$\displaystyle=\mathbb{P}[S_{1}=k]c^{k-j}=\mathbb{P}[X_{0}=k]c^{k-j}.$

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

######  Remark 39.

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].$

######  Remark 40.

If the random walk has positive drift, 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\leq j\leq k$.

Assume that $\mathbb{E}[X_{0}]>0$. In this case, the following lemma shows
that the random walk conditioned to hit $-1$ is also a skip-free to the left
random walk with a different increment distribution.

Let $p=(p_{k})_{k\geq-1}$ be the distribution of the increment $X_{0}$, i.e.,
$p_{k}:=\mathbb{P}[X_{0}=k]$, for all $k\in\mathbb{Z}_{\geq-1}$. Consider the
harmonic function $h$ (with respect to the random walk $S$) on
$\mathbb{Z}_{\geq 0}$ defined by $h(i)=\mathbb{P}_{i}[\eta_{-1}<\infty]$, for
all $i\in\mathbb{Z}_{\geq 0}$. In particular,
$h(0)=\mathbb{P}_{0}[\eta_{-1}<\infty]=c$. Since $h$ is harmonic,
$h(0)=\sum_{k=-1}^{\infty}p_{k}h(k)=\sum_{k=-1}^{\infty}p_{k}c^{k+1}$, which
follows from Lemma 37. Therefore,

$\sum_{k=-1}^{\infty}p_{k}c^{k}=\sum_{k=-1}^{\infty}\mathbb{P}[X_{0}=k]c^{k}=1.$
(21)

Let $\hat{p}=(\hat{p}_{k})_{k\geq-1}$ be the Doob $h$-transform of $p$, where
$\hat{p}_{k}:=p_{k}c^{k}$. Let

$\hat{X}=(\hat{X}_{n})_{n\in\mathbb{Z}}$ (22)

be an i.i.d. sequence of random variables whose common distribution is
$\hat{p}$, and $(\hat{S}_{n})_{n\in\mathbb{Z}}$ be the skip-free to the left
random walk whose increment sequence is $(\hat{X}_{n})_{n\in\mathbb{Z}}$,
defined as in Eq. (1).

######  Lemma 41.

Let $\mathbb{E}[X_{0}]>0$, and $\hat{\eta}_{-1}$ be the hitting time as
defined in Eq. (19) for the process $(\hat{S}_{n})_{n\in\mathbb{Z}}$. Then,
the stopped random walk $\hat{S}=(\hat{S}_{n\wedge\hat{\eta}_{-1}})_{n\geq 0}$
has the same law as the stopped random walk $(S_{n\wedge\eta_{-1}})_{n\geq 0}$
conditioned on $\eta_{-1}<\infty$.

###### Proof.

Let $(x_{0},x_{1},\cdots,x_{n})$ be arbitrary integers that satisfy
$x_{k}\geq-1,\forall k\leq n$, $x_{1}+\cdots+x_{m}\geq 0,\forall m<n$, and
$x_{1}+\cdots+x_{n}\geq-1$. Then, for all such $n$ and $x$,

$\displaystyle\mathbb{P}[S_{0}=0,S_{1}=x_{1},S_{2}-S_{1}=x_{2},\cdots,S_{(n\wedge\eta_{-1})}-S_{(n\wedge\eta_{-1}-1)}=x_{n},\eta_{-1}\geq
n|\eta_{-1}<\infty]$
$\displaystyle=\frac{\mathbb{P}[S_{1}=x_{1}]\mathbb{P}_{x_{1}}[S_{1}=x_{2},S_{2}-S_{1}=x_{3},\cdots,S_{n-1}-S_{n-2}=x_{n},\eta_{-1}<\infty]}{\mathbb{P}[\eta_{-1}<\infty]}$
$\displaystyle=\frac{\left(\prod_{i=1}^{n}\mathbb{P}[S_{1}=x_{i}]\right)\mathbb{P}_{x_{1}+\cdots+x_{n}}[\eta_{-1}<\infty]}{\mathbb{P}[\eta_{-1}<\infty]}=\frac{\left(\prod_{i=1}^{n}\mathbb{P}[S_{1}=x_{i}]\right)c^{x_{1}+x_{2}+\cdots+x_{n}+1}}{c}$
$\displaystyle=\prod_{i=1}^{n}(\mathbb{P}[X_{0}=x_{i}]c^{x_{i}})$
$\displaystyle=\mathbb{P}[\hat{S}_{1}=x_{1},\hat{S}_{2}-\hat{S}_{1}=x_{2},\cdots,\hat{S}_{(n\wedge\eta_{-1})}-\hat{S}_{(n\wedge\eta_{-1}-1)}=x_{n},\hat{\eta}_{-1}\geq
n].$

Thus, the conditioned random walk is a stopped random walk, stopped at the
hitting time $\hat{\eta}_{-1}$, whose increments have the common distribution
$\hat{p}$. ∎

The following lemma shows that the random walk $(\hat{S}_{n})_{n\geq 0}$ has
negative drift.

######  Lemma 42.

Assume $\mathbb{E}[X_{0}]>0$. Then, $\sum_{k=-1}^{\infty}k\hat{p}_{k}<0$,
i.e., the mean of the increment $\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]$. Using Eq. (21) in the following, one obtains

$\displaystyle\phi(c)$
$\displaystyle=\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$
$\displaystyle=\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}_{0}].$

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}kp_{k}+1-p_{-1}-1=\mathbb{E}[X_{0}]>0$.

  * •

$\phi$ is strictly increasing since $\phi^{\prime}(x)>0,\forall x\in(0,1)$.

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

It is now shown that $c<c^{\prime}$. 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^{\prime}(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^{\prime}(d)=0$. Since
$\phi(d)=\psi^{\prime}(d)=0$, one has $d=c^{\prime}$. Thus, $c<c^{\prime}$. ∎

###  4.3 Instances of unimodular Family Trees

This subsection introduces two parametric families of 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}$. An
instance of parametric family of unimodular Family Trees of class
$\mathcal{I}/\mathcal{I}$ called the unimodular Eternal Galton-Watson Trees
parametrized by the offspring distribution $\pi$ has already been described in
Subsection 2.3, where the mean $m(\pi)=1$ and $\pi(1)<1$. All the above Family
Trees appear as the component of $0$ in the record graph depending upon the
mean of the increment. This will be proven in the next subsection.

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

Let $\pi$ be a probability distribution on $\\{0,1,2,3,\cdots\\}$ such that
its mean $0\leq 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,\cdots\\}$. 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-
biased distribution of $\pi$). To each of the ancestors of $\mathbf{o}$,
attach a random number of children independently with distribution the same as
that of $Z-1$. Assign uniform order among the children of every ancestor of
$\mathbf{o}$.

  * •

To each of these new children and to the root $\mathbf{o}$, attach
independently ordered Galton-Watson Trees with offspring distribution $\pi$.

See Figure 5 for an illustration.

######  Remark 43.

The $TGWT(\pi)$ is a finite unimodular ordered Family Tree (see Proposition
50).

Figure 5: Typically rooted Galton-Watson Tree with offspring distribution
$\pi$ ($\mathbf{o}$ is the root), $m(\pi)$ is the probability that the root
$\mathbf{o}$ has a parent, $\hat{\pi}$ is the offspring distribution of the
parent of $\mathbf{o}$, $N$ is a geometric random variable with the success
probability $1-m(\pi)$.

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 as in Def. 12. This is indeed true and is proved in Proposition
48. A characterizing condition for $TGWT$ is given in Proposition 50.

##### Bibliographic comment

A construction for the modified subcritical Galton-Watson Tree $\mathfrak{T}$,
a random tree that resembles $TGWT$, is given by Jonsson and Stefánsson [14]
(for a simpler construction, see the subcritical case of [13, Section 5]). In
their construction, a vertex can have infinite degree with positive
probability and the tree is undirected. The special vertices of
$\mathfrak{T}$, which belong to the spine, have the offspring distribution
same as that of the ancestors of the root of $TGWT$, except for the last
special vertex of $\mathfrak{T}$ which may have infinite children. Note that
the undirected tree obtained by forgetting the directions of edges of $TGWT$
is not the same as $\mathfrak{T}$.

####  4.3.2 Bi-variate Eternal Kesten Tree

The unimodularised version of this tree is an instance of a unimodular tree
belonging to the class $\mathcal{I}/\mathcal{F}$. Its constuction is given
using the typically re-rooted joining operation (as in Def. 14). See Figure 6
for an illustration.

The next paragraph introduces the bi-variate Eternal Kesten Tree, denoted as
$EKT(\alpha,\beta)$, with the offspring distributions $\alpha$ and $\beta$.
This tree is unordered, unlabelled and parametrized by $\alpha$ and $\beta$.
Although $EKT(\alpha,\beta)$ is not unimodular, a unimodularised version can
be obtained from it using the typically re-rooted joining operation. To use
this operation, it is necessary to have $m(\beta)<1$. However, to define
$EKT(\alpha,\beta)$, it is sufficient to have $m(\alpha)<\infty$ and
$m(\beta)\leq 1$.

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

Observe that, if $\beta$ has mean $1$ and $\alpha=\hat{\beta}-1$, where
$\hat{\beta}$ is the size-biased distribution of $\beta$, then the descendant
tree of the root $[D(\mathbf{o}^{\prime}),\mathbf{o}^{\prime}]$ is the usual
Kesten tree (see [1, Section 2.3]).

Note that $EKT(\alpha,\beta)$ is the joining of the i.i.d. sequence
$([\mathbf{T}_{i},\mathbf{o}_{i}])_{i\in\mathbb{Z}}$, where
$T_{i}=D(\mathbf{o}_{i})\backslash D(\mathbf{o}_{i-1})$. Keep in mind that
$d_{1}(\mathbf{o}_{i},\mathbf{T}_{i})=d_{1}(\mathbf{o}_{i},\mathbf{T}^{\prime})-1$,
where $d_{1}(\mathbf{o}_{i},\mathbf{T}_{i})$ denotes the number of children of
$\mathbf{o}_{i}$ in $\mathbf{T}_{i}$.

Furthermore, assume that $m(\beta)<1$. Then, $GW(\beta)$ is subcritical, which
implies that $\mathbb{E}[\\#V(\mathbf{T}_{0})]<\infty$. So, in this case, the
necessary condition needed to apply typically re-rooted joining operation to
the i.i.d. Family Trees $([\mathbf{T}_{i},\mathbf{o}_{i}])_{i\in\mathbb{Z}}$
is satisfied. Let $[\mathbf{T},\mathbf{o}]$ be the typically re-rooted joining
of $([\mathbf{T}_{i},\mathbf{o}_{i}])_{i\in\mathbb{Z}}$ (as in Def. 14). Then,
by Theorem 15, the EFT $[\mathbf{T},\mathbf{o}]$ is unimodular. The
distribution of $[\mathbf{T},\mathbf{o}]$ is called the unimodularised bi-
variate $EKT(\alpha,\beta)$. Clearly, the unimodularised $EKT(\alpha,\beta)$
is of class $\mathcal{I}/\mathcal{F}$ as it has a (unique) bi-infinite
$F$-path.

An _Every Child Succeeding (ECS) order_ on
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ is obtained by declaring that
$\mathbf{o}_{n}$ is the smallest among $D_{1}(\mathbf{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. 22 )
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}$. In
the next subsection, it is shown that the unimodularised ECS ordered
$EKT(\alpha,\beta)$ is the component of $0$ in the record graph of the network
$(\mathbb{Z},X)$, where the sequence $X=(X_{n})_{n\in\mathbb{Z}}$ is an i.i.d.
sequence satisfying the conditions in Eq. 3 and $\mathbb{E}[X_{0}]>0$. In this
case, the distributions $\alpha,\beta$ are related to the distribution of
$X_{0}$.

Figure 6: An illustration of bi-variate ECS ordered EKT with distributions
$\alpha,\beta$ ($\mathbf{o}_{0}$ is the root), $\alpha$ is the offspring
distribution of $\mathbf{o}_{0}$ in $\mathbf{T}_{0}$, $\beta$ is the offspring
distribution of every child of $\mathbf{o}_{0}$ in $\mathbf{T}_{0}$.

Note that, to obtain a unimodular EFT, it is sufficient to follow a stationary
rule of assigning order to the vertices in the typically re-rooted joining of
a stationary sequence of Family Trees, as explained in the following. Let
$([\mathbf{T}_{n},\mathbf{o}_{n},Z_{n}])_{n\in\mathbb{Z}}$ be stationary
sequence of marked ordered Family Trees, where $Z_{n}$ is a random variable
such that $Z_{n}\leq d_{1}(\mathbf{o}_{n+1})$, for all $n\in\mathbb{Z}$. Let
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ be the ordered EFT obtained by the
joining of $([\mathbf{T}_{n},\mathbf{o}_{n},Z_{n}])_{n\in\mathbb{Z}}$, where
the order on $\mathbf{T}^{\prime}$ is given by the following: for all
$n\in\mathbb{Z}$, the order of $\mathbf{o}_{n}$ among the children of
$\mathbf{o}_{n+1}$ is $Z_{n}$. Let $[\mathbf{T},\mathbf{o}]$ denote the EFT
obtained by re-rooting to the typical root of $\mathbf{T}_{0}$ in
$\mathbf{T}^{\prime}$. Then, $[\mathbf{T},\mathbf{o}]$ is unimodular. This
follows because, the EFT $[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ is
invariant under the vertex-shift $f$, defined on the set of EFTs $T$ that has
a unique bi-infinite path $S_{T}$ in the following way:

$f_{T}(u)=\begin{cases}F_{T}(u)\text{ if }u\in S_{T}\\\ u\text{
otherwise,}\end{cases}$

where $F_{T}(u)$ is the parent of $u$.

###  4.4 Distribution of the component in the record graph

This subsection focuses on the distribution of the component of $0$ in the
record graph of $(\mathbb{Z},X)$, where $X=(X_{n})_{n\in\mathbb{Z}}$ is any
i.i.d. sequence satisfying conditions of Eq. (3). This subsection is divided
into three parts, each corresponds to the three phases
$\mathbb{E}[X_{0}]<0,\mathbb{E}[X_{0}]=0$ and $\mathbb{E}[X_{0}]>0$
respectively.

The following proposition shows that when $\mathbb{E}[X_{0}]\leq 0$, the
descendant tree of $0$ in the record graph is given by the excursion set
associated to $(S_{n})_{n\leq 0}$. The case when $\mathbb{E}[X_{0}]=0$ has
also been addressed in [7].

An $n+1$-tuple of integers of the form $(0,s_{1},\cdots,s_{n-1},1)$ with
$s_{j}\leq 0$ for all $1\leq j\leq n-1$ is called an excursion set. Let
$\delta=\max\\{n<0:S_{n}\geq 1\\}=\max\\{n<0:S_{n}=1\\}$ (equality follows
from the skip-free property).

######  Proposition 44.

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be an i.i.d. sequence satisfying the
conditions in Eq. (3), $(\mathbb{Z},X)$ be its associated network, and
$[D(0),0]$ be the descendant tree of $0$ in the record graph of
$(\mathbb{Z},X)$. If $\mathbb{E}[X_{0}]\leq 0$, then $[D(0),0]$ is the ordered
Galton-Watson Tree with the offspring distribution
$\pi\overset{\mathcal{D}}{=}X_{0}+1$.

###### Proof.

Since the random walk $(S_{-n})_{n\geq 0}$ drifts to $\infty$, one has
$\delta>-\infty$. It follows from the definition of $L_{X}(0)$ (see Eq. (7))
that $L_{X}(0)=\delta-1$ since $y(\delta,0)=-S_{\delta}=-1$ and for any
$\delta-1\leq j<0$, $y(j,0)=-S_{j}>-1$. Thus, $L_{X}(0)>-\infty$ a.s., which
is the required condition in order to apply Lemma 33. The first part of Lemma
33 implies that $d_{1}(0)=X_{-1}+1\overset{\mathcal{D}}{=}\pi$.

It is now shown 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\geq 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 33, $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\geq 1$, $i_{m}$ is a stopping time for the random walk $(S_{-n})_{n\geq
0}$, and the third part of Lemma 33, together imply the following: the
excursions
$((S_{i_{k}}-S_{i_{k}},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 17, for any $1\leq k\leq 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}})\overset{\mathcal{D}}{=}(S_{0},S_{-1},\cdots,S_{\delta}).$

This completes the proof. ∎

######  Remark 45.

Consider the i.i.d. sequence $\hat{X}=(\hat{X}_{n})_{n\in\mathbb{Z}}$ defined
in Eq. (22). Since $\mathbb{E}[\hat{X}_{0}]<0$ by Lemma 42, the assumption of
Proposition 44 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 fact will be
used in the last part of Step 2 of Theorem 53.

####  4.4.1 Negative mean

This part of the subsection focuses on the case when the mean of the increment
$X_{0}$ is negative, and it has three key objectives.

The first objective is to establish that the distribution of the component of
$0$ in the record graph of $(\mathbb{Z},X)$ is the $TGWT$ with the offspring
distribution the same as that of $X_{0}+1$. This is proved in Theorem 46.

The second objective is to demonstrate that every $TGWT(\alpha)$ is obtained
by typically re-rooting $GW(\alpha)$, where $\alpha$ is any offspring
distribution that has mean $m(\alpha)<1$. To prove this, consider
$[\mathbf{T},0]$, the component of $0$ in the record graph of
$(\mathbb{Z},X)$, where the increments follow the common distribution
$X_{0}+1\overset{\mathcal{D}}{=}\alpha$. Initially, it is shown that the
conditioned Family Tree $[\mathbf{T},0]|\\{F(0)=0\\}$, conditioned on the
event that the root $0$ of $\mathbf{T}$ has no parent, follows the
distribution $GW(\alpha)$ (see Lemma 47). Then, it is shown that
$[\mathbf{T},0]$ is obtained by typically re-rooting
$[\mathbf{T},0]|\\{F(0)=0\\}$ (see Proposition 48).

The third objective is to give a characterisation of $TGWT$, which is detailed
in Proposition 50.

######  Theorem 46.

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be an i.i.d. sequence satisfying the
conditions in Eq. (3), $(\mathbb{Z},X)$ be its associated network, and
$[\mathbf{T},o]$ be the connected component of $0$ (rooted at $o=0$) in the
record graph of $(\mathbb{Z},X)$. If $\mathbb{E}[X_{0}]<0$, then
$[\mathbf{T},o]$ is the Typically rooted Galton-Watson Tree with offspring
distribution $\pi$, where $\pi$ is the distribution of $X_{0}+1$.

###### Proof.

The theorem is proved in several steps.

_Step 1_ shows that the descendant tree of the root $o$ is a Galton-Watson
Tree with offspring distribution $\pi$. _Step 2_ shows the probability that
$o$ has a parent is equal to the mean $m(\pi)$. One way to compute it is by
using Kemperman’s formula (see [8, Proposition 3.7]). Alternatively, one could
use the unimodularity of $[\mathbf{T},o]$. The latter is used in this step.
_Step 3_ shows that the offspring distribution of $F(o)$ conditioned on the
event that $o$ has a parent is $\hat{\pi}$ (the size-biased distribution of
$\pi$). _Step 4_ shows that the distribution of the order of $o$ is uniform
among its siblings conditioned on the event that $o$ has a parent. _Step 5_
shows that the descendant trees of the siblings of $o$ conditioned on the
event that $o$ has a parent are independent Galton-Watson Trees with offspring
distribution $\pi$.

The final step (_Step 6_) shows that the offspring distribution of $F^{2}(o)$
conditioned on the event that $o$ has an ancestor of order $2$ is the same as
the offspring distribution of $F(o)$ conditioned on the event that $o$ has a
parent. Similarly, it is shown that the descendant trees of siblings of $F(o)$
and its order among its siblings conditioned on the event that $o$ has an
ancestor of order $2$ have the same distribution as those of $o$ conditioned
on the event that $o$ has a parent.

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

Step 2: Since $[\mathbf{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 9. Therefore,

$\displaystyle\mathbb{P}[o\text{ has a parent}]$
$\displaystyle=\mathbb{E}\left[\sum_{u\in
V(\mathbf{T})}\mathbf{1}\\{F(o)=u\\}\right]=\mathbb{E}\left[\sum_{u\in
V(\mathbf{T})}\mathbf{1}\\{F(u)=o\\}\right]$
$\displaystyle=\mathbb{E}[d_{1}(o)]=m(\pi)=\mathbb{E}[X_{0}]+1,$

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 38 for the definition of $\tau$). So,
$\mathbb{P}[\tau<\infty]=m(\pi)$. Since $(S_{-n})_{n\geq 0}$ drifts to
$+\infty$, part (1) of Lemma 33 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$,

$\displaystyle\mathbb{P}[d_{1}(F(o))=n,\tau<\infty]$
$\displaystyle=\sum_{j=0}^{n-1}\mathbb{P}[\tau<\infty,X_{\tau-1}=n-1,S_{\tau}=j]$
$\displaystyle=\sum_{j=0}^{n-1}\mathbb{P}[S_{1}=n-1]c^{j-n+1}=n\pi(n).$ (23)

By Lemma 38, Eq. (23) follows from the previous equation. The last equation
follows since $c=\mathbb{P}[S_{n}=-1\text{ for some }n>0]=1$ as the random
walk $(S_{n})_{n\geq 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\leq n$ follows from part (3) of Lemma 33 (with $i_{m}$ as $0$ and
$i$ as $F(0)$). Therefore, using Lemma 38 and $c=1$, one gets that for any
$0<k\leq 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\leq 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}<\cdots<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\leq j\leq n-1$, the part of the random walk
$(0,S_{i_{j}-1}-S_{i_{j}},S_{i_{j}-2}-S_{i_{j}},\cdots,S_{i_{j+1}}-S_{i_{j}})$
is an excursion set by Lemma 33 (part 3). Further, these excursion sets are
independent of one another because the times $i_{j}$ (for $1\leq j\leq n$) are
stopping times. Indeed, for all $1\leq j\leq n-1$, $S_{i_{j+1}}-S_{i_{j}}=1$
and $S_{l}<S_{i_{j+1}}$ for all $i_{j+1}<l\leq i_{j}$. Therefore, for each
$1\leq j\leq n-1$,
$(0,S_{i_{j}-1}-S_{i_{j}},S_{i_{j}-2}-S_{i_{j}},\cdots,S_{i_{j+1}}-S_{i_{j}})$
is the skip-free to the right random walk $(S_{-n})_{n\geq 0}$ conditioned on
$\eta_{1}<\infty$, and stopped at $\eta_{1}$, where
$\eta_{1}=\min\\{n>0:S_{-n}=1\\}$. But $(S_{-n})_{n\geq 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}},\cdots,S_{i_{j-1}}-S_{i_{j}})$
has the same distribution as $(0,S_{-1},\cdots,S_{\eta_{1}})$. Therefore, by
Proposition 44, for each $1\leq j\leq n$, the descendant trees are independent
$GW(\pi)$.

Step 6: Observe that the distribution of $(S_{n}-S_{\tau})_{n\geq\tau}$
conditioned on $\tau<\infty$ is the same as that of $(S_{n})_{n\geq 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\geq 0}$ drifts to $+\infty$ a.s., it reaches
$S_{R^{2}(0)+1}$ a.s.. Therefore, by part (1) of Lemma 33, 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))\backslash D(F(o)),o]$ conditioned on $\\{o\text{ has a
grandparent}\\}$ is the same as that of $[D(F(o))\backslash D(o),o]$
conditioned on $\\{o\text{ has a parent}\\}$. By induction, it follows that
$[D(F^{n}(o))\backslash 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))\backslash D(o),o]$ conditioned on $\\{o\text{ has a parent}\\}$. ∎

It is now shown that the Typically rooted Galton-Watson Tree is the typical
re-rooting (as in Def. 14) of a Galton-Watson Tree. Let $[\mathbf{T},o]$ be
the Family Tree as in Theorem 46, and let $\\{F(o)=o\\}$ denote the event that
$o$ does not have a parent. Let

$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]\overset{\mathcal{D}}{:=}[\mathbf{T},o]|\\{F(o)=o\\},$
(24)

be the Family Tree obtained from $[\mathbf{T},o]$ by conditioning on the event
that $o$ does not have a parent. The first step consists in showing that the
distribution of $[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ is $GW(\pi)$.
Since $m(\pi)=\mathbb{E}[X_{0}]+1<1$, the size of $GW(\pi)$ is finite in mean.
Thus, the typical re-rooting of $GW(\pi)$ is defined. The next step consists
in proving that $[\mathbf{T},o]$ is the typical re-rooting of
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$. By varying the distribution of
$X_{0}$, it is shown that every Typically rooted Galton-Watson Tree is the
typical re-rooting of a Galton-Watson Tree.

The following lemma uses the notation of Theorem 46.

######  Lemma 47.

Let $[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ be the Family Tree defined in
Eq. 24, with $[\mathbf{T},0]$ as the component of $0$ in the record graph of
$(\mathbb{Z},X)$, where $X$ is the sequence as in Theorem 46. Then, the
distribution of $[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ 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\leq 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\leq 0\\}$. This implies that the distribution of the
descendant tree $[D(o),o]$ of $o$ conditioned on the event $\\{F(o)=o\\}$ is
the same as that of $[D(o),o]$ (the unconditioned descendant tree of $o$).
Therefore,

$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]=[D(o),o]|\\{F(o)=o\\}\overset{\mathcal{D}}{=}[D(o),o].$

Since $\mathbb{E}[X_{0}]<0$, by Proposition 44, the distribution of $[D(o),o]$
is $GW(\pi)$. ∎

######  Proposition 48.

Let $\alpha$ be a probability measure on $\\{0,1,2,\cdots\\}$ such that its
mean $m(\alpha)<1$. Then, the $TGWT(\alpha)$ is the typical re-rooting of
$GW(\alpha)$.

###### Proof.

Take an i.i.d. sequence of random variables
$X^{\prime}=(X_{n}^{\prime})_{n\in\mathbb{Z}}$ such that their common
distribution is given by $\mathbb{P}[X^{\prime}_{0}=j]=\alpha(j+1)$, for all
$j\in\\{-1,0,1,2,\ldots\\}$. Let $[\mathbf{T},\mathbf{o}]$ be the component of
$0$ in the record graph of $(\mathbb{Z},X^{\prime})$ and let
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ 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 46, the distribution of
$[\mathbf{T},\mathbf{o}]$ is $TGWT(\alpha)$, which is unimodular; and by Lemma
47, the distribution of $[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ is
$GW(\alpha)$, which has finite mean size. It is shown below that
$[\mathbf{T},\mathbf{o}]$ is the typical re-rooting of
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$.

For any measurable subset $A$ of $\mathcal{T}_{*}$, consider the function
$g_{A}:\mathcal{T}_{**}\to\mathbb{R}_{\geq 0}$ defined by
$g_{A}([T,u,v])=\mathbf{1}_{A}([T,u])\mathbf{1}\\{F(v)=v\\}$. Then, for any
measurable set $A$, one has,

$\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 exactly one vertex that does not have a parent. Similarly,

$\displaystyle\mathbb{E}\left[\sum_{u\in
V(\mathbf{T})}g_{A}([\mathbf{T},u,\mathbf{o}])\right]$
$\displaystyle=\mathbb{E}\left[\mathbf{1}\\{F(\mathbf{o})=\mathbf{o}\\}\sum_{u\in
V(\mathbf{T})}\mathbf{1}_{A}([\mathbf{T},u])\right]$
$\displaystyle=\mathbb{E}\left[\sum_{u\in
V(\mathbf{T}^{\prime})}\mathbf{1}_{A}([\mathbf{T}^{\prime},u])\right]\mathbb{P}[F(\mathbf{o})=\mathbf{o}].$

The last step follows since $[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ 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}]$, one gets

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

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

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

∎

The next proposition gives a characterizing condition for a Typically rooted
Galton-Watson Tree. The proof of this proposition depends on the following
lemma which says that every unimodular tree is characterised by the descendant
tree of its root.

######  Lemma 49.

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}\overset{\mathcal{D}}{=}[\mathbf{T},\mathbf{o}]_{r}$
for all $n>r$.

For any measurable set $A$,

$\displaystyle\mathbb{P}[[D(F^{n}(\mathbf{o})),\mathbf{o}]\in A]$
$\displaystyle=\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,

$\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 49 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}]$. The connection between [2,
Proposition 10] and Lemma 49 follows from the observation that 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 49 is also applicable to the unimodular Family trees of class
$\mathcal{I}/\mathcal{F}$. For more details on this connection, see [5,
Bibliographical Comments (Section 6.3)].

The following proposition and its proof are analogous to the characterization
of Eternal Galton-Watson Tree of [5]. However, the following proposition
differs from the latter as its statement is about finite Family Trees, whereas
the latter is about EFTs.

In the following proposition, only the random objects are denoted in bold
letters.

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)\backslash D(o))\cup\\{o\\}$. For any vertex $u$ of $T$, let
$c_{j}(u)$ denote the $j$-th child of $u$.

######  Proposition 50 (Characterization of $TGWT$).

A random _finite_ Family Tree $[\mathbf{T},\mathbf{o}]$ is a Typically rooted
Galton-Watson Tree ($TGWT$) if and only if

  1. 1.

it is unimodular, and

  2. 2.

the number of children of the root $d_{1}(\mathbf{o})$ is independent of the
non-descendant tree of the root $\mathbf{o}$.

###### Proof.

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

It is now shown that if a random finite Family Tree $[\mathbf{T},\mathbf{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^{\prime};A_{1},A_{2},\cdots,A_{k})$ be an event of the form

$d_{1}(o)=k,D^{c}(o)\in A^{\prime},D(c_{1}(o))\in A_{1},\cdots,D(c_{k}(o))\in
A_{k}.$ (25)

By Lemma 49, any unimodular Family Tree is characterized by the descendant
tree of its root. So, it is sufficient to prove that

$\mathbb{P}[A]=\mathbb{P}[d_{1}(\mathbf{o})=k]\mathbb{P}[D^{c}(\mathbf{o})\in
A^{\prime}]\left(\prod_{i=1}^{k}\mathbb{P}[D(\mathbf{o})\in A_{i}]\right),$
(26)

for any such event $A$ of the form given by Eq (25). Assume further that the
events $A_{1},A_{2},\cdots,A_{k}$ depend only up to the $n$-th generation of
$o$, which is the union of $D_{1}(o)$, $D_{2}(o)$, $\cdots$, $D_{n}(o)$. It
suffices to show Eq. (26) for such events because of the local topology.

The result is proved by induction on $n$. For $n=0$, one has
$\mathbb{P}[A]=\mathbb{P}[d_{1}(\mathbf{o})=k]\mathbb{P}[D^{c}(\mathbf{o})\in
A^{\prime}]$ by condition $2$ of the hypothesis. So, assume that the result is
true for $n-1$. Let $n\geq 1$ and $1\leq j\leq 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\leq j\leq k$,

$\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]).$ (27)

Note that, since $k\geq 1$, the event $\\{[T,o]\in A\\}$ is a subset of the
event $\\{D_{1}(o)\not=\emptyset\\}$ Applying Eq. (27) for $j=1$, one gets

$\displaystyle\mathbb{P}[A]$ $\displaystyle=\mathbb{E}\left[\sum_{u\in
V(\mathbf{T})}\mathbf{1}_{A}[\mathbf{T},F(u)]\mathbf{1}\\{u=c_{1}(\mathbf{o})\\}\mathbf{1}\\{u\in
D_{1}(\mathbf{o})\\}\right]$ $\displaystyle=\mathbb{E}\left[\sum_{u\in
V(\mathbf{T})}\mathbf{1}_{A}[\mathbf{T},F(\mathbf{o})]\mathbf{1}\\{\mathbf{o}=c_{1}(u)\\}\mathbf{1}\\{\mathbf{o}\in
D_{1}(u)\\}\right]$ (28)
$\displaystyle=\mathbb{E}\left[\mathbf{1}_{A}[\mathbf{T},F(\mathbf{o})]\mathbf{1}\\{\mathbf{o}\in
E\\}\mathbf{1}\\{\mathbf{o}=c_{1}(F(\mathbf{o}))\\}\right]$
$\displaystyle=\mathbb{P}[\mathbf{o}\in
E,\mathbf{o}=c_{1}(F(\mathbf{o})),[\mathbf{T},F(\mathbf{o})]\in A]$ (29)
$\displaystyle=\mathbb{P}[D(\mathbf{o})\in A_{1},\mathbf{o}\in
E,\mathbf{o}=c_{1}(F(\mathbf{o})),[\mathbf{T},F(\mathbf{o})]\in
A(A^{\prime};\mathcal{T}_{*},A_{2},\cdots,A_{k})].$

In the above, Eq. (28) 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,

$\displaystyle\mathbb{P}[A]$ $\displaystyle=\mathbb{P}[D(\mathbf{o})\in
A_{1}]\mathbb{P}[\mathbf{o}\in
E,\mathbf{o}=c_{1}(F(\mathbf{o})),[\mathbf{T},F(\mathbf{o})]\in
A(A^{\prime};\mathcal{T}_{*},A_{2},\cdots,A_{k})]$
$\displaystyle=\mathbb{P}[D(\mathbf{o})\in
A_{1}]\mathbb{P}[A(A^{\prime};\mathcal{T}_{*},A_{2},\cdots,A_{k})].$

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

Applying Eq.(27) with $j=2$ to
$A(A^{\prime};\mathcal{T}_{*},A_{2},\cdots,A_{k})$, one gets

$\displaystyle\mathbb{P}[A$
$\displaystyle(A^{\prime};\mathcal{T}_{*},A_{2},\cdots,A_{k})]$
$\displaystyle=\mathbb{P}[D(\mathbf{o})\in A_{2}]\mathbb{P}[\mathbf{o}\in
E,\mathbf{o}=c_{1}(F(\mathbf{o})),[\mathbf{T},F(\mathbf{o})]\in
A(A^{\prime};\mathcal{T}_{*},\mathcal{T}_{*},\cdots,A_{k})]$
$\displaystyle=\mathbb{P}[D(\mathbf{o})\in
A_{2}]\mathbb{P}[A(A^{\prime};\mathcal{T}_{*},\mathcal{T}_{*},\cdots,A_{k})].$

By iterating the same procedure for $j=3,4,\cdots$, one gets

$\displaystyle\mathbb{P}[A]$
$\displaystyle=\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^{\prime}]$
$\displaystyle=\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^{\prime}].$

Thus, Eq. (26) holds, which completes the proof. ∎

####  4.4.2 Zero mean

######  Theorem 51.

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be a sequence of random variables satisfying
the conditions of Eq. 3, $(\mathbb{Z},X)$ be its associated network, and
$[\mathbf{T},0]$ be the connected component of $0$ in the record graph of
$(\mathbb{Z},X)$. If $\mathbb{E}[X_{0}]=0$, then $[\mathbf{T},0]$ is the
ordered Eternal Galton-Watson Tree $EGWT(\pi)$ with offspring distribution
$\pi\stackrel{{\scriptstyle\mathcal{D}}}{{=}}X_{0}+1$.

###### Proof.

It is first shown that $[\mathbf{T},0]$ satisfies the condition of Theorem 11.
Observe that $L_{X}(0)$ is a stopping time for the random walk with increments
$(X_{-n})_{n\geq 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=1}^{n=L_{X}(0)}$. Let $(\mathbf{T}^{\prime},0)$ denote the non-
descendant tree of $o$, i.e., the tree generated by $(\mathbf{T}\backslash
D(0))\cup\\{0\\}$. By Lemma 17, the subtree $(D(0),0)$ is a function of $Z$
and the subtree $(\mathbf{T}^{\prime},0)$ is a function of
$Y\cup(X_{n})_{n\geq 0}$. So, the unordered tree $(D(0),0)$ is independent of
the unordered tree $(\mathbf{T}^{\prime},0)$. The second part of Lemma 33
implies that, conditionally on the event that $0$ has children, the order of a
child is independent of $Y\cup(X_{n})_{n\geq 0}$, whereas the order of any
vertex in $(\mathbf{T}^{\prime},0)$ is a function of $Y\cup(X_{n})_{n\geq 0}$.
Thus, the ordered subtree $(D(0),0)$ is independent of the ordered subtree
$(\mathbf{T}^{\prime},0)$. So, $[\mathbf{T},0]$ satisfies the sufficient
condition of Theorem 11.

The first statement of Lemma 33 implies that
$d_{1}(0)=X_{-1}+1\overset{\mathcal{D}}{=}X_{0}+1$, and thus completes the
proof. ∎

####  4.4.3 Positive mean

Let $X=(X_{n})_{n\in\mathbb{Z}}$ be an i.i.d. sequence that satisfies the
conditions of Eq. (3) with $0<\mathbb{E}[X_{0}]\leq\infty$, and
$(\mathbb{Z},X)$ be its associated network.

Recall the following notations of Subsection 4.2. Let $\eta_{-1}$ be the
hitting time at $-1$ defined as in Eq. (19) for $j=-1$, and
$c=\mathbb{P}[\eta_{-1}<\infty]$ be the probability that the hitting time at
$-1$ is finite. Let $[\mathbf{T},\mathbf{o}]$ be the connected component of
$0$ (with root $0=\mathbf{o}$) in the record graph of $(\mathbb{Z},X)$.

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

$\displaystyle\tilde{\pi}(k)$ $\displaystyle=c^{k-1}\mathbb{P}[X_{0}=k-1],$
(30) $\displaystyle\bar{\pi}(k)$ $\displaystyle=\mathbb{P}[X_{0}\geq k]c^{k}.$

######  Remark 52.

The fact that $\bar{\pi}$ is a probability distribution follows from Eq. (33),
in the proof of Theorem 53. Similarly, it follows from Eq. (21) that
$\tilde{\pi}$ is a probability distribution.

Recall the construction bi-variate Eternal Kesten Tree (see Subsection 4.3.2).
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 $d_{1}(\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 re-rooted joining of
$([\mathbf{T}_{i},\mathbf{o}_{i}])_{i\in\mathbb{Z}}$ is the unimodularised
$EKT(\bar{\pi},\tilde{\pi})$. Since the mean $m(\tilde{\pi})<1$, the typically
re-rooted joining operation is well-defined for this sequence. Recall the ECS
order on the joining of $([\mathbf{T}_{i},\mathbf{o}_{i}])_{i\in\mathbb{Z}}$
(see Subsection 4.3.2).

######  Theorem 53.

If $0<\mathbb{E}[X_{0}]\leq\infty$, then the distribution of
$[\mathbf{T},\mathbf{o}]$ is the unimodularised ECS ordered
$EKT(\bar{\pi},\tilde{\pi})$.

###### Proof.

Since the random walk has positive drift, by Theorem 29, the unimodular EFT
$[\mathbf{T},\mathbf{o}]$ is of class $\mathcal{I}/\mathcal{F}$. Let
$\mathbf{o}\in\mathrel{\text{\ooalign{$\swarrow$\cr$\nearrow$}}}$ denote the
event that $\mathbf{o}$ belongs to the bi-infinite path of $\mathbf{T}$. Let
$[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ be the conditioned Family Tree
obtained from $[\mathbf{T},\mathbf{o}]$ by conditioning on the event
$\mathbf{o}\in\mathrel{\text{\ooalign{$\swarrow$\cr$\nearrow$}}}$, denoted as
$[\mathbf{T},\mathbf{o}]|\mathbf{o}\in\mathrel{\text{\ooalign{$\swarrow$\cr$\nearrow$}}}$.
By Theorem 16, $[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ is the joining of
some stationary sequence of Family Trees
$([\mathbf{T}^{\prime}_{i},\mathbf{o}^{\prime}_{i}])_{i\in\mathbb{Z}}$. The
proof is complete once it is shown that this sequence is i.i.d. (shown in
_Step 1_), that the following distributional equality holds:
$[\mathbf{T}^{\prime}_{1},\mathbf{o}^{\prime}_{1}]\overset{\mathcal{D}}{=}[\mathbf{T}_{0},\mathbf{o}_{0}]$
(shown in _Step 2_), and that $[\mathbf{T}^{\prime},\mathbf{o}^{\prime}]$ has
ECS order — $\mathbf{o}_{i}^{\prime}$ is the smallest child of
$\mathbf{o}_{i+1}^{\prime}$ in $\mathbf{T}^{\prime}$, for all $i\in\mathbb{Z}$
(shown in _Step 3_).

_Step 1,
$([\mathbf{T}^{\prime}_{i},\mathbf{o}^{\prime}_{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 17,
$\mathbf{o}\in\mathrel{\text{\ooalign{$\swarrow$\cr$\nearrow$}}}$ if and only
if $L_{X}(0)=\infty$, and the latter condition holds if and only if $S_{n}\leq
0,\forall n\leq-1$.

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

$([\mathfrak{S}(F^{n}(\mathbf{o}))\backslash\mathfrak{S}(F^{n-1}(\mathbf{o})),F^{n}(\mathbf{o})])_{n\geq
1}|\mathbf{o}\in\mathrel{\text{\ooalign{$\swarrow$\cr$\nearrow$}}}$

(distribution obtained by conditioning on
$\mathbf{o}\in\mathrel{\text{\ooalign{$\swarrow$\cr$\nearrow$}}}$), 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 ancestor of
order $n$ of $\mathbf{o}$). On the event
$\mathbf{o}\in\mathrel{\text{\ooalign{$\swarrow$\cr$\nearrow$}}}$, each
subtree