Consider the first sum. We have,

$$
\begin{align*}
& \mathbb{P}[\mathbf{T}, F^n(\mathbf{o}), Z]_r \in A, M(\mathbf{o}) < n-r] \\
&= \sum_{k=0}^{n-r-1} \mathbb{P}[[\mathbf{T}, F^n(\mathbf{o}), Z]_r \in A, M(\mathbf{o}) = k] \\
&= \sum_{k=0}^{n-r-1} \mathbb{P}[[\mathbf{T}, F^{n-k}(\mathbf{o}^*), Z]_r \in A, M(\mathbf{o}) = k].
\end{align*}
$$

The last equation follows by the definition of $\mathbf{o}^* := F^{M(\mathbf{o})}(\mathbf{o})$. By the defi-
nition of $[\mathbf{T}, \mathbf{o}, Z]$ (see Eq. (4.5.2)), the last equation is equal to

$$
\sum_{k=0}^{n-r-1} \frac{\mathbb{E}[\sum_{u \in V(\mathbf{T}_0)} \mathbf{1}_A([\mathbf{T}', F^{n-k}(u^*), Z']_r) \mathbf{1}\{M(u) = k\}]}{\mathbb{E}[\#V(\mathbf{T}_0)]} \quad (4.5.3)
$$

On the tree **T'**, we have $F^{n-k}(u^*) = \mathbf{o}_{n-k}$, for all $u \in V(\mathbf{T}_0)$ and for all
$0 \le k \le n-r-1$. Since $([\mathbf{T}_i, \mathbf{o}_i, Z_i]_{i \in \mathbb{Z}}$ is an i.i.d. sequence, the distribution
of $[\mathbf{T}', \mathbf{o}_{n-k}, Z']_r$ is independent of $[\mathbf{T}_0, \mathbf{o}_0, Z_0]$ for all $0 \le k \le n-r-1$. By
applying this fact to Eq. (4.5.3), it is equal to

$$
\sum_{k=0}^{n-r-1} \frac{\mathbb{E}[\sum_{u \in V(\mathbf{T}_0)} \mathbf{1}_A([\mathbf{T}', \mathbf{o}_{n-k}, Z']) \mathbf{1}\{M(u) = k\}]}{\mathbb{E}[\#V(\mathbf{T}_0)]} \\
= \sum_{k=0}^{n-r-1} \frac{\mathbb{P}[[\mathbf{T}', \mathbf{o}_{n-k}, Z']_r \in A] \mathbb{E}[\sum_{u \in V(\mathbf{T}_0)} \mathbf{1}\{M(u) = k\}]}{\mathbb{E}[\#V(\mathbf{T}_0)]}.
$$

The distribution of $[\mathbf{T}', \mathbf{o}_{n-k}, Z']_r$ is identical to that of $[\mathbf{T}', \mathbf{o}', Z']_r$ for all $n > 2r + k$, by the construction of $\text{MEKT}(\alpha, \beta)$. Using this and applying Eq. (4.5.2) to the last equation, we get

$$
\begin{align*}
\mathbb{P}[[\mathbf{T}, F^n(\mathbf{o}), Z]_r \in A, M(\mathbf{o}) < n-r] &= \mathbb{P}[[\mathbf{T}', \mathbf{o}', Z']_r \in A] \sum_{k=0}^{n-r-1} \mathbb{P}[M(\mathbf{o}) = k] \\
&= \mathbb{P}[[\mathbf{T}', \mathbf{o}', Z']_r \in A] \mathbb{P}[M(\mathbf{o}) < n-r].
\end{align*}
$$

As $n \to \infty$, $\mathbb{P}[M(\mathbf{o}) < n - r] \to 1$. Therefore,

$$
\mathbb{P}[[\mathbf{T}, F^n(\mathbf{o}), Z]_r \in A] \xrightarrow{n \to \infty} \mathbb{P}[[\mathbf{T}', \mathbf{o}', Z']_r \in A].
$$

Since this is true for any $r \ge 1$, we have

$$
[\mathbf{T}, F^n(\mathbf{o}), Z] \xrightarrow{n \to \infty} [\mathbf{T}', \mathbf{o}', Z'].
$$

□
*Remark 83.* From the construction of *MEKT*(α, β), it follows that both [**T'**, F(**o'**), Z'] and [**T'**, **o'**, Z'] have the same distribution. So, the marked EFT [**T'**, **o'**, Z'] satisfies the Mecke's invariant measure equation. Therefore, by Lemma 66, **o'** has a.s. infinitely many descendants, which can also be seen directly from the construction of *MEKT*(α, β).
<figure><img src="image_24.png" /></figure>
# Chapter 5

## Record vertex-shift probability
for the random walk case

In this chapter, we focus again on the record vertex-shift on the network [Z, 0, X], where X is an i.i.d. sequence as in Def. 22 and satisfies $E[X_0] \ge 0$. We show the existence of a unique R-probability (i.e., a vertex-shift probability under record vertex-shift) when $E[X_0] \ge 0$. Although one could show the same when $E[X_0] < 0$, we did not consider it since the component of 0 can only give partial information of the trajectory of random walk associated to X.

We use the FB Lemma 61 to prove the existence and uniqueness of the R-probability. We define two maps namely the backward map $\Phi_R$ and the extended backward map $\hat{\Phi}_R$ that satisfy the hypotheses of the FB Lemma when $E[X_0] = 0$ and $E[X_0] > 0$ respectively. This is done in several sections. We also give constructions for the R-probability in these two cases and prove that the constructions indeed generate the R-probability.

(In French) Dans ce chapitre, nous nous intéressons à nouveau au décalage de sommet des records sur le réseau [Z, 0, X], où X est une suite i.i.d. comme dans la définition 22 et qui satisfait $E[X_0] \ge 0$. Nous montrons l'existence d'une R-probabilité unique (c'est-à-dire une probabilité de décalage de sommet associée au décalage de sommet des records) lorsque $E[X_0] \ge 0$. Bien que l'on puisse montrer la même chose lorsque $E[X_0] < 0$, nous ne l'avons pas considéré car la composante de 0 ne peut donner qu'une information partielle sur la trajectoire de la marche aléatoire associée à X.

Nous utilisons le lemme FB 61 pour prouver l'existence et l'unicité de la R-probabilité. Nous définissons deux fonctions nommées la fonction
réciproque $\Phi_R$ et la fonction réciproque étendue $\hat{\Phi}_R$ qui satisfont les hypothèses du lemme FB lorsque $\mathbb{E}[X_0] = 0$ et $\mathbb{E}[X_0] > 0$ respectivement. Ceci est fait dans plusieurs sections. Nous donnons également des constructions pour la R-probabilité dans ces deux cas et prouvons que les constructions génèrent bien la R-probabilité.

## 5.1 The backward map of the record vertex-shift

In this section, we define a backward map $\Phi_R : \mathcal{T}_* \to \mathcal{G}_*$, where $\mathcal{T}_*$ is the subset of $\mathcal{T}_*$ consisting of all ordered Family Trees that have at most one bi-infinite F-path. Recall that the forward map $\Psi_R : \mathcal{G}_* \to \mathcal{T}_*$ maps a network of the form $[\mathbb{Z}, 0, x]$ to $[\mathbb{Z}^R(0), 0]$, where $x$ is a sample of the i.i.d. sequence $X$ with $\mathbb{E}[X_0] = 0$, and $\mathbb{Z}^R(0)$ is the connected component of 0 of the record graph $\mathbb{Z}^R$ of $[\mathbb{Z}, 0, x]$. For any ordered Family Tree that has at most one bi-infinite path, using the depth-first search order and the tree structure, we can define a sequence in such a way that the record graph associated to the sequence is the Family Tree. This map essentially depends on a sequence of vertices of the Family Tree called succession line, which can be seen as a factor map from $\mathbb{Z}$ to the vertices of a unimodular Family Tree ([11]).

This map extends the usual depth-first search encoding of finite ordered trees, defined in [14, Chapter 5], [16], to infinite ordered Family Trees that have at most one bi-infinite path.

In the next sections, we show that the map $\Phi_R$ satisfies the three conditions of the FB Lemma 61 when $\mathbb{E}[X_0] = 0$. However, this map fails to be bijective when $\mathbb{E}[X_0] > 0$. So, in Section 5.3, we extend this map to the space of marked Family Trees in order to obtain a bijective map.

In Subsection 3.2 of Chapter 3, we show that the R-graph of $[\mathbb{Z}, 0, X]$ when $\mathbb{E}[X_0] = 0$ is a unimodular ordered Eternal Galton-Watson Tree $EGWT(\pi)$ with offspring distribution $\pi$, where $\pi$ is the distribution of $X_0 + 1$. The parent vertex-shift probability of $EGWT(\pi)$ is shown to be the Eternal Kesten Tree $EKT(\pi)$ (see Subsection 4.5 for the definition of $EKT(\pi)$). In contrast to $EGWT(\pi)$, when $\pi(1) < 1$, a realization of $EKT(\pi)$ has a unique bi-infinite path. So, the map $\Phi_R$ should be defined such that it is continuous on the support of $EKT(\pi)$ in order to satisfy the hypotheses of FB Lemma 61. Therefore, our first goal is to define $\Phi_R$ on
ordered Family Trees that have at most one bi-infinite path. We achieve
this goal using the properties of the RLS order. Then, we show that the
defined map $\Phi_R$ is continuous $EKT(\pi)$-a.s..

Let $T$ be an ordered Family Tree. Consider the RLS order $<$ on the
vertices of $T$ and recall that for any two vertices $u$ and $v$, we say $u$ succeeds
$v$ if $u < v$ (equivalently $v$ precedes $u$).

**Definition 84.** For any vertex $u \in T$, let $B(u) := \{v \in T : v < u\}$ and define $b(u) = \max\{v \in B(u)\}$ if it exists, where $\max$ is taken with respect to $<$. Similarly, let $A(u) := \{v \in T : v > u\}$ and $a(u) = \min\{u \in A(u)\}$ if it exists, where $\min$ is taken with respect to $<$.

According to the RLS order, $b(u)$ has the highest precedence over all
those vertices that succeed $u$, and $a(u)$ has the smallest precedence among
those vertices that precede $u$.

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

*Proof.* By hypothesis, $B(u)$ is not empty. So, either of the following two
cases occur:

* 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 \ge 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 an $m$ 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)$.

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

**Lemma 86.** Let $T$ be an ordered Family Tree, $u$ be a non-maximal vertex of $T$. If every sibling of $u$ that precedes $u$ has finitely many descendants, then $a(u)$ exists.

*Proof.* If $u$ does not have a sibling that precedes $u$, then $a(u) = F(u)$ (by hypothesis $F(u) \neq u$ in this case). Otherwise, let $w$ be the smallest sibling of $u$ larger than $u$. It has finitely many descendants by hypothesis. Then $a(u)$ is the minimal vertex of $D(w)$ (recall that $D(w) = \{v \in V(T)\setminus\{w\} : F^m(v) = w$ for some $m > 0\} \cup \{w\}$). $\square$

<figure><img src="image_26.png" /></figure>
**Definition 87.** Consider an ordered rooted Eternal Family Tree $(T, o)$ that has at most one bi-infinite $F$-path passing through $o$. With the RLS order, we call **succession line** of $(T, o)$ the sequence $U((T, o)) = (u_n)_{n \in \mathbb{Z}}$ iteratively given by $u_0 = o$ and,

$$ u_n = \begin{cases} b(u_{n+1}) & \text{if it exists} \\ u_{n+1} & \text{otherwise} \end{cases} \quad \text{for } n < 0, \qquad (5.1.1) $$

$$ u_n = \begin{cases} a(u_{n-1}) & \text{if it exists} \\ u_{n-1} & \text{otherwise} \end{cases} \quad \text{for } n > 0. $$

Observe that this is the unique sequence that satisfies $u_0 = o$, and $u_{n-1}$ is the immediate successor of $u_n$, when they are distinct, for all $n \in \mathbb{Z}$. With the above preparation, we are ready to define the backward map which plays a crucial role in the rest of the chapter.

**Definition 88.** Define the **backward map of the record vertex-shift** $\Phi_R : \mathcal{T}' \to \mathcal{G}_*$ as the function that maps $[T, o] \in \mathcal{T}'$ to

$$ \Phi_R([T, o]) = [\mathbb{Z}, 0, x((T, o))], \qquad (5.1.2) $$

where $x((T, o)) = (x_n)_{n \in \mathbb{Z}}$ is given by $x_n = d_1(u_{n+1}) - 1$ and $(u_n)_{n \in \mathbb{Z}} = U((T, o))$.

Note that $\Phi_R$ is well-defined: if $(T, o) \sim (T', o')$ be two isomorphic ordered Family Trees and $(u_n)_{n \in \mathbb{Z}}$ and $(u'_n)_{n \in \mathbb{Z}}$ be their respective succession lines passing through $o, o'$ respectively, then $d_1(u_n) - 1 = d_1(u'_n) - 1$ for all $n \in \mathbb{Z}$, which implies that $x((T, o)) = x((T', o'))$. In general the succession line of a rooted Family Tree $[T, o]$ passing through $o$ may not contain all the vertices of $T$. But, if $[T, o]$ is a sample of component of 0 in the record graph of $[\mathbb{Z}, 0, X]$ with $\mathbb{E}[X_0] \ge 0$, then we show that the succession line of $[T, o]$ contains every vertex of $T$ (see Lemma 89 and Remark 90).

**Lemma 89.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be the i.i.d. increments of a skip-free to the left random walk with $\mathbb{E}[X_0] \ge 0$ and $[\mathbb{Z}, 0, X]$ be the network associated to $X$. Let $[\mathbf{T}, 0]$ be the component of 0 in the record graph of $[\mathbb{Z}, 0, X]$ rooted at 0. Then, a.s., the succession line $U((\mathbf{T}, o))$ consists of distinct entries.

*Proof.* Observe that the set of minimal vertices of $\mathbf{T}$ is a covariant subset. It can only be either empty or a singleton, because $\mathbf{T}$ is totally ordered by the
RLS order. But $[\mathbf{T}, \mathbf{o}]$ is unimodular (Lemma 16), and $\#V(\mathbf{T})$ is infinite since $\mathbb{E}[X_0] \ge 0$, in fact $V(\mathbf{T}) = \mathbb{Z}$ since the record graph is connected when $\mathbb{E}[X_0] \ge 0$ (see Proposition 40 and Proposition 41). Therefore, by No Infinite/Finite inclusion Lemma 12, a.s., the minimal vertex does not exist. Therefore, by Lemma 85, almost surely, the successor of $u$, $b(u)$ exists for all $u \in V(\mathbf{T})$. Since $a(b(u)) = u$ for all $u \in V(\mathbf{T})$, $a(v)$ exists for all $v$ in the range of the map $b$. But $b$ is injective a.s. and hence surjective a.s. (by the unimodularity of $[\mathbf{T}, \mathbf{o}]$). Therefore, the range of $b$ is $V(\mathbf{T})$ a.s. and hence, a.s., $a(u)$ exists for all $u \in V(\mathbf{T})$. Thus, the map $n \mapsto u_n$ from $\mathbb{Z}$ to $V(\mathbf{T})$ is injective, which implies that all the elements of the sequence $U((\mathbf{T}, \mathbf{o}))$ are distinct. $\square$

**Remark 90.** Observe that $U(\Psi_R([\mathbb{Z}, 0, X])) = (u_n)_{n \in \mathbb{Z}} = (n)_{n \in \mathbb{Z}}$, when the i.i.d. sequence $X = (X_n)_{n \in \mathbb{Z}}$ satisfies $\mathbb{E}[X_0] \ge 0$. This follows by combining Lemma 33 with the facts that the $R$-graph $\mathbb{Z}^R$ of $[\mathbb{Z}, 0, X]$ is a.s. connected, and the map $n \mapsto u_n$ from $\mathbb{Z}$ to $V(\mathbb{Z}^R) = \mathbb{Z}$ is injective. Indeed, by definition, $B(0) = \{i \in \mathbb{Z} : i < 0\}$. But, by Lemma 33, $i \in B(0) \iff i < 0$. Therefore, $B(0) = \{i \in \mathbb{Z} : i < 0\}$. Hence, $b(0) = -1$ and $u_{-1} = -1$. By induction, assume $u_{-n} = -n$. Consider $B(u_{-n}) = \{i \in \mathbb{Z} : i < -n\} = \{i \in \mathbb{Z} : i < -n\}$. Therefore, $u_{-(n+1)} = -(n+1)$. Similarly, we could show that $a(u_n) = n, \forall n \ge 0$.

**Lemma 91.** Let $[\mathbf{T}', \mathbf{o}']$ be a random ordered Family Tree whose distribution is EKT($\pi$), where $\pi$ is a probability distribution on $\{0, 1, 2, \dots\}$ with mean $m(\pi) = 1$. Then, the succession line $U((\mathbf{T}', \mathbf{o}'))$ consists of distinct entries.

*Proof.* Let $[T', o']$ be a realization of EKT($\pi$). Since $T'$ has a unique bi-infinite $F$-path passing through the root $o$, by Lemma 85, $b(u)$ exists for all $u \in V(T')$. If $u$ satisfies the property that every sibling of $u$ that precedes $u$ has finitely many descendants, then, by Lemma 86, $a(u)$ exists. In this case, $a(u)$ also satisfies the same property. Since the root $o$ satisfies this property, the map $n \mapsto u_n$ from $\mathbb{Z}$ to $V(T')$ is injective. Thus, all the elements of $U(\mathbf{T}', \mathbf{o}')$ are distinct. $\square$

The following remark is used in the later sections to describe the $R$-probability from EKT.

**Remark 92.** Let $[T', o']$ be a realization of EKT($\pi$) and $\L(([T', o'])$ denote its bi-infinite $F$-path. Since $o' \in \L$ ($[T', o']$), we could define the following. The **positive part** of $[T', o']$ is the rooted Family Tree $[T'^+, o']$, where $T'^+$
is the subtree of $T'$ induced by the vertices $\{u \in V(T') : u > v \text{ for some } v \in \nabla ([T', o'])\}$. Observe that the set of elements of $U((T', o'))$ is equal to $V(T')$.

## 5.2 Bijectivity and continuity of the backward map

We first show that $\Psi_R \circ \Phi_R([T, o]) = [T, o]$ a.s. for every realization $[T, o]$ of the ordered EGWT($\pi$), where the mean $m(\pi) = 1$, using the following lemma.

**Lemma 93.** Let $T$ be a finite ordered tree and $v_1 < v_2 < \dots < v_n$ be the vertices of $T$ ordered according to the RLS order. Then,

$$1. \sum_{i=1}^{n} (d_1(v_i) - 1) = -1.$$

$$2. \sum_{i=1}^{k} (d_1(v_i) - 1) < 0, \text{ for all } 1 < k \le n.$$

*Proof.* The first equation follows from the fact that for a finite tree $T$,

$$\sum_{u \in V(T)} d_1(u) = \#V(T) - 1.$$

We prove the second equation by induction on $k$. If $k = 1$ then $v_1$ is a leaf and hence $d_1(v_1) - 1 = -1$. Now, assume that the statement is true for $1 \le m \le k$, where $k > 1$. Observe that by the RLS order, either $v_{k+1}$ is a leaf or $v_{k+1}$ is the parent of $v_k$. In the latter case, there exists $1 \le j \le k$ such that $v_j < v_{j+1} < \dots < v_k$ (written according to the RLS order) are all the descendants of $v_{k+1}$. If $v_{k+1}$ is a leaf then, by induction,

$$\sum_{i=1}^{k+1} (d_1(v_i) - 1) = \sum_{i=1}^{k} (d_1(v_i) - 1) + d_1(v_{k+1}) - 1 < -1.$$

The only other possibility is that $v_{k+1}$ is the parent of $v_k$. Then,

$$\sum_{i=1}^{k+1} (d_1(v_i) - 1) = \sum_{i=1}^{j-1} (d_1(v_i) - 1) + \sum_{i=j}^{k+1} (d_1(v_i) - 1) \le 0 + (-1).$$

The last step follows from the fact that the first sum on the right-hand side is at most 0 (by induction), while the second sum is on the descendant tree of $v_{k+1}$ which is equal to $-1$ by the first result of the lemma. $\square$
## 5.2. BIJECTIVITY AND CONTINUITY OF THE BACKWARD MAP 99

**Remark 94.** Let $v_1 < v_2 < \dots < v_n$ be the vertices of a finite ordered tree, ordered according to RLS order. Then using Lemma 93 we obtain, for any $1 < k < n$,

$$ \sum_{i=k+1}^{n} (d_1(v_i) - 1) = \sum_{i=1}^{n} (d_1(v_i) - 1) - \sum_{i=1}^{k} (d_1(v_i) - 1) \geq -1 - (-1) \geq 0. $$

**Proposition 95.** *Almost surely, every realisation $[T, o]$ of the ordered EGWT($\pi$), where the mean $m(\pi) = 1$, satisfies $\Psi_R \circ \Phi_R([T, o]) = [T, o]$.*

*Proof.* Let $(u_n)_{n \in \mathbb{Z}} = U((T, o))$ be the succession line of $(T, o)$ and $[\mathbb{Z}, 0, x] = \Phi_R([T, o])$, where $x = (x_n)_{n \in \mathbb{Z}}$ is such that $x_n = d_1(u_n) - 1$ is the mark of the edge $(n, n+1)$, for all $n \in \mathbb{Z}$.

First, observe that the map $\alpha: \mathbb{Z} \to V(T)$ defined by $\alpha(n) = u_n$, for all $n \in \mathbb{Z}$ is bijective. This follows because, every vertex $v$ of $T$ has finitely many descendants. So, there are only finitely many vertices between $o$ and $v$ according to the RLS order, and hence $u_n = v$ for some $n \in \mathbb{Z}$. Therefore, $\alpha$ is surjective. The injectivity of the map $\alpha$ follows from Lemma 89 because $[T, o]$ is a realisation of the component of 0 in the record graph of $[\mathbb{Z}, 0, X]$ when $\mathbb{E}[X_0] = 0$. We now prove that the bijective map $\alpha: \mathbb{Z} \to V(T)$ defined by $\alpha(n) = u_n$, for all $n \in \mathbb{Z}$, induces a rooted network isomorphism $\alpha$ from $\Psi_R([\mathbb{Z}, 0, x])$ to $(T, o)$. Note that, if $u_j$ is a parent of $u_i$ in $T$ for some integers $i$ and $j$ then $j > i$, which follows because $(u_n)_{n \in \mathbb{Z}}$ is the succession line of $(T, o)$. In view of this, to prove that $\alpha$ induces a rooted network isomorphism, it is enough to show that for all $i \in \mathbb{Z}$, if $u_j$ is the parent of $u_i$ in $T$ for some $j > i$, then $j = R_x(i)$ (since every vertex has at most one parent).

Let $i \in \mathbb{Z}$ and $u_j$ be the parent of $u_i$ in $T$ for some integer $j > i$. If $j = i + 1$, then $x_i = d_1(u_{i+1}) - 1 \geq 0$, because $u_i$ is a child of $u_{i+1}$. Hence, $R_x(i) = i + 1$.

So, let us assume that $j > i + 1$. This implies that either $u_{i+1}$ is a leaf and a descendant of a sibling of $u_i$, or $u_{i+1}$ is a leaf and a sibling of $u_i$. The descendant tree of $u_j$ is a finite ordered tree, as $[T, o]$ is a realization of EGWT($\pi$). Let $u_{i_1} < u_{i_2} < \dots < u_{i_n}$ be all the elder siblings of $u_i$, and $T_1, T_2, \dots, T_n$ be their descendant trees respectively. For any $i < k < j$, let $l(k)$ be the smallest element of the set $\{1, 2, \dots, n\}$ such that $\{u_{i+1}, u_{i+2}, \dots, u_k\} \subset V(T_1) \cup V(T_2) \cup \dots V(T_{l(k)})$, and $u_{k_1}$ be the smallest vertex of $T_{l(k)}$.
Then, the sum $y(i, k) = \sum_{m=i}^{k-1} x_m = \sum_{m=i+1}^{k} (d_1(u_m) - 1)$ can be written as

$$y(i, k) = \left( \sum_{u \in V(T_1)} d_1(u) - 1 \right) + \cdots + \left( \sum_{u \in V(T_{l(k)-1})} d_1(u) - 1 \right) + \sum_{m=k_1}^{k} (d_1(u_m) - 1) \\ < (-1) + \cdots + (-1) + \sum_{m=k_1}^{k} (d_1(u_m) - 1) < 0,$$

with the notation that $V(T_0)$ is just an empty set. The last steps follow from the first and the second statements of Lemma 93.

On the other hand, the sum $y(i, j) = \sum_{m=i+1}^{j} (d_1(u_m) - 1)$ can be written as

$$y(i, j) = \left( \sum_{u \in V(T_1)} d_1(u) - 1 \right) + \cdots + \left( \sum_{u \in V(T_n)} d_1(u) - 1 \right) + d_1(u_j) - 1 \\ = -n + d_1(u_j) - 1 \ge 0.$$

The above steps follow from the first part of Lemma 93, and by the assumption that $u_j$ has at least $n+1$ children, namely $u_i, u_{i_1}, \cdots, u_{i_n}$. Thus, $R_x(i) = j$, completing the proof. $\square$

The following proposition shows that the backward map $\Phi_R$ satisfies the first condition of the FB lemma (Lemma 61).

**Proposition 96.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be as in Def. 22 and satisfies $\mathbb{E}[X_0] = 0$. Let $x = (x_n)_{n \in \mathbb{Z}}$ be a realization of $X$, and $[\mathbb{Z}, 0, x]$ be its associated network. Then, $\Phi_R \circ \Psi_R([\mathbb{Z}, 0, x]) = [\mathbb{Z}, 0, x]$.

*Proof.* Let $(u_n)_{n \in \mathbb{Z}} = U(\Psi_R([\mathbb{Z}, 0, x]))$ be the succession line of $\Psi_R([\mathbb{Z}, 0, x])$. By Remark 90, $u_n = n$ for all $n \in \mathbb{Z}$. Let $[\mathbb{Z}, 0, y] := \Phi_R \circ \Psi_R([\mathbb{Z}, 0, x])$, where $y = (y_n)_{n \in \mathbb{Z}}$ with $y_n := d_1(u_{n+1}) - 1 = d_1(n+1) - 1$ for all $n \in \mathbb{Z}$. From the first statement of Lemma 34, $x_n = d_1(n+1) - 1$, for all $n \in \mathbb{Z}$. Therefore, $x_n = y_n$ for all $n \in \mathbb{Z}$. $\square$

We now show that the map $\Phi_R$ is continuous on the set of ordered family trees that have at most one bi-infinite F-path.

**Lemma 97.** Let $[T, o]$ be an ordered EFT that has at most one bi-infinite F-path, and such that the bi-infinite path passes through o. If $([T_n, o_n])_{n \ge 1}$ is any sequence of rooted Family Trees such that $[T_n, o_n] \to [T, o]$ as $n \to \infty$, then $\Phi_R([T_n, o_n]) \to \Phi_R([T, o])$ as $n \to \infty$ (both convergences are in local sense).
Proof. For $r > 0$, denote $x_r((T,o)) = (x_{-r}, x_{-r+1}, \dots, x_0, \dots, x_{r-1}, x_r)$. We need to show that given $r > 0$, there exists $N_0$ such that for all $n > N_0$, $x_r((T_n, o_n)) = x_r((T, o))$. Since $(T_n, o_n) \to (T, o)$, it is enough to show that, given $r > 0$, there exists $R > 0$ such that $x_r((T, o)_R) = x_r(T, o)$, where $(T, o)_R$ is the restriction of $T$ to the graph ball of radius $R$ centered at $o$.

Let $(o_{-r-1}, o_{-r}, \dots, o, o_1, \dots, o_{r+1})$ be the $r+1$ restriction of the $F$-bi-infinite path of $(T, o)$ passing through $o$. If such a path does not exist (take for instance, a sample of the non-trivial unimodular EGWT), then we can find the largest $k < 0$ such that $o_l = o_k$ for all $-r-1 \le l \le k$.

Let $h_i$ be the largest graph distance from $o_i$ to the descendants of $o_i$ which are not the descendants of $o_{i-1}$ for $-r-1 \le i \le r+1$. Then, $h_i$ is finite for all $i$ since the descendants of $o_i$ that are not the descendants of $o_{i-1}$ are finite for all $i$ (otherwise this contradicts the fact that $T$ has at most one bi-infinite $F$-path). Take $R = \max\{h_i : -r-1 \le i \le r+1\}$. Then, we have $U((T, o)_R) = U((T, o))$. Thus, $x_r((T, o)_R) = x_r((T, o))$. $\square$

## 5.3 The extended backward map of record vertex-shift

In this section, we define a map $\hat{\Phi}_R$ on the space of marked Family Trees and show that it satisfies all the conditions of FB Lemma 61. The map $\hat{\Phi}_R$ will be used later to show that the $R$-probability of $[\mathbb{Z}, 0, X]$ exists. We call the map $\hat{\Phi}_R$ the extended backward map.

Let $T'_*$ (resp. $\hat{T}'_*$) be the space of rooted ordered Family Trees (resp. space of rooted marked ordered Family Trees whose marks take values in $\mathbb{Z}$) that have at most one bi-infinite $F$-path.

We have defined earlier in Eq. (5.1.1) the succession line of a rooted ordered Family Tree $[T, o]$ that has at most one bi-infinite $F$-path, and using this we defined in Eq. (5.1.2) the backward map $\Phi_R : T'_* \to \mathcal{G}_*$.

In order to use the FB lemma (Lemma 61), we need this backward map to satisfy

$$ \Phi_R \circ \Psi_R = I \mathcal{P}\text{-a.s.,} \qquad (5.3.1) $$

where $\mathcal{P}$ is the distribution of $[\mathbb{Z}, 0, X]$, where $X = (X_n)_{n \in \mathbb{Z}}$ satisfies $\mathbb{E}[X_0] \ge 0$.
When $\mathbb{E}[X_0] > 0$, the random walk $(S_{-n})_{n \ge 0}$ starting at 0 drifts to $-\infty$ (where $S_{-n} = \sum_{k=-n}^{-1} -X_k$ for all $n > 0$ and $S_0 = 0$). In this case, $\Phi_R$ does not satisfy Eq. (5.3.1) since $\Psi_R$ fails to be injective. For instance, consider the set $A = \{[\mathbb{Z}, 0, x] = (x_n)_{n \in \mathbb{Z}} : x_{-1} = 3 \text{ and } s_{-n} \to -\infty \text{ as } n \to \infty\}$. The set $A$ has positive measure since we assumed that $\mathbb{E}[X_0] > 0$. For each $[\mathbb{Z}, 0, x] \in A$, define a new element $[\mathbb{Z}, 0, \tilde{x}]$, where the sequence $\tilde{x} = (\tilde{x}_n)_{n \in \mathbb{Z}}$ is given by the following: $\tilde{x}_n = x_n$ for all $n \ne -1$ and $\tilde{x}_{-1} = 4$. In comparison to the sums $(s_n)_{n \in \mathbb{Z}}$ associated to $x$, the sums $(\tilde{s}_n)_{n \in \mathbb{Z}}$ associated to the sequence $\tilde{x}$ are shifted by $-1$ for all $n \le -1$. Both the networks $[\mathbb{Z}, 0, x]$ and $[\mathbb{Z}, 0, \tilde{x}]$ have the same record graphs. So, $\Psi_R$ is not injective with positive probability, see Figure 5.1.

<figure><img src="image_27.png" /><figcaption>Figure 5.1: Example showing that when $\mathbb{E}[X_0] > 0$, two samples of $[\mathbb{Z}, 0, X]$ can have the same record graph.</figcaption></figure>

To obtain the injectivity, we enrich the record graph $[\mathbb{Z}, 0, X]$ with the type function of $X$ as a mark function on the vertices of the record graph. This gives the forward map $\hat{\Psi}_R : \mathcal{G}_* \to \hat{T}'_*$ given by $\hat{\Psi}_R([\mathbb{Z}, 0, x]) = [T, 0, t]$, where $[T, 0] = \Psi_R([\mathbb{Z}, 0, x])$ is the component of 0 in the record graph of $[\mathbb{Z}, 0, x]$, $t$ is the type function associated to $x$, and $x = (x_n)_{n \in \mathbb{Z}}$ is a sample of the i.i.d. sequence $X = (X_n)_{n \in \mathbb{Z}}$ when $0 < \mathbb{E}[X_0] < \infty$. We define a backward map $\hat{\Phi}_R$ (associated to $X$) on $\hat{T}'_*$ such that it satisfies Eq. (5.3.1) with $\hat{\Psi}_R$ as the forward map.
**Definition 98.** Let $[T, o, M]$ be a rooted marked Family Tree that has at most one bi-infinite F-path and $M: V(T) \to \mathbb{Z}$ be a marked function such that $M(u) \ge -1$ for all $u \in V(T)$. Let $u((T, o, M)) = (u_n)_{n \in \mathbb{Z}}$ be its succession line with $u_0 = o$. Define

$$ \hat{\Phi}_R([T, o, M]) = [\mathbb{Z}, 0, x], \qquad (5.3.2) $$

where $x = (x_n)_{n \in \mathbb{Z}}$ is given by $x_n = (d_1(u_{n+1}) - 1)\mathbf{1}\{u_{n+1} \notin \mathcal{V}\} + (d_1(u_{n+1}) + M(u_{n+1}) - 1)\mathbf{1}\{u_{n+1} \in \mathcal{V}\}$ for all $n \in \mathbb{Z}$.

The map $\hat{\Phi}_R$ is defined keeping in mind the relation between increment, offspring count and type as given in Lemma 38.

## 5.4 Bijectivity and continuity of the extended backward map

Let $\hat{\Psi}_R : \mathcal{G}_* \to \hat{T}'_*$ be the forward map given by $\hat{\Psi}_R([\mathbb{Z}, 0, x]) = [T, 0, t]$, where $[T, 0] = \Psi_R([\mathbb{Z}, 0, x])$ is the component of 0 in the record graph of $[\mathbb{Z}, 0, x]$, $t$ is the type function associated to $x$ (see subsection 3.1 for the definition of the type function), and $x = (x_n)_{n \in \mathbb{Z}}$ is a sample of the i.i.d. sequence $X = (X_n)_{n \in \mathbb{Z}}$ when $0 < \mathbb{E}[X_0] < \infty$.

**Proposition 99.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be an i.i.d. sequence as in Def. 22 with $0 < \mathbb{E}[X_0] < \infty$, and $\mathcal{P}$ be the distribution of $[\mathbb{Z}, 0, X]$ on $\mathcal{G}_*$. Then, $\hat{\Phi}_R \circ \hat{\Psi}_R = I \mathcal{P} - a.s.$

*Proof.* Let $x = (x_n)_{n \in \mathbb{Z}}$ be a sample of $X$, $[\mathbb{Z}, 0, x]$ be its network, and let $[T, 0, t] = \hat{\Psi}_R([\mathbb{Z}, 0, x])$ be the marked random rooted tree, where the mark function is given by the type function $t$ associated to $x$. We know that $[T, 0, t]$ has at most one bi-infinite path and $T$ is eternal. So, we obtain its succession $u([T, 0, t]) = (u_n)_{n \in \mathbb{Z}}$. Note that $u_n = n$ for all $n \in \mathbb{Z}$ by Remark 90. Let $[\mathbb{Z}, 0, y] = \hat{\Phi}_R([T, 0, t])$, where $y = (y_n)_{n \in \mathbb{Z}}$ is the sequence given by $y_n = (d_1(u_{n+1}) - 1)\mathbf{1}\{u_{n+1} \notin \mathcal{V}\} + (d_1(u_{n+1}) + t_x(u_{n+1}) - 1)\mathbf{1}\{u_{n+1} \in \mathcal{V}\}$ for all $n \in \mathbb{Z}$. By Lemma 38 and the fact that for any $n \in \mathbb{Z}$, $u_n \in \mathcal{V}$ if and only if $t(u_n) > -1$, it follows that $x_n = (d_1(n+1) - 1)\mathbf{1}\{t_x(n+1) = -1\} + (d_1(n+1) + t(n+1) - 1)\mathbf{1}\{t(n+1) \ge 0\} = y_n$ for all $n \in \mathbb{Z}$. Thus, $[\mathbb{Z}, 0, x] = [\mathbb{Z}, 0, y]$. $\square$
**Lemma 100.** Let $[T, o, m] \in \hat{T}_*'. If a sequence $([T_n, o_n, m_n])_{n \ge 1}$ in $\hat{T}_*'$ converges to $[T, o, m]$ as $n \to \infty$, then $\hat{\Phi}_R([T_n, o_n, m_n])$ converges to $\hat{\Phi}_R([T, o, t])$ as $n \to \infty$.

*Proof.* Since the marks take values in $\mathbb{Z}$, which is a discrete set, the proof of the statement is the same as in Lemma 97, but the underlined space is $\hat{T}_*$' instead of $T_*'$.
$\square$

## 5.5 Existence of R-probability for non-negative mean

Let $X = (X_n)_{n \in \mathbb{Z}}$ be the i.i.d. sequence of increments of a skip-free to the left random walk and let $[\mathbb{Z}, 0, X]$ be its associated network. Let $\pi$ be the distribution of $X_0 + 1$.

**Theorem 101.** If $\mathbb{E}[X_0] = 0$, then the R-probability of $[\mathbb{Z}, 0, X]$ exists. Its distribution is equal to the push-forward of $\mathrm{EKT}(\pi)$ under the map $\Phi_R$, where $\pi$ is the probability distribution of $X_0 + 1$.

*Proof.* Let $\mathcal{P}$ be the distribution of $[\mathbb{Z}, 0, X]$, and $\mathcal{Q} := \mathcal{P} \circ \Psi_R^{-1}$. We show that $\mathcal{P}$ and $\Phi_R$ satisfy all the hypotheses of FB Lemma 61. Theorem 53 shows that $\mathcal{Q} = \mathrm{EGWT}(\pi)$, where the offspring distribution $\pi \stackrel{D}{=} X_0 + 1$. Proposition 96 implies the first condition of Lemma 61. In Lemma 80, we showed that the F-probability $Q_F$ of $\mathrm{EGWT}(\pi)$ exists and it is equal to $\mathrm{EKT}(\pi)$, satisfying the second condition of Lemma 61. The third condition of Lemma 61 is shown to be satisfied by $\Phi_R$ in Lemma 97. Thus, the R-probability of $[\mathbb{Z}, 0, X]$ exists, and its distribution is $Q_F \circ \Phi_R^{-1}$.
$\square$

Assume $0 < \mathbb{E}[X_0] < \infty$. Let $\bar{\pi}$ and $\tilde{\pi}$ be the probability distributions defined in Eq. (3.2.8). Consider the bi-variate ECS ordered marked Eternal Kesten Tree $\mathrm{MEKT}(\bar{\pi}, \tilde{\pi})$ whose marked bush has the distribution given in Theorem 55.

**Theorem 102.** If $0 < \mathbb{E}[X_0] < \infty$, then the R-probability of $[\mathbb{Z}, 0, X]$ exists, and its distribution is $\mathrm{MEKT}(\bar{\pi}, \tilde{\pi}) \circ \hat{\Phi}_R^{-1}$, the push-forward measure of $\mathrm{MEKT}(\bar{\pi}, \tilde{\pi})$ under the extended backward map $\hat{\Phi}_R$.
5.6. CONSTRUCTION OF THE R-PROBABILITY FOR ZERO MEAN

Proof. Let $[\mathbf{T}, 0, t] = \hat{\Psi}_R([\mathbb{Z}, 0, X])$, where $t$ is the type function associated to $X$, and $\mathcal{P}$ be the distribution of $[\mathbb{Z}, 0, X]$. We apply FB Lemma 61. By Proposition 99, the extended map $\hat{\Phi}_R \circ \hat{\Psi}_R = \text{Id} \mathcal{P}$ - a.s.. By Theorem 55, $[\mathbf{T}, 0, t]$ is the unimodularised MEKT($\bar{\pi}, \tilde{\pi}$) (in the sense of Eq. (2.3.3)). By Proposition 82, MEKT($\bar{\pi}, \tilde{\pi}$) is the $F$-probability of the unimodularised MEKT($\bar{\pi}, \tilde{\pi}$). By Lemma 100, the extended backward map $\hat{\Phi}_R$ is continuous.

So, all the three conditions of the FB lemma (Lemma 61) are satisfied by
the extended backward map $\hat{\Phi}_R$ and the probability measure $\mathcal{P}$. Thus, $R$-
probability $[\mathbb{Z}, 0, X]$ exists, and its distribution is equal to $\text{MEKT}(\bar{\pi}, \tilde{\pi}) \circ$
$\hat{\Phi}_R^{-1}$.
□

Remark 103. When $0 < \mathbb{E}[X_0] < \infty$, MEKT($\bar{\pi}, \tilde{\pi}$) is the distribution of the record graph of the conditioned network $[\mathbb{Z}, 0, X]$ conditioned on $\{S_n \le 0, \forall n \le 0\}$ which is equivalent to $\{0 \in \nabla\}$ (i.e., 0 belongs to the bi-infinite path of the record graph) by Theorem 55. This implies that the $R$-probability of $[\mathbb{Z}, 0, X]$ is the conditioned network $[\mathbb{Z}, 0, X]$ conditioned on $\{S_n \le 0, \forall n \le 0\}$.

5.6 Construction of the R-probability for
zero mean

We have seen in the previous sections that the *R*-probability of $[\mathbb{Z}, 0, X]$ exists when $\mathbb{E}[X_0] = 0$. We now provide two constructions for the *R*-probability and prove in Proposition 104 that the constructions indeed generate the *R*-probability when $\mathbb{E}[X_0] = 0$. The second construction is useful to prove several properties of the *R*-probability, see Section 5.7.

**Construction 1:** We now construct a sequence of random variables $Y = (Y_n)_{n \in \mathbb{Z}}$ and show, in Proposition 104, that its associated network $[\mathbb{Z}, 0, Y]$ is the $R$-probability of $[\mathbb{Z}, 0, X]$ when $\mathbb{E}[X_0] = 0$. In particular, we show that $[\mathbb{Z}, 0, Y] = \Phi_R([\mathbf{T}, \mathbf{o}])$, where $[\mathbf{T}, \mathbf{o}]$ is distributed as $EKT(\pi)$ with $\pi$ being the distribution of $X_0 + 1$.

Define the non-negatively indexed subsequence $(Y_n)_{n \ge 0}$ to be i.i.d. ran-
dom variables with $Y_n \stackrel{D}{=} X_n$, $n \ge 0$. The construction for the negatively
indexed subsequence $(Y_n)_{n<0}$ is given in the following steps. Recall that the
size-biased distribution $\hat{\pi}$ of $\pi$ is given by $\hat{\pi}(k) = k\pi(k)$, $k \in \{0, 1, 2, \dots\}$. In
particular, $\hat{\pi}(\{1, 2, 3, \dots\}) = 1$.
Let $\lambda$ be the distribution of $X_0$.

1. Let $l = -1$.

2. Generate a random variable $Z$ with distribution $\hat{\pi}$ and assign $Y_l := (Z-1)$.

3. Let $K$ be an integer chosen uniformly among $\{0, 1, \dots, Y_l\}$.

4. Generate an i.i.d. sequence of random variables $(Z_n)_{n<0}$ with distribution $\lambda$.

5. Let $\tau = \sup\{n < 0 : -Y_l - \sum_{m=n}^{-1} Z_m = -K\}$. Assign $Y_{n+l} := Z_n$ for $\tau \le n < 0$.

6. Assign $l := l + \tau - 1$.

7. Repeat the procedure from step 2.

Let $\tau_n, l_n$ denote $\tau$ and $l$ of the $n$-th ($n \ge 1$) iteration in the above construction, with the notation that $\tau_0 = 0, l_0 = 0$. Then, for all $n \ge 2$, the following equality of joint distribution holds because of the iterative nature of the construction:

$$ (Y_{\tau_n+l_n}, Y_{\tau_n+l_n+1}, \dots, Y_{\tau_{n-1}+l_{n-1}-1}) \stackrel{D}{=} (Y_{\tau_{n-1}+l_{n-1}}, Y_{\tau_{n-1}+l_{n-1}+1}, \dots, Y_{\tau_{n-2}+l_{n-2}-1}). \quad (5.6.1) $$

**Proposition 104.** Let $[\mathbb{Z}, 0, Y]$ be the network associated to the sequence of random variables $Y = (Y_n)_{n \in \mathbb{Z}}$ obtained from Construction 1. Then $[\mathbb{Z}, 0, Y]$ is the R-probability of $[\mathbb{Z}, 0, X]$, where $X = (X_n)_{n \in \mathbb{Z}}$ is as in Def. 22 with $\mathbb{E}[X_0] = 0$.

*Proof.* Let $\pi$ be the distribution of $X_0 + 1$, $[\mathbf{T}, \mathbf{o}]$ and $[\mathbf{T}', \mathbf{o}']$ be random rooted trees with distributions $EKT(\pi)$ (see Fig. 5.2) and $EGWT(\pi)$ (see Fig. 5.3) respectively. We show that $[\mathbb{Z}, 0, Y] = \Phi_R([\mathbf{T}, \mathbf{o}])$. Let $(u_n)_{n \in \mathbb{Z}}$ and $(w_n)_{n \in \mathbb{Z}}$ be the succession lines of $[\mathbf{T}, \mathbf{o}]$ and $[\mathbf{T}', \mathbf{o}']$ respectively, with $u_0 = \mathbf{o}$ and $w_0 = \mathbf{o}'$. It follows from the constructions of $EGWT(\pi)$ and $EKT(\pi)$ that the distribution of the sequence of offspring counts of $(u_n)_{n \ge 1}$ is the same as that of $(w_n)_{n \ge 1}$. Since the map $\Phi_R$ is bijective $EGWT(\pi)$-a.s., by Proposition 96 we have $(d_1(w_n) - 1)_{n \ge 1} \stackrel{D}{=} (X_{n-1})_{n \ge 1}$. Therefore, $(d_1(u_n) - 1)_{n \ge 1} \stackrel{D}{=} (d_1(w_n) - 1)_{n \ge 1} \stackrel{D}{=} (X_{n-1})_{n \ge 1} \stackrel{D}{=} (Y_{n-1})_{n \ge 1}$.
5.6. CONSTRUCTION OF THE R-PROBABILITY FOR ZERO MEAN

<figure><img src="image_28.png" /><figcaption>Figure 5.2: Distribution of *EKT*(*π*) and its succession line starting from the root **o** (drawn in blue).</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>Figure 5.3: Distribution of *EGWT*(*π*) and its succession line starting from the root **o** (drawn in blue).</figcaption></figure>
<figure><img src="image_30.png" /><figcaption>Figure 5.4: Sample trajectory of the sums of the R-probability sequence when $\mathbb{E}[X_0] = 0$ (the R-probability sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ is the sequence of increments of this trajectory).</figcaption></figure>

We now show that $(Y_{-n})_{n \ge 1} \stackrel{\mathcal{D}}{=} (d_1(u_{-n+1}) - 1)_{n \ge 1}$. Consider the random variable $\tau$ defined in the first iteration of Construction 1. Let $N$ be a positive random variable such that $u_{-N}$ is the unique child of $\mathbf{o}$ that belongs to the bi-infinite path of $\mathbf{T}$, i.e., $u_{-N} = \mathbf{o}_{-1}$. By the construction of $\text{EKT}(\pi)$, $(d_1(u_{-N-n}))_{n \ge 0} \stackrel{\mathcal{D}}{=} (d_1(u_{-n}))_{n \ge 0}$. Therefore, by Eq. (5.6.1), it is enough to show that

$$ \tau \stackrel{\mathcal{D}}{=} -N + 1 \qquad (5.6.2) $$

and the equality of the following conditioned distributions

$$ (Y_{-n}, Y_{-n+1}, \dots, Y_{-1})|_{\tau=-n+1} \stackrel{\mathcal{D}}{=} (d_1(u_{-n+1}) - 1, d_1(u_{-n+2}) - 1, \dots, d_1(u_0) - 1)|_{N=n}. \qquad (5.6.3) $$

By the construction of $\text{EKT}(\pi)$ and Construction 1, Eq. (5.6.3) follows. It remains to show Eq. (5.6.2). We show it using the following inequality. For a realization $[T, o]$ of $\text{EKT}(\pi)$, and any $M$ such that $0 < M \le N-1$ ($N$ as above), let $u' := u'(M)$ denote the youngest child of $u_0$ such that $u > u'$ implies that $u \in \{u_0, u_{-1}, \dots, u_{-M}\}$. Then, we have

$$ \sum_{i=0}^{M} (d_1(u_{-i}) - 1) \ge \#\{u \in D_1(u_0) : u < u_{-N}\}, \qquad (5.6.4) $$
5.6. CONSTRUCTION OF THE R-PROBABILITY FOR ZERO MEAN

with equality if and only if $M = N - 1$. Indeed,

$$ \sum_{i=0}^{M} (d_1(u_{-i}) - 1) = d_1(u_0) - 1 + \sum_{\{u \in D_1(u_0) : u > u'\}} \sum_{v \in T_u} (d_1(v) - 1) + \sum_{\{u \in T_u' : u \ge u_{-M}\}} (d_1(u) - 1), $$

where $T_u$ in the above equation denotes the descendant tree of $u$ (with root as $u$). The above equation is obtained by rearranging the sum on the left-hand side into sums on the descendant trees of the children of $u_0$ whose descendants are contained in $\{u_0, u_{-1}, \dots, u_{-M}\}$ and the remaining part. By applying part 1 of Lemma 93 to the second sum and Remark 94 to the third sum of the above equation respectively, the right-hand side of the above equation is

$$ \ge d_1(u_0) - 1 + \sum_{\{u \in D_1(u_0) : u > u'\}} (-1) + 0. $$

Since $u' \ge u_{-N}$, the sum in the above equation is lower bounded by $\#\{u \in D_1(u_0) : u > u_{-N}\}$, so we obtain,

$$ \sum_{i=0}^{M} (d_1(u_{-i}) - 1) \ge d_1(u_0) - 1 - \#\{u \in D_1(u_0) : u > u_{-N}\} \\ = \#\{u \in D_1(u_0) : u < u_{-N}\}. $$

Equality in the above occurs if and only if $u' = u_{-N}$, i.e., $M = N - 1$.

Since the order of $o_{-1} (= u_{-N})$ is uniform among the children of $o$ in $EKT(\pi)$, and $d_1(u_0) > 0$ (because $d_1(u_0) \stackrel{D}{=} \hat{\pi}$ and $\hat{\pi}(N) = 1$), it follows that the distribution of $\#\{u \in D_1(u_0) : u < u_{-N}\}$ conditioned on $\{d_1(u_0) = \ell\}$ is the uniform distribution on $\{0, 1, 2, \dots, \ell - 1\}$. Therefore, $\#\{u \in D_1(u_0) : u < u_{-N}\} \stackrel{D}{=} K$, where $K$ is the random variable in the first iteration of Construction 1.

By the argument following Eq. (5.6.4), it follows that $M = N - 1$ is the smallest non-negative integer for which equality is attained in Eq. (5.6.4). Therefore, $\tau \stackrel{D}{=} -(N - 1)$. Thus,

$$ (Y_{-N}, Y_{-N+1}, \dots, Y_{-1}) \stackrel{D}{=} (Z_{\tau}, Z_{\tau+1}, \dots, Z_{-1}, Y_{-1}) \\ \stackrel{D}{=} (d_1(u_{-N+1}) - 1, d_1(u_{-N+2}) - 1, \dots, d_1(u_0) - 1). $$

□
**Construction 2:** In the following steps, we provide an alternative construction of the sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ (also illustrated in Figure 5.4) from the sequence $X = (X_n)_{n \in \mathbb{Z}}$, where $X$ is as in Def. 22 with $\mathbb{E}[X_0] = 0$. This construction is used in Section 5.9 to compare the foil structures of $[\mathbb{Z}, 0, X]$ and $[\mathbb{Z}, 0, Y]$ under the record vertex-shift. Let $\pi$ be the distribution of $X_0 + 1$, and $\hat{\pi}$ be the size-biased distribution of $\pi$.

1. Take $(Y_n)_{n \ge 0} \stackrel{D}{=} (X_n)_{n \ge 0}$.

2. Let $(Z_n)_{n \ge 1}$ be an i.i.d. sequence of random variables, independent of $(Y_n)_{n \ge 0}$, that take values in $\mathbb{Z}_{\ge -1}$ and whose common distribution is given by $\mathbb{P}[Z_1 = b] = \hat{\pi}(b+1)$ for all $b \ge -1$. Note that $\mathbb{P}[Z_1 = -1] = 0$.

3. Let $(K_n)_{n \ge 1}$ be an i.i.d. sequence of random variables such that $K_n$ is independent of $Z_m$ whenever $m \ne n$, and $\mathbb{P}[K_n = a | Z_n = b] = \frac{1}{b+1} \mathbf{1}_{0 \le a \le b}$, for all $(a, b) \in \mathbb{Z}_{\ge 0} \times \mathbb{Z}_{\ge 0}$ and for all $n \ge 1$.

4. Consider an array $(X_m^{(n)})_{m, n \in \mathbb{N}}$ of i.i.d. random variables, independent of all the above random variables, such that $X_1^{(1)} \stackrel{D}{=} X_1$.

5. Define a sequence of random times $(\tau_n)_{n \ge 1}$ by $\tau_n := \inf\{m \ge 1 : -Z_n - \sum_{l=1}^m X_m^{(n)} \ge -K_n\}$ for all $n \ge 1$. Note that $\tau_n < \infty$ almost surely for all $n \ge 1$ by Chung-Fuchs theorem. Since $X_1^{(1)}$ cannot be smaller than $-1$, we have $-Z_n - \sum_{l=1}^{\tau_n} X_m^{(n)} = -K_n$ for all $n \ge 1$.

Finally, consider the following independent sequence of random-sized tuples

$$ (Y_{-1}, Y_{-2}, \dots, Y_{-(\tau_1+1)}) \stackrel{D}{=} (Z_1, X_1^{(1)}, X_2^{(1)}, \dots, X_{\tau_1}^{(1)}), \\ (Y_{-(\tau_1+2)}, \dots, Y_{-(\tau_1+\tau_2+2)}) \stackrel{D}{=} (Z_2, X_1^{(2)}, \dots, X_{\tau_2}^{(2)}), \dots, \\ (Y_{-(\tau_1+\dots+\tau_{n-1}+n)} + \dots + Y_{-(\tau_1+\dots+\tau_{n-1}+\tau_n+n)}) \stackrel{D}{=} (Z_n, X_1^n, \dots, X_{\tau_n}^{(n)}), \dots $$

We call the sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ the **R-probability sequence** associated to $X = (X_n)_{n \in \mathbb{Z}}$.

*Remark 105.* Note that $K_1$ is a proper random variable since $\mathbb{P}[K_1 = a] = \sum_{l=a+1}^{\infty} \pi(l)$ for all non-negative integers $a \ge 0$ and $\mathbb{P}[K_n < \infty] = \sum_{a=0}^{\infty} \pi((a, \infty)) = m(\pi) = 1$. Observe that $\mathbb{P}[K_1 > 0] > 0$ since $\pi(0) < 1$.

From the construction, it is clear that $(K_n, \tau_n) \stackrel{D}{=} (K, \tau)$, where $K, \tau$ are the random variables defined in Construction 1.
5.7 Properties of the R-probability
sequence for zero mean

In this section, we discuss the properties of the R-probability sequence
$Y = (Y_n)_{n \in \mathbb{Z}}$ of $X = (X_n)_{n \in \mathbb{Z}}$, defined in the last section, when $\mathbb{E}[X_0] = 0$.
Recall that $(Y_n)_{n \ge 0}$ is an i.i.d. sequence whose common distribution is given
by $Y_0 \stackrel{\mathcal{D}}{=} X_0$. So, we focus on the properties of $(Y_n)_{n<0}$.

For two integers $m < n$, let $w(m,n) := \sum_{k=m}^{n-1} Y_k$ and $W_n = -w(-n,0) = -\sum_{k=-n}^{-1} Y_k$, for $n \ge 1$. We continue to use the notations of the last section in the following lemma and proposition. From the definitions of $\tau_n$ and $K_n$, it follows that $W_{\tau_1+\tau_2+\cdots+\tau_n+n} = -(K_1 + K_2 + \cdots + K_n)$ for all $n \ge 1$.

**Lemma 106.** *Almost surely* $W_m < -(K_1 + \cdots + K_n + K_{n+1})$ *for all positive integers* $m, n$ *such that* $n \ge 1$ *and* $\tau_1 + \tau_2 + \cdots + \tau_n + n < m < \tau_1 + \tau_2 + \cdots + \tau_{n+1} + n + 1$, *where* $(\tau_i)_{i \ge 1}$ *are as in Construction 2*.

*Proof.* The proof is by induction on $n$. For $n=1$ and $\tau_1+1 < m < \tau_1+\tau_2+2$, we have

$$
W_m = W_{\tau_1+1} - w(-m, -(\tau_1+1)) = -K_1 - w(-m, -(\tau_1+1)).
$$

But, by the definition of $\tau_2$,

$$
-w(-m, -(\tau_1+1)) = -Y_{-(\tau_1+2)} - w(-m, -(\tau_1+2)) \stackrel{\mathcal{D}}{=} -Z_2 - \sum_{l=1}^{m-(\tau_1+2)} X_l^{(2)} < -K_2.
$$

Therefore, $W_m < -K_1 - K_2$ for $n = 1$.

Assume that the statement is true for $n-1$. For $\tau_1 + \cdots + \tau_n + n < m < \tau_1 + \tau_2 + \cdots + \tau_{n+1} + n + 1$, we have

$$
\begin{align*}
W_m &= W_{\tau_1 + \dots + \tau_n + n} - w(-m, -(\tau_1 + \dots + \tau_n + n)) \\
&\stackrel{\mathcal{D}}{=} W_{\tau_1 + \dots + \tau_n + n} - Z_{n+1} - \sum_{l=1}^{m-(\tau_1 + \dots + \tau_n + n+1)} X_l^{(n+1)} \\
&< -(K_1 + \dots + K_n + K_{n+1}).
\end{align*}
$$

Last step follows by induction, and by the definition of $\tau_{n+1}$.

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

**Proposition 107.** *Almost surely* $W_n \to -\infty$ as $n \to \infty$.
*Proof.* From Lemma 106, and the fact that $K_n \ge 0, \forall n \ge 1$, it follows that $W_m < -(K_1+K_2+\cdots+K_n)$, for all $n \ge 1$ and $m > \tau_1+\cdots+\tau_n+n$. Therefore, the event $\{W_m \xrightarrow{m \to \infty} -\infty\}$ contains the event $\{-(K_1+\cdots+K_n) \xrightarrow{n \to \infty} -\infty\}$. So, it is enough to show that $\mathbb{P}[-(K_1+K_2+\cdots+K_n) \xrightarrow{n \to \infty} -\infty] = 1$. Since $K_n$ is non-negative for all $n \ge 1$, it is enough to show that $\mathbb{P}[K_n > 0 \text{ infinitely often}] = 1$. The events $\{K_n > 0\}$ satisfy $\sum_{n=1}^{\infty} \mathbb{P}[K_n > 0] = \infty$ since, $\mathbb{P}[K_1 > 0] > 0$ and $(K_n)_{n \ge 1}$ are i.i.d. random variables. Therefore, $\mathbb{P}[K_n > 0 \text{ i.o.}] = 1$ by the Borel-Cantelli Lemma. $\square$

The following corollary is used to describe the record foils of the R-probability (see Proposition 112).

**Corollary 108.** For any integer $j$, almost surely

$$-w(j-n, j) = - \sum_{k=j-n}^{j-1} Y_k \xrightarrow{n \to \infty} -\infty.$$

*Proof.* For $n > \max\{0, j\}$,

$$-w(j-n, j) = \begin{cases} W_n - w(0, j) & \text{if } j > 0 \\ W_n + w(j, 0) & \text{otherwise.} \end{cases}$$

Therefore, by Proposition 107, a.s. $-w(j-n, j) \to -\infty$ as $n \to \infty$. $\square$

## 5.8 Construction of R-probability for positive mean

In the following steps, we construct a sequence $\tilde{Y} = (\tilde{Y}_n)_{n \in \mathbb{Z}}$ and later show that $[\mathbb{Z}, 0, \tilde{Y}]$ is the R-probability of $[\mathbb{Z}, 0, X]$ when $0 < \mathbb{E}[X_0] < \infty$. Recall the definitions of $\tilde{\pi}, \tilde{\pi}$ and $c$ from Eq. (3.2.8) in Section 3.2.

1. The random variables $(\tilde{Y}_n)_{n \ge 0}$ are i.i.d. with the common distribution the same as that of $X_0$. That is, $\tilde{Y}_n \stackrel{D}{=} X_0$ for all $n \ge 0$.

2. Let $((K_n, Z_n))_{n \ge 1}$ be an i.i.d. sequence of random variables taking values in $\mathbb{Z}_{\ge 0} \times \mathbb{Z}_{\ge 0}$ whose common joint-distribution is given by $\mathbb{P}[K_1 = m, Z_1 = l] = \mathbb{P}[X_0 = m + l]c^l$ for all $m \ge 0, l \ge 0$.
5.8. CONSTRUCTION OF R-PROBABILITY FOR POSITIVE MEAN 3

3. Define an array $(X_m^{(n)})_{m,n \in \mathbb{N}}$ of i.i.d. sequence of random variables whose common distribution is given by $\mathbb{P}[X_1^{(1)} = k] = \tilde{\pi}(k+1)$ for all $k \ge 0$.

4. Define the sequence of random times $(\tau_n)_{n \ge 1}$ by $\tau_n = \inf\{m \ge 1 : -Z_n - K_n - \sum_{l=1}^m X_m^{(n)} = -K_n\} = \inf\{m \ge 1 : -Z_n - \sum_{l=1}^m X_m^{(n)} = 0\}$ if the infimum is attained and $\tau_n = \infty$ otherwise, for all $n \ge 1$. Note that $\tau_1 < \infty$ a.s. since the random walk $(\tilde{S}_m)_{m \ge 0}$ starting at 0 drifts to $\infty$ by Lemma 32, where $\tilde{S}_m = - \sum_{l=1}^m X_m^{(1)}$ for all $m \ge 1$.

5. Define $(\tilde{Y}_{-n})_{n \ge 0}$ by
$$ (\tilde{Y}_{-1}, \tilde{Y}_{-2}, \dots, \tilde{Y}_{-(\tau_1+1)}) = (Z_1 + K_1, X_1^{(1)}, X_2^{(1)}, \dots, X_{\tau_1}^{(1)}), \\ (\tilde{Y}_{-(\tau_1+2)}, \tilde{Y}_{-(\tau_1+3)}, \dots, \tilde{Y}_{-(\tau_1+\tau_2+2)}) = (Z_2 + K_2, X_1^{(2)}, X_2^{(2)}, \dots, X_{\tau_2}^{(2)}), \dots, \\ (\tilde{Y}_{-(\tau_1+\dots+\tau_{n-1}+n)}, \dots, \tilde{Y}_{-(\tau_1+\dots+\tau_n+n)}) = (Z_n + K_n, X_1^{(n)}, X_2^{(n)}, \dots). $$

Note that the R-probability of $[\mathbb{Z}, 0, X]$ exists by Theorem 102. We now prove that the sequence constructed above is the R-probability of $[\mathbb{Z}, 0, X]$ when $0 < \mathbb{E}[X_0] < \infty$. The proof of this statement together with Remark 103 implies that $[\mathbb{Z}, 0, \tilde{Y}]$ has the same distribution as that of the conditioned network $[\mathbb{Z}, 0, X]$ conditioned on the event that $\{S_n \le 0 \ \forall n \le 0\}$, where $(S_n)_{n \in \mathbb{Z}}$ denotes the skip-free random walk associated to the increment sequence $X = (X_n)_{n \in \mathbb{Z}}$.

For any Family Tree $T$ that has a unique bi-infinite path, denote its bi-infinite path by $\mathcal{L}(T)$.

**Proposition 109.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be the i.i.d. sequence of increments of a skip-free to the left random walk that satisfies $0 < \mathbb{E}[X_0] < \infty$ and $[\mathbb{Z}, 0, X]$ be its associated network. Let $[\mathbb{Z}, 0, Y]$ be the R-probability of $[\mathbb{Z}, 0, X]$, where $Y = (Y_n)_{n \in \mathbb{Z}}$. Then, $(Y_n)_{n \ge 0}$ is an i.i.d. sequence of random variables independent of $(Y_n)_{n<0}$ and their common distribution is the same as that of $X_0$.

*Proof.* Let $[\mathbf{T}, 0, t]$ be the record graph of $[\mathbb{Z}, 0, X]$ with the type function $t$ as the mark function and $[\mathbf{T}', \mathbf{o}', t']$ be the random Family Tree obtained from $[\mathbf{T}, 0, t]$ by conditioning on the event $0 \in \mathcal{L}'$ (denoted as $[\mathbf{T}, 0, t]|0 \in \mathcal{L}'$). Note that $[\mathbf{T}', \mathbf{o}', t']$ is the F-probability of $[\mathbf{T}, 0, t]$ (see Proposition 82 and Theorem 55). By Theorem 54 and Theorem 55, the distribution of $[\mathbf{T}', \mathbf{o}', t']$
is the MEKT($\bar{\pi}$, $\tilde{\pi}$) where the marked bush of the root is distributed as in Eq. (3.2.9) and $\bar{\pi}$, $\tilde{\pi}$ are as in Eq. (3.2.8).

Let $U((\mathbf{T}', \mathbf{o}')) = (u_n)_{n \in \mathbb{Z}}$ be the succession line of $(\mathbf{T}', \mathbf{o}')$ with $u_0 = \mathbf{o}'$, and $U((\mathbf{T}, 0)) = (w_n)_{n \in \mathbb{Z}}$ be the succession line of $(\mathbf{T}, 0)$ with $w_0 = 0$.

Since $[\mathbf{T}', \mathbf{o}', t'] \stackrel{D}{=} [\mathbf{T}, 0, t]|0 \in \mathcal{L}$, we have the equality in distribution of the following two sequence of random variables:

$$ ((d_1(u_n) - 1)\mathbf{1}\{u_n \notin \mathcal{L}\} + (d_1(u_n) + t(u_n) - 1)\mathbf{1}\{u_n \in \mathcal{L}\})_{n \ge 1} \quad (5.8.1) $$

$$ ((d_1(w_n) - 1)\mathbf{1}\{w_n \notin \mathcal{L}\} + (d_1(w_n) + t(w_n) - 1)\mathbf{1}\{w_n \in \mathcal{L}\})_{n \ge 1}|0 \in \mathcal{L} $$

Since $[\mathbb{Z}, 0, Y]$ is the push-forward of the MEKT($\bar{\pi}$, $\tilde{\pi}$) (with $t$ as the mark function) under the extended backward map $\hat{\Phi}_R$, we have $(d_1(u_n) - 1)\mathbf{1}\{u_n \notin \mathcal{L}\} + (d_1(u_n) + t(u_n) - 1)\mathbf{1}\{u_n \in \mathcal{L}\} = Y_{n-1}, \forall n \in \mathbb{Z}$. From the construction of the MEKT($\bar{\pi}$, $\tilde{\pi}$) with $t$ as the mark function, the subtrees generated by $\{u_n : n \ge 1\}$ and $\{u_n : n \le 0\}$ are independent of each other. This implies that the sequence $(Y_n)_{n \ge 0}$ and $(Y_n)_{n < 0}$ are independent of each other.

Recall that the extended backward map $\hat{\Phi}_R$ is bijective, and we have $(d_1(w_n) - 1)\mathbf{1}\{w_n \notin \mathcal{L}\} + (d_1(w_n) + t(w_n) - 1)\mathbf{1}\{w_n \in \mathcal{L}\} = X_{n-1}$ for all $n \ge 1$. Observe that the event $\{0 \in \mathcal{L}\}$ is equal to $\{S_n \le 0, \forall n < 0\}$.

Since $(X_n)_{n \ge 0}$ is independent of the event $\{S_n \le 0, \forall n < 0\}$, the conditioned process $(X_n)_{n \ge 0}$ conditioned on this event has the same distribution as that of the unconditioned process $(X_n)_{n \ge 0}$. Therefore, by Eq. (5.8.1), we have

$$ (Y_n)_{n \ge 0} \stackrel{D}{=} (X_n)_{n \ge 0}|0 \in \mathcal{L} = (X_n)_{n \ge 0}|\{S_n \le 0, \forall n < 0\} \stackrel{D}{=} (X_n)_{n \ge 0}. $$

Thus,

$$ (Y_n)_{n \ge 0} \stackrel{D}{=} (X_n)_{n \ge 0}. $$

□

Consider the sequence $\tilde{Y} = (\tilde{Y}_n)_{n \in \mathbb{Z}}$ generated by the above construction of this subsection. Proposition 109 proves that the non-negatively indexed part $(\tilde{Y}_n)_{n \ge 0}$ has the same distribution as that of the non-negatively indexed part $(Y)_{n \ge 0}$, where $Y = (Y_n)_{n \in \mathbb{Z}}$ is the R-probability sequence associated to
5.8. CONSTRUCTION OF R-PROBABILITY FOR POSITIVE MEAN 5

X. In the following proposition, we show that the negatively indexed part $(\tilde{Y}_n)_{n<0}$ has the same distribution of the negatively indexed part $(Y_n)_{n<0}$. These two propositions together show that the above construction generates the R-probability sequence of X.

**Proposition 110.** Let $[\mathbb{Z}, 0, Y]$ be the R-probability of $[\mathbb{Z}, 0, X]$, where $Y = (Y_n)_{n \in \mathbb{Z}}$ where X is as in Proposition 109. Then, $(\tilde{Y}_n)_{n<0} \stackrel{D}{=} (Y_n)_{n<0}$.

*Proof.* Let $[\mathbf{T}, 0, t]$ be the record graph of $[\mathbb{Z}, 0, X]$ with the type function $t$ associated to $X$ as the mark function, and $[\mathbf{T}', \mathbf{o}', t']$ be the F-probability of $[\mathbf{T}, 0, t]$. Note that the distribution of $[\mathbf{T}', \mathbf{o}', t']$ is $\text{MEKT}(\bar{\pi}, \tilde{\pi})$ whose bush of the root is distributed as in Eq. (3.2.9) (see Proposition 82 and Theorem 55). Let $U((\mathbf{T}', \mathbf{o}', t')) = (u_n)_{n \in \mathbb{Z}}$ be the succession line of $(\mathbf{T}', \mathbf{o}', t')$ with $u_0 = \mathbf{o}'$.

Let $N > 0$ be a positive integer such that $u_{-N}$ is the smallest child of $u_0$. By the construction of $[\mathbf{T}', \mathbf{o}', t']$, $u_{-N}$ lies on the bi-infinite F-path of $\mathbf{T}'$. We know that $[\mathbf{T}', \mathbf{o}', t']$ is obtained as the joining of i.i.d. Family Trees $[\mathbf{T}_i, \mathbf{o}_i, t_i]_{i \in \mathbb{Z}}$, where $t_i$ is the restriction of $t'$ to $V(\mathbf{T}_i)$ (see Subsection 3.2). So, we have $\mathbf{o}_{-1} = u_{-N}$, $\mathbf{o}_0 = u_0$. Therefore, $u_0, u_{-N}$ lie on the bi-infinite path and none of $\{u_{-1}, \dots, u_{-N+1}\}$ lie on the bi-infinite path.

Since $[\mathbb{Z}, 0, Y] = \hat{\Phi}_R([\mathbf{T}', \mathbf{o}', t'])$ (see Theorem 102), we have

$$ (Y_n)_{n<0} = ((d_1(u_{n+1})-1)\mathbf{1}\{u_{n+1} \notin \mathcal{V}'\}+(d_1(u_{n+1})+t(u_{n+1})-1)\mathbf{1}\{u_{n+1} \in \mathcal{V}'\})_{n<0}. $$

In particular, we have $(Y_{-1}, Y_{-2}, \dots, Y_{-N}) \stackrel{D}{=} (d_1(u_0) + t(u_0) - 1, d_1(u_{-1}) - 1, \dots, d_1(u_{-N+1}) - 1)$.

Consider $\tau_1$ of the construction of this subsection. It is defined as $\tau_1 = \inf\{m \ge 1 : -Z_1 - \sum_{l=1}^m X_m^{(1)} = 0\}$, where $Z_1, X_m^{(1)}$ are as defined in the construction. In the construction, we generate the sequence $(\tilde{Y}_n)_{n<0}$ iteratively. The first iteration gives the sequence $(\tilde{Y}_{-1}, \tilde{Y}_{-2}, \tilde{Y}_{-3}, \dots, \tilde{Y}_{-(\tau_1+1)}) = (Z_1 + K_1, X_1^{(1)}, X_2^{(1)}, \dots, X_{\tau_1}^{(1)})$.

Because of the i.i.d. joining involved in the construction of $[\mathbf{T}', \mathbf{o}', t']$ and the iterative nature of the algorithm, it is sufficient to show that the joint distribution of the random variables associated to the subtree $[\mathbf{T}_0, \mathbf{o}_0, t_0]$ (i.e., $(\tilde{Y}_{-1}, \tilde{Y}_{-2}, \tilde{Y}_{-3}, \dots, \tilde{Y}_{-(\tau_1+1)})$) is the same as that of those that are generated in the first iteration of the construction. That is, it is sufficient to show that

$$ N \stackrel{D}{=} \tau_1 + 1 \qquad (5.8.2) $$
and

$$ (Z_1 + K_1, X_1^{(1)}, X_2^{(1)}, \dots, X_{n-1}^{(1)})|_{\tau_1=n-1} \stackrel{\mathcal{D}}{=} (d_1(u_0) + t(u_0) - 1, d_1(u_{-1}) - 1, \dots, d_1(u_{-n+1}) - 1)|_{N=n}. \quad (5.8.3) $$

The joint-distribution of $(K_1, Z_1)$ is chosen such that $\mathbb{P}[K_1 = m, Z_1 = l] = \mathbb{P}[X_0 = m+l]c^l = \mathbb{P}[t_0(\mathbf{o}_0) = m, d_1(\mathbf{o}_0) = l]$ (see Eq. (3.2.9)). Since $d_1(u_0) = d_1(\mathbf{o}_0) - 1$, we have $Z_1 + K_1 \stackrel{\mathcal{D}}{=} d_1(u_0) - 1 + t(u_0)$. On the event that $N = n$, $u_{-k}$ does not belong to the bi-infinite path of $\mathbf{T}'$ and they have the same offspring distribution $\tilde{\pi}$, for all $1 \le k \le n-1$. Since, $(X_i^{(1)} + 1)_{i \ge 1}$ are i.i.d. random variables with the common distribution $\tilde{\pi}$, Eq. (5.8.3) follows.

We now show Eq. (5.8.2). Consider the finite ordered Family Tree $[\mathbf{T}_0, \mathbf{o}_0]$. The vertices of $\mathbf{T}_0$ are $u_{-N+1} < \dots < u_{-1} < u_0$ listed according to the RLS order. For any $0 \le k \le N-1$, by Remark 94 and Lemma 93, we have

$$ \sum_{i=-k}^{0} (d_1(u_i) - 1) \ge 0 $$

and

$$ \sum_{i=-N+1}^{0} (d_1(u_i) - 1) = -1. $$

Rewriting the above two equations, we obtain

$$ \sum_{i=-k}^{-1} (d_1(u_i) - 1) + d_1(u_0) \ge 1 $$

and

$$ \sum_{i=-N+1}^{-1} (d_1(u_i) - 1) + d_1(u_0) = 0. $$

Note that $Z_1 \stackrel{\mathcal{D}}{=} d_1(u_0)$ (in $\mathbf{T}_0$) and $d_1(u_i) - 1 \stackrel{\mathcal{D}}{=} X_1^{(1)}$ for all $-N+1 \le i \le -1$. Thus, we obtain

$$ \sum_{i=-k}^{-1} X_{-i}^{(1)} + Z_1 \ge 1 $$

and

$$ \sum_{i=-N+1}^{-1} X_{-i}^{(1)} + Z_1 = 0. $$

In particular, $\tau_1 \stackrel{\mathcal{D}}{=} N-1$. This completes the proof.

□
5.9 R-foils of R-probability for zero mean

Let $Y = (Y_n)_{n \in \mathbb{Z}}$ be the $R$-probability sequence of $X = (X_n)_{n \in \mathbb{Z}}$, where $X$ is as in Def. 22 with $\mathbb{E}[X_0] = 0$, and $[\mathbb{Z}, 0, Y], [\mathbb{Z}, 0, X]$ be their associated networks respectively. We study the record vertex-shift on $[\mathbb{Z}, 0, Y]$ and compare it with that of $[\mathbb{Z}, 0, X]$.

*Remark 111.* Observe that the record vertex-shift $R$ is continuous $[\mathbb{Z}, 0, Y]$-a.s.. This implies that the map $\theta_R$ preserves the distribution of $[\mathbb{Z}, 0, Y]$ (see the proof of Corollary 68).

In contrast to Remark 57, we prove in this section that, almost surely, every $R$-foil of $[\mathbb{Z}, 0, Y]$ has a minimal element. This fact can be guessed by comparing the $R$-graph of $[\mathbb{Z}, 0, X]$ with the $R$-graph of $[\mathbb{Z}, 0, Y]$. Let us call the rooted tree $[T', o]$ obtained by trimming off the branches that lie above the bi-infinite $F$-path shown in Figure 5.2 as the **positive half of the Eternal Kesten Tree** (with the root same as before). As shown in Figure 5.2, it is the subtree induced on the vertices that belong to the succession line of the Eternal Kesten Tree passing through the root. Observe that the $R$-graph of $[\mathbb{Z}, 0, Y]$ is the positive half of the Eternal Kesten Tree. From the construction of $Y$, it is clear that a.s. $R_Y^n(0) > R_Y^{(n-1)}(0)$ for all $n \ge 1$. This and the fact that $-w(n, 0) \to -\infty$ (see Corollary 108) as $n \to \infty$ imply that the $R$-graph of $[\mathbb{Z}, 0, Y]$ is a.s. connected. Every generation (i.e. $F$-foils) of $T'$ has a unique vertex that belongs to the bi-infinite path. These unique vertices are the smallest elements among their respective foils.

**Proposition 112.** *Consider the $R$-foliation of $[\mathbb{Z}, 0, Y]$. For any integer $j \in \mathbb{Z}$, the $R$-foil of $j$ has a minimal element.*

*Proof.* By Corollary 108, a.s. the partial sums $-w(j-n, j) \to -\infty$ as $n \to \infty$. So, there exists a (random) unique integer $k \le j$ such that $-w(n, j) < 0$ for all $n < k$ and $w(k, j) \le 0$. Indeed, $k = \sup\{n \le j : -w(l, j) < 0 \ \forall l < n\}$. This implies that $-w(n, k) = -w(n, j) + w(k, j) < 0$ for all $n < k$. Therefore, by Lemma 24, every integer $n < k$ is a descendant of $k$. Since the $R$-graph of $[\mathbb{Z}, 0, Y]$ is connected a.s., there exist smallest integers $a, b \ge 0$ such that $R^a(k) = R^b(j)$.

If $b=0$, then every integer smaller than $j$ is a descendant of $j$ by Lemma 24 and from the discussion in the above paragraph. Hence, $j$ is the smallest element of its $R$-foil.
So, let us assume that $b \ge 1$. In this case, we show that only finitely many descendants of $k$ belong to the $R$-foil of $j$. This implies that the $R$-foil of $j$ has a smallest element because all the integers smaller than $k$ are descendants of $k$ and there are only finitely many integers between $k$ and $j$. If no descendant of $k$ belongs to the $R$-foil of $j$, then nothing to prove. Suppose that there exists an integer $l < k$ that belongs to the $R$-foil of $j$. Since $l$ is a descendant of $k$, we have $R^N(l) = R^N(j)$, for some smallest $N > a$. Further, $N = b$, since $b > 0$ is the smallest for which $R^b(j) = R^a(k)$. Therefore, $l$ is a $(b-a)$-th descendant of $k$. Thus, every descendant of $k$ that belongs to the $R$-foil of $j$ is a $(b-a)$-th descendant of $k$. But, $k$ has finitely many $(b-a)$-th descendants. Hence, finitely many descendants of $k$ belong to the $R$-foil of $j$, and this completes the proof. $\square$
# Chapter 6

## Vertex-shifts on processes with stationary increments

In this chapter, we focus on record vertex-shift on stationary sequences and representation of unimodular EFTs as record graphs of a stationary sequence. We use the following stationary framework taken from [5, 10]. The main results of this chapter are Theorem 119 and Theorem 121. Theorem 119 shows that the component of 0 in the record graph of the network associated to a stationary sequence exhibits a phase transition at mean 0 and Theorem 121 provides sufficient conditions under which a unimodular ordered EFT can be represented as the component of 0 in the record graph of the network associated to a stationary sequence.

(In French) Dans ce chapitre, nous nous intéressons au décalage de sommet des records sur les suites stationnaires et à la représentation des EFT unimodulaires comme des graphes des records de suites stationnaires. Nous utilisons le cadre stationnaire suivant, tiré de [5, 10]. Les principaux résultats de ce chapitre sont le théorème 119 et le théorème 121. Le théorème 119 montre que la composante de 0 dans le graphe des records du réseau associé à une suite stationnaire présente une transition de phase à la moyenne 0 et le théorème 121 fournit des conditions suffisantes sous lesquelles un EFT ordonné unimodulaire peut être représenté comme la composante de 0 dans le graphe des records du réseau associé à une suite stationnaire.
## 6.1 Record vertex-shift on processes with stationary and ergodic increments

In this section, we first show that if $X = (X_n)_{n \in \mathbb{Z}}$ is a stationary and ergodic sequence, then the event $\{\mathbb{Z}_X^R(0) \text{ is of class } \star\}$ is trivial (i.e., it occurs with probability either 0 or 1), where $\star \in \{\mathcal{I}/\mathcal{I}, \mathcal{I}/\mathcal{F}, \mathcal{F}/\mathcal{F}\}$ and $\mathbb{Z}_X^R(0)$ is the component of 0 in the record graph of $[\mathbb{Z}, 0, X]$. This is shown in Proposition 114 and in Corollary 115. In Theorem 119, we show that $\mathbb{Z}_X^R(0)$ exhibit a phase transition at 0 when the mean of $X_0$ is varied between $-\infty$ and $+\infty$.

**Definition 113.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be a stationary sequence, where $X_n \in \mathbb{Z}$ for all $n \in \mathbb{Z}$ and $\mathbb{E}[|X_0|] < \infty$.

Define the sequence of sums $(S_n)_{n \in \mathbb{Z}}$ by $S_0 = 0$, $S_n = \sum_{k=0}^{n-1} X_k$, for all $n > 0$, and $S_n = -\sum_{k=n+1}^{n-1} X_k$, for all $n < 0$. For any sequence $x = (x_n)_{n \in \mathbb{Z}}$ of integers, let $\mathbb{Z}_x^R$ denotes the record graph of the network $(\mathbb{Z}, x)$, and for any $i \in \mathbb{Z}$, let $\mathbb{Z}_x^R(i)$ denotes the component of $i$ in $\mathbb{Z}_x^R$. 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 network of the form $[\mathbb{Z}, 0, x]$ to $T([\mathbb{Z}, 0, x]) = [\mathbb{Z}, 0, Tx]$. For any integer $i \in \mathbb{Z}$, consider the following events:

$$ 
\begin{aligned}
E_i &:= \{[\mathbb{Z}, 0, x] : \mathbb{Z}_x^R(i) \text{ is of class } \mathcal{I}/\mathcal{I}\} \\
F_i &:= \{[\mathbb{Z}, 0, x] : \mathbb{Z}_x^R(i) \text{ is of class } \mathcal{I}/\mathcal{F}\},
\end{aligned}
$$

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}$, we have

$$ 
\begin{aligned}
T^{-1}E_i &= \{[\mathbb{Z}, 0, x] : \mathbb{Z}_{Tx}^R(i) \text{ is of class } \mathcal{I}/\mathcal{I}\} \\
&= \{[\mathbb{Z}, 0, x] : \mathbb{Z}_x^R(i+1) \text{ is of class } \mathcal{I}/\mathcal{I}\} \quad (6.1.1) \\
&= E_{i+1},
\end{aligned}
$$

where in Eq. (6.1.1), we used the fact that $[\mathbb{Z}, i, Tx] = [\mathbb{Z}, i+1, x]$. Similarly, we can show 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 25 and Remark 26), $i+1$ and $i$ are in the same connected component, i.e., $\mathbb{Z}_x^R(i) = \mathbb{Z}_x^R(i+1)$, which implies that $[\mathbb{Z}, 0, x] \in E_{i+1}$ (similarly $F_{i+1}$). Thus, we have $E_i \subseteq T^{-1}(E_i)$. Similarly, we have $F_i \subseteq T^{-1}(F_i)$. Using the fact that, 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 [10, Theorem 16.1.9]), we obtain the following proposition.

**Proposition 114.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be a stationary sequence as in Def. 113 and *ergodic*. Then,

$$ \begin{aligned} \mathbb{P}[\mathbb{Z}_X^R(0) \text{ is of class } \mathcal{I}/\mathcal{I}] &\in \{0, 1\}, \\ \mathbb{P}[\mathbb{Z}_X^R(0) \text{ is of class } \mathcal{I}/\mathcal{F}] &\in \{0, 1\}. \end{aligned} $$

**Corollary 115.** Under the assumptions of Proposition 114, the event $\{\mathbb{Z}_X^R(0) \text{ is of class } \mathcal{F}/\mathcal{F}\}$ has trivial probability measure.

*Proof.* By the Foil classification Theorem 14, $\mathbb{Z}_X^R(0)$ is either of class $\mathcal{I}/\mathcal{I}$ or $\mathcal{I}/\mathcal{F}$ or $\mathcal{F}/\mathcal{F}$. By Proposition 114, the first two events have trivial probability measure which implies that the third event has trivial probability measure. $\square$

The proof of the following lemma is similar to that of Proposition 40. The proof essentially relies on the interval property of record vertex-shift.

**Lemma 116.** Let $X$ be a stationary sequence as in Def. 113, $[\mathbb{Z}, 0, X]$ be its associated network, and $\mathbb{Z}_X^R$ be the record graph of the network $(\mathbb{Z}, X)$. If $0$ has a.s. infinitely many ancestors in $\mathbb{Z}_X^R$, then the record graph $\mathbb{Z}_X^R$ 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}_X^R$. 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.

We now show that every integer $i < 0$ belongs to the component of 0 in $\mathbb{Z}^R$. Similarly, by interchanging the role of $i$ and 0, we could show that every integer $i > 0$ belongs to the component of 0.

Let $i < 0$. Since $A$ occurs with probability 1, the sequence $(R_X^n(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 \le R_X^k(i)$ a.s.. By Lemma 25 (applied to $R_X^{k-1}(i)$) and by Remark 26, 0 is a descendant of $R_X^k(i)$ a.s.. Thus, a.s., 0 and $i$ are in the same connected component. $\square$
**Lemma 117.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be a stationary sequence of random variables as in Def. 113, $[\mathbb{Z}, 0, X]$ be its associated network and for all $n \in \mathbb{Z}$, $\mathbb{Z}_X^R(n)$ be the component of $n$ in the record graph of $(\mathbb{Z}, X)$. Then, we have

$$ \mathbb{P}[\mathbb{Z}_X^R(0) \text{ is finite}] = \mathbb{P}[\mathbb{Z}_X^R(n) \text{ is finite}, \forall n \ge 1] = \mathbb{P}[\mathbb{Z}_X^R(n) \text{ is finite}, \forall n \le -1]. \quad (6.1.2) $$

*Proof.* Let $A$ be the event given by $A = \{\mathbb{Z}_X^R(0) \text{ is finite}\}$. By Poincaré's recurrence lemma, $\mathbb{P}[A] = \mathbb{P}[\{\mathbb{Z}_{T^n X}(0) \text{ is finite for infinitely many } n \ge 1\}]$. We show that for any $\omega \in A$, if $\mathbb{Z}_{T^n X(\omega)}^R(0)$ is finite for infinitely many $n \ge 1$, then $\mathbb{Z}_{X(\omega)}^R(n)$ is finite for all $n \ge 1$. This implies the first equality in Eq. (6.1.2). The second equality of Eq. (6.1.2) follows by taking the shift $\tilde{T} = T^{-1}$ instead of $T$, and by using the equality of the events $\{\tilde{\mathbb{Z}}_{T^n X}^R(0) \text{ is finite}\} = \{\mathbb{Z}_X^R(-n) \text{ is finite}\}$ for all $n \ge 1$.

Since $X$ is stationary, the network $[\mathbb{Z}, 0, X]$ is unimodular. So, we apply the classification theorem (Theorem 14) 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.

We claim 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 \ge 0}$ attains a maximum value $a_{n_1}$ finitely many times, i.e., $S_{n'+n_1} = a_{n_1}$ for some $n' \ge 0$ and $S_{n+n_1} < a_{n_1}$ for all $n > n'$ (equivalently, from the discussion in the above paragraph, $n_1$ has finitely many ancestors). So, if $k \le n' + n_1$, then the sequence $(S_{n+k})_{n \ge 0}$ attains the maximum value $a_{n_1}$ at $N = n' + n_1 - k$ and never attains it for all $n > N$. Thus, $\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 \ge 1}$ of non-negative integers such that $n_k \to \infty$ as $k \to \infty$ and $\mathbb{Z}_{X(\omega)}^R(n_k)$ is finite for all $k \ge 1$, then $\mathbb{Z}_{X(\omega)}^R(n)$ is finite for all $n \in \mathbb{Z}$. Using this and the fact that $\mathbb{Z}_{T^n X}(0) = \mathbb{Z}_X^R(n)$ for all $n \ge 0$, we obtain that the events $\{\mathbb{Z}_{T^n X}(0) \text{ is finite for infinitely many } n \ge 1\}$ and $\{\mathbb{Z}_X^R(n) \text{ is finite for all } n \ge 1\}$ are one and the same. $\square$

*Remark 118.* By the above lemma, it follows that if $\mathbb{Z}_X^R(0)$ is finite a.s., then a.s., $\mathbb{Z}_X^R(n)$ is finite for all $n \in \mathbb{Z}$.
**Theorem 119 (Phase transition).** Let $X = (X_n)_{n \in \mathbb{Z}}$ be a stationary sequence as in Def. 113 and *ergodic*. Let $[\mathbb{Z}_X^R(0), 0]$ be the component of 0 in the record graph $\mathbb{Z}_X^R$ of the network $(\mathbb{Z}, X)$.

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

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

3. If $\mathbb{E}[X_0] = 0$, then a.s., $\mathbb{Z}_X^R$ 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., we have $S_n \to -\infty$ a.s. Therefore, the sequence $(S_n)_{n \ge 0}$ attains a maximum value $a_0$ at some (random) $n' \ge 0$ and $S_n < a_0$ for all $n > n'$. This implies that $[\mathbb{Z}_X^R(0), 0]$ is finite a.s. and hence it is of class $\mathcal{F}/\mathcal{F}$. By Remark 118, every component of $\mathbb{Z}_X^R$ 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., we have $S_n \to \infty$ a.s. and $S_{-n} \to -\infty$ a.s. Therefore, 0 has infinitely many ancestors and by the interval property of record vertex-shift, some ancestor of 0 has infinitely many descendants. Hence, $\mathbb{Z}_X^R$ has a single component (by Lemma 116) and it is of class $\mathcal{I}/\mathcal{F}$.

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

$$A := \{[\mathbb{Z}_X^R(0), 0] \text{ is of class } \mathcal{F}/\mathcal{F}\}.$$

We show that $\mathbb{P}[A] = 0$. Suppose that $\mathbb{P}[A] > 0$. Then, by Corollary 115, $\mathbb{P}[A] = 1$. Lemma 117 implies that $\mathbb{P}[\mathbb{Z}_X^R(n)$ is finite $\forall n \in \mathbb{Z}] = 1$. Note that $\mathbb{Z}_X^R(\omega)(n)$ is finite for all $n \in \mathbb{Z}$ if and only if there exists a (random) subsequence $(n'_k)_{k \in \mathbb{Z}}$ of $\mathbb{Z}$ such that $n'_k \to +\infty$, $n'_{-k} \to -\infty$ as $k \to \infty$ and for every $k \in \mathbb{Z}$, $S_n(\omega) < S_{n'_k}(\omega)$ for all $n > n'_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 \le -1 \forall n \ge 0 \right\}.$$

The covariant set $Q$ is a subset of integers such that the sums starting from these integers are always negative. Let us enumerate the integers of the set $Q$ 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 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 \le -1, \forall i \in \mathbb{Z}. \qquad (6.1.3) $$

Since $\mathbb{P}[Q$ is non-empty$] = 1$, the intensity $\mathbb{P}[0 \in Q]$ of the set $Q$ is positive (by Lemma 13). By Birkhoff's pointwise ergodic theorem, we have a.s., $\frac{S_n}{n} \to \mathbb{E}[X_0]$ as $n \to \infty$. Since $n_i \to \infty$ as $i \to \infty$, we have 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 \ge 1$, we have

$$ \frac{S_{n_i}}{n_i} = \frac{X_0 + \cdots + X_{n_0-1} + \sum_{k=0}^{i-1} (X_{n_k} + \cdots + X_{n_{k+1}-1})}{n_i} \\ \le \frac{X_0 + \cdots + X_{n_0-1} + \sum_{k=0}^{i-1} (-1)}{n_i}, \qquad (6.1.4) $$

where Eq. (6.1.4) is obtained using Eq. (6.1.3). Taking the limit $i \to \infty$ on both sides of Eq. (6.1.4), we obtain a.s.,

$$ \mathbb{E}[X_0] \le -\mathbb{P}[0 \in Q], $$

since $\frac{-i}{n_i} = -\left(\frac{\sum_{k=1}^{n_i} 1_{\{k \in Q\}} - 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 [5, Section 1.6.4]). Since, the intensity $\mathbb{P}[0 \in Q] > 0$ and $\mathbb{E}[X_0] = 0$, we obtain a contradiction. Hence, $\mathbb{P}[\mathbb{Z}^R(0), 0]$ is of class $\mathcal{F}/\mathcal{F}] = 0$. $\square$

We have already seen an instance when the component is of class $\mathcal{I}/\mathcal{I}$. When $X = (X_n)_{n \in \mathbb{Z}}$ is i.i.d. with mean 0, we showed that the record graph is of class $\mathcal{I}/\mathcal{I}$ (see Proposition 40). We now give an example of class $\mathcal{I}/\mathcal{F}$ when mean is 0.

**Example 120** (stationary, ergodic, mean 0 but the record graph is of class $\mathcal{I}/\mathcal{F}$). See Figure 6.1 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 \ge 1}$ be the number of customers in the queue observed at all changes of
state. The Markov chain $(N_n)_{n \ge 1}$ has a unique stationary distribution $\eta$ (see [4]). The Markov chain $(N_n)_{n \ge 1}$ starting with the stationary distribution $\eta$ is ergodic and $N_n = 0$ for infinitely many $n \ge 1$. Note that $N_n \ge 0$ and $N_{n+1} - N_n \in \{-1, +1\}$, for all $n \ge 1$. Consider the stationary version $(-N_n)_{n \in \mathbb{Z}}$ of $(-N_n)_{n \ge 1}$ (which can be done by extending the probability space, see [10, 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)_{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}, 0, X]$. Let $(S_n)_{n \in \mathbb{Z}}$ be the sums of $X$ given by $S_0 = 0$, $S_n = \sum_{k=0}^{n-1} X_k$ for all $n > 0$, and $S_n = \sum_{k=n}^{n-1} -X_k$ for all $n < 0$. 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 \ge 0$ for all $n \in \mathbb{Z}$ and $N_n = 0$ a.s. for infinitely many $n \ge 1$, we have $S_n \le N_0$ for all $n \in \mathbb{Z}$ and $S_n = N_0$ for infinitely many $n \ge 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 \ge 1$). Similarly, since $S_n \le 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}^R(0), 0]$ of the record graph of $[\mathbb{Z}, 0, X]$ is of class $\mathcal{I}/\mathcal{F}$.

## 6.2 Record representable Eternal Family Trees

In this section, we focus on the following question. Given a unimodular ordered EFT $[T, o]$, does there exist a stationary sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ of random variables taking values in $\{-1, 0, 1, 2, \dots\}$ such that $[T, o]$ is the component of 0 in the record graph of the network $(\mathbb{Z}, X)$? If there exists such a sequence, then we call $[T, o]$ a **record representable EFT**. In Theorem 121, we provide sufficient conditions for $[T, o]$ to be record representable. In particular, we show that every unimodular ordered EFT of class $\mathcal{I}/\mathcal{I}$ is record representable. As for the unimodular ordered EFTs of class $\mathcal{I}/\mathcal{F}$, we show that those EFTs of this class that have a unique succession line are record representable. We prove Theorem 121 in the following way: we observe that on any unimodular ordered EFT, the functions $a$ and $b$ are well-defined. The function $a$ maps a vertex to its immediate predecessor, whereas the function $b$ maps it to its immediate successor in an ordered
<figure><img src="image_32.png" /><figcaption>Figure A</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>Figure B</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>Figure C</figcaption></figure>

Figure 6.1: An Illustration of Example 120, consisting in the construction of a stationary sequence $X = (X_n)_{n \in \mathbb{Z}}$ with $E[X_0] = 0$ such that the component of 0 of the record graph of the network $[\mathbb{Z}, 0, 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 arrows and the sequence of top most arrows is the bi-infinite path.
EFT. We then proceed to show that every unimodular ordered EFT has at most two succession lines. The backward map $\Phi_R$ is bijective on the set of ordered EFTs that have a unique succession line. The stationary sequence $Y$ is the push-forward of $[T, o]$ under the backward map $\Phi_R$. The stationarity of $Y$ follows by Mecke-Thorisson point stationarity 10.

An immediate corollary of Theorem 121 is that if $X = (X_n)_{n \in \mathbb{Z}}$ is a stationary sequence of random variables taking values in $\mathbb{Z}$ such that $\mathbb{E}[|X_0|] < \infty$, $[\mathbb{Z}, 0, X]$ be its associated network, $f$ is a vertex-shift on $[\mathbb{Z}, 0, X]$ and $[\mathbb{Z}_X^f(0), 0]$ be the component of 0 in the $f$-graph of $(\mathbb{Z}, X)$ such that $[\mathbb{Z}_X^f(0), 0]$ has a unique succession line, then there exist a stationary sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ of random variables taking values in $\{-1, 0, 1, 2, \dots\}$ such that the component $[\mathbb{Z}_Y^R(0), 0]$ of 0 in the record graph of the network $(\mathbb{Z}, Y)$ has the same distribution as that of $[\mathbb{Z}_X^f(0), 0]$. In particular, if $[\mathbb{Z}_X^f(0), 0]$ is of class $\mathcal{I}/\mathcal{I}$, then such a stationary sequence $Y$ exists. The vertex-shift $f$ on $[\mathbb{Z}, 0, X]$ is said to be **record representable** if $[\mathbb{Z}_X^f(0), 0]$ is record representable.

**Theorem 121.** Let $[T, o]$ be a unimodular ordered EFT such that $T$ has a unique succession line. Then, there exists a stationary sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ of random variables taking values in $\{-1, 0, 1, 2, \dots\}$ such that
$$[T, o] \stackrel{\mathcal{D}}{=} [\mathbb{Z}_Y^R(0), 0], \text{ where } R \text{ is the record vertex-shift and } \mathbb{Z}_Y^R(0) \text{ is the component of 0 in the record graph } \mathbb{Z}_Y^R \text{ of the network } (\mathbb{Z}, Y). \text{ (In particular, if } [T, o] \text{ is of class } \mathcal{I}/\mathcal{I}, \text{ then such a stationary sequence } Y \text{ exists.)}$$

**Corollary 122.** Let $X = (X_n)_{n \in \mathbb{Z}}$ be a stationary sequence that satisfies $\mathbb{E}[|X_0|] < \infty$ and $[\mathbb{Z}, 0, X]$ be the network associated to $X$. Let $f$ be a vertex-shift on $[\mathbb{Z}, 0, X]$ such that 0 has a.s. infinitely many ancestors in the $f$-graph $\mathbb{Z}_X^f$ and the component $\mathbb{Z}_X^f(0)$ of 0 in $\mathbb{Z}_X^f$ has a unique succession line. Then, there exists a stationary sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ of random variables taking values in $\{-1, 0, 1, 2, \dots\}$ such that $[\mathbb{Z}_X^f(0), 0] \stackrel{\mathcal{D}}{=} [\mathbb{Z}_Y^R(0), 0]$, where $R$ is the record vertex-shift and $\mathbb{Z}_Y^R(0)$ is the component of 0 in the record graph $\mathbb{Z}_Y^R$ of the network $(\mathbb{Z}, Y)$.

*Proof.* Since $X$ is stationary, the network $[\mathbb{Z}_X^f(0), 0]$ is unimodular. Apply Theorem 121 to get the result. $\square$

We first recall the notation of Section 5.1 and prove a few lemmas before proving Theorem 121.
Let $[\mathbf{T}, \mathbf{o}]$ be a unimodular ordered EFT. Denote the RLS (total) order obtained on the vertices of $\mathbf{T}$ by $<$ (see Section 2.2). The set of minimal vertices of $\mathbf{T}$ is a covariant subset. It can be either empty or a singleton. Since $\mathbf{T}$ has infinitely many vertices, by No Infinite/ Finite Inclusion (Lemma 12), a.s. $\mathbf{T}$ does not have any minimal vertices. Therefore, the map $b: V(\mathbf{T}) \to V(\mathbf{T})$ given by $b(u) = \max\{v: v < u\}$ (if $\max$ exists) is a.s. well-defined. Since $b$ is injective on $V(\mathbf{T})$ and $[\mathbf{T}, \mathbf{o}]$ is unimodular, $b$ is bijective a.s. by Proposition 11. But $a(b(u)) = u$, for all $u \in V(\mathbf{T})$, where $a(v) = \min\{w: w > v\}$. Since the range of $b$ is $V(\mathbf{T})$, the map $a$ is well-defined on $V(\mathbf{T})$. Thus, we have the following lemma.

**Lemma 123.** Let $[\mathbf{T}, \mathbf{o}]$ be a unimodular ordered EFT. Then, the maps $a: V(\mathbf{T}) \to V(\mathbf{T})$, $b: V(\mathbf{T}) \to V(\mathbf{T})$ are a.s. well-defined.

Let $T$ be an ordered EFT. For any vertex $u \in V(T)$, let $U((T, u)) = (u_n)_{n \in \mathbb{Z}}$ be the succession line passing through $u$ (see Def. 87). The set $\{u_n : n \in \mathbb{Z}\}$ is called the succession line of $u$. It is easy to check that if two succession lines intersect then they are one and the same.

Let $[\mathbf{T}, \mathbf{o}]$ be a unimodular ordered EFT. Lemma 123 implies that $U((\mathbf{T}, u))$ has distinct entries for all $u \in V(\mathbf{T})$. In Lemma 124, we show that a unimodular ordered EFT $[\mathbf{T}, \mathbf{o}]$ has at most two succession lines. Note that by the classification theorem, $[\mathbf{T}, \mathbf{o}]$ is either of class $\mathcal{I}/\mathcal{I}$ or of class $\mathcal{I}/\mathcal{F}$.

**Lemma 124.** Let $[\mathbf{T}, \mathbf{o}]$ be a unimodular ordered EFT.

* If $[\mathbf{T}, \mathbf{o}]$ is of class $\mathcal{I}/\mathcal{I}$, then $\mathbf{T}$ has a unique succession line and it contains all the vertices of $\mathbf{T}$.

* If $[\mathbf{T}, \mathbf{o}]$ is of class $\mathcal{I}/\mathcal{F}$, then $\mathbf{T}$ has at most two succession lines; together they contain all the vertices of $\mathbf{T}$.

*Proof.* If $[\mathbf{T}, \mathbf{o}]$ is of class $\mathcal{I}/\mathcal{I}$, then every vertex of $\mathbf{T}$ has finitely many descendants. Let $v \in V(\mathbf{T})$. Consider the smallest common ancestor $w$ of $v$ and $\mathbf{o}$. The descendant tree of $w$ is finite and it contains both $v$ and $\mathbf{o}$. Thus, the succession lines of $v$ and $\mathbf{o}$ intersect, which implies that they are one and the same.

Let us assume that $[\mathbf{T}, \mathbf{o}]$ is of class $\mathcal{I}/\mathcal{F}$. Let $\mathcal{I}'$ denote the unique bi-infinite path of $\mathbf{T}$. Consider the set

$$W = \{u \in V(\mathbf{T}) : u < v \ \forall v \in \mathcal{I}'\}. \qquad (6.2.1)$$
Denote its complement $V(\mathbf{T})\backslash W$ by $W'$. We first show that $W'$ has a unique succession line and all the vertices of $W'$ belong to this succession line. See Figure 6.2 for an illustration.

If $u \in W'$, then there exists a vertex $v \in \mathcal{V}$ such that $u > v$ (we may safely assume it because if $u \in \mathcal{V}$ then $u$ has a child $v' \in \mathcal{V}$ and $u > v'$). The vertex $a(u) = \min\{w : w > u\}$ also satisfies $a(u) > v$ since $a(u) > u$, implying that $a(u) \in W'$. The vertex $b(u) = \max\{w : w < u\}$ satisfies $b(u) \ge v$ since $v \in \{w : w < u\}$, implying that $b(u) \in W'$. Therefore, for every vertex $u \in W'$, the succession line of $u$ is contained in $W'$. For any two vertices $u, v$ in $W'$, there are finitely many in between them, i.e., the set $\{w : u < w < v\}$ is finite (assuming that $u < v$). Therefore, the succession line of $u$ and $v$ are one and the same. Thus, $W'$ has a unique succession line and this succession line contains all the vertices of $W'$.

We now show that if $W$ is non-empty, then it has a unique succession line and all the vertices of $W$ belong to this succession line. Let $u \in W$. The vertex $a(u) = \min\{w : w > u\}$ also belongs to $W$ because $\mathcal{V} \subset \{w : w > u\}$ and $a(u) \notin \mathcal{V}$. The vertex $b(u) = \max\{w : w < u\}$ also belongs to $W$ since $b(u) < u$ and $u \in W$. Therefore, the succession line of $u$ is contained in $W$. For any two vertices $u, v$ in $W$, there are finitely many vertices between them. Thus, $W$ has a unique succession line (if $W$ is non-empty). This completes the proof. $\square$

*Remark 125.* If $[\mathbf{T}, \mathbf{o}]$ is unimodular ordered EFT of class $\mathcal{I}/\mathcal{F}$ that has a unique succession line, then it has the ECS (Every Child Succeeding) order (see Subsection 3.2 for the definition).

Consider the following subset

$$ \tilde{T}_* := \{[T, o] : T \text{ is an ordered EFT with a unique succession line}\} \quad (6.2.2) $$

of EFTs. It follows from Lemma 123 and Lemma 124 that for all $[T, o] \in \tilde{T}_*$, the succession line $U((T, o)) = (u_n)_{n \in \mathbb{Z}}$ passing through $o$ with $u_0 = o$ is a bijection from $\mathbb{Z}$ to $V(T)$ that maps $n$ to $u_n$, for all $n \in \mathbb{Z}$. Recall the backward map $\Phi_R$ defined on the set $T'_*$ of Family Trees that have at most one bi-infinite F-path. For all $[T, o] \in T'_*$, we have $\Phi_R([T, o]) = [\mathbb{Z}, 0, y]$, where $y = (y_n)_{n \in \mathbb{Z}}$ is the sequence given by $y_n = d_1(u_{n+1}) - 1$, for all $n \in \mathbb{Z}$ and $(u_n)_{n \in \mathbb{Z}} = U((T, o))$ is the succession line passing through $o$. The sequence $y = (y_n)_{n \in \mathbb{Z}}$ takes values in $\{-1, 0, 1, 2, \dots\}^{\mathbb{Z}}$. We show that $\Psi_R \circ \Phi_R = I$ on $\tilde{T}_*$, where $\Psi_R([\mathbb{Z}, 0, y]) = [\mathbb{Z}_y^R(0), 0]$ is the component of 0 in the record
<figure><img src="image_35.png" /><figcaption>Figure 6.2: An Illustration of the *I/F* case in the proof of Lemma 124. The set *W* and its complement *W'* are highlighted. Each one of these set of vertices contains a unique succession line passing through all of its vertices. The arrow direction of the succession line indicates the images under the map *b*, i.e., the immediate successor of the previous vertex. In this figure, the root *o* belongs to the succession line containing the bi-infinite path.</figcaption></figure>

graph of the network (Z, y). The proof of the following lemma is the same
as that of Proposition 95 except for a few modifications. The proof relies
on the property that every elder sibling of any vertex (if they exist) of a
Family Tree with a unique succession line has finitely many descendants.

**Lemma 126.** For all $[T, o] \in \tilde{T}_*$, $\Psi_R \circ \Phi_R([T, o]) = [T, o]$.

*Proof.* Let $(u_n)_{n \in \mathbb{Z}} = U((T,o))$ be the succession line of $(T,o)$ and $[\mathbb{Z}, 0, y] = \Phi_R([T,o])$, where $y = (y_n)_{n \in \mathbb{Z}}$.

We prove that the bijective map $\alpha : \mathbb{Z} \to V(T)$ defined by $\alpha(n) = u_n$, for all $n \in \mathbb{Z}$, induces a rooted network isomorphism $\alpha$ from $[\mathbb{Z}_y^R(0), 0] =$
$\Psi_R([\mathbb{Z},0,y])$ to $(T,o)$. Note that, if $u_j$ is a parent of $u_i$ in $T$ for some integers $i$ and $j$ then $j > i$, which follows because $(u_n)_{n \in \mathbb{Z}}$ is the succession line of $(T,o)$. In view of this, to prove that $\alpha$ induces a rooted network isomorphism, it is enough to show that for all $i \in \mathbb{Z}$, if $u_j$ is the parent of $u_i$ in $T$ for some $j > i$, then $j = R_y(i)$. It is enough to show the latter because (assuming the latter implication) if $j = R_y(i)$ and $u_k$ is a parent of $u_i$ for some $k > i$, then $R_y(i) = k$, which implies that $j = k$, and $u_k = u_j$.

Let $i \in \mathbb{Z}$ and $u_j$ be the parent of $u_i$ in $T$ for some integer $j > i$. If $j = i + 1$, then $x_i = d_1(u_{i+1}) - 1 \ge 0$, because $u_i$ is a child of $u_{i+1}$. Hence, $R_y(i) = i + 1$.

So, let us assume that $j > i + 1$. This implies that either $u_{i+1}$ is a leaf and a descendant of a sibling of $u_i$ or $u_{i+1}$ is a sibling of $u_i$. Every sibling $v$ of $u_i$ such that $v > u_i$ has finitely many descendants. This follows because if there exists a sibling $v > u_i$ of $u_i$ that has infinitely many descendants, then $u_i \in W$ (see Eq. 6.2.1). But $W$ is empty since $T$ has a unique succession line.

Let $u_{i_1} < u_{i_2} < \cdots < u_{i_n}$ be the elder siblings of $u_i$ (i.e., $u_i < u_{i_1}$), and $T_1, T_2, \cdots, T_n$ be their descendant trees respectively. For $i < k < j$, let $l(k)$ be the smallest element of the set $\{1, 2, \cdots, n\}$ such that $\{u_{i+1}, u_{i+2}, \cdots, u_k\} \subset V(T_1) \cup V(T_2) \cup \cdots V(T_{l(k)})$, and $u_{k_1}$ be the smallest vertex of $T_{l(k)}$.

Then, the sum $z(i,k) = \sum_{m=i}^{k-1} y_m = \sum_{m=i+1}^{k} (d_1(u_m) - 1)$ can be written as

$$z(i,k) = \left( \sum_{u \in V(T_1)} d_1(u) - 1 \right) + \cdots + \left( \sum_{u \in V(T_{l(k)-1})} d_1(u) - 1 \right) + \sum_{m=k_1}^{k} (d_1(u_m) - 1) < (-1) + \cdots + (-1) + \sum_{m=k_1}^{k} (d_1(u_m) - 1) < 0,$$

with the notation that $V(T_0)$ is an empty set. The last steps follow from the first and the second statements of Lemma 93.

On the other hand, the sum $z(i,j) = \sum_{m=i+1}^{j} (d_1(u_m) - 1)$ can be written as

$$z(i,j) = \left( \sum_{u \in V(T_1)} d_1(u) - 1 \right) + \cdots + \left( \sum_{u \in V(T_n)} d_1(u) - 1 \right) + d_1(u_j) - 1 \\ = -n + d_1(u_j) - 1 \ge 0.$$
The above steps follow from the first part of Lemma 93, and by the assumption that $u_j$ has at least $n+1$ children, namely $u_i, u_{i_1}, \dots, u_{i_n}$. Thus, $R_x(i) = j$, completing the proof. $\square$

*Proof of Theorem 121.* Let $[\mathbb{Z}, 0, Y] = \Phi_R([\mathbf{T}, \mathbf{o}])$. Since $\mathbf{T}$ has a unique succession line, we have a.s., $\Psi_R \circ \Phi_R([\mathbf{T}, \mathbf{o}]) = [\mathbf{T}, \mathbf{o}]$ by Lemma 126. Therefore, a.s., $[\mathbb{Z}_Y^R(0), 0] = [\mathbf{T}, \mathbf{o}]$.

We now show that the sequence $Y$ is stationary. Let $(u_n)_{n \in \mathbb{Z}} = U((\mathbf{T}, \mathbf{o}))$ be the succession line with $u_0 = \mathbf{o}$. For any $i \in \mathbb{Z}$, the map $u_n \mapsto u_{n+i}$, $\forall n \in \mathbb{Z}$ is bijective. Therefore, the map $[\mathbf{T}, \mathbf{o}] \mapsto [\mathbf{T}, u_i]$ is measure-preserving, for any $i \in \mathbb{Z}$, by Mecke-Thorisson point stationarity (Proposition10). Since, $[\mathbb{Z}, 0, T_i Y] = \Phi_R([\mathbf{T}, u_i])$, the map $(Y_n)_{n \in \mathbb{Z}} \mapsto (Y_{n+i})_{n \in \mathbb{Z}}$, for any $i \in \mathbb{Z}$, is measure-preserving. Thus, $Y$ is stationary. $\square$

## Examples of record representable vertex-shifts

**Example 127** (Strict record vertex-shift on an i.i.d. sequence (class $\mathcal{I}/\mathcal{I}$)). An illustration of this example can be seen in Figure 6.3. The strict record vertex-shift $SR$ is defined on the set of networks of the form $[\mathbb{Z}, 0, x]$, where $x = (x_n)_{n \in \mathbb{Z}}$ is a sequence of integers. It is defined by

$$SR(i) = \begin{cases} \inf\{n > i : \sum_{k=i}^{n-1} x_k > 0\} & \text{if the infimum exists,} \\ i & \text{otherwise,} \end{cases}$$

for all $i \in \mathbb{Z}$. Let $X = (X_n)_{n \in \mathbb{Z}}$ be an i.i.d. sequence of random variables taking values in $\mathbb{Z}$. One can show that the component of 0 in the $SR$-graph is of class $\mathcal{I}/\mathcal{I}$ if $\mathbb{E}[X_0] = 0$ and $\mathbb{E}[X_0^2] > 0$, because $\limsup_{n \to \infty} S_{-n} = \infty$, which implies that the descendant tree of 0 is a.s. finite. By Theorem 121, there exists a stationary sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ of random variables taking values in $\{-1, 0, 1, 2, \dots\}$ such that $[\mathbb{Z}_X^{SR}(0), 0] = [\mathbb{Z}_Y^R(0), 0]$.

**Example 128** (Climbing point vertex-shift that depends on the future (class $\mathcal{I}/\mathcal{F}$)). An illustration of this example is shown in Figure 6.4. We define a vertex-shift $C$ ($C$ for climbing point) based on an example taken from [12, Example 1(a)]. Let $X = (X_n)_{n \in \mathbb{Z}}$ be an i.i.d. sequence of random variables taking values in $\{-1, 0, 1\}$ with probabilities given by: $\mathbb{P}[X_0 = 1] = p, \mathbb{P}[X_0 = -1] = q$ and $\mathbb{P}[X_0 = 0] = 1 - p - q$, where $0 < q < p$ and $p + q < 1$. Define the vertex-shift on the networks of the form $[\mathbb{Z}, 0, x]$,
<figure><img src="image_36.png" /><figcaption>Figure 6.3: An Illustration of Example 127. The top left figure shows the trajectory of a realisation of the i.i.d. sequence $X = (X_n)_{n \in \mathbb{Z}}$, where $X_n \in \mathbb{Z}, \forall n$. The SR-graph (strict record graph) is drawn in red on the trajectory of the top left figure. The component of 0 in the SR-graph is drawn in the bottom figure. The top right figure shows the trajectory of the sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ which is obtained by applying the backward map $\Phi_R$ to the rooted tree of the bottom figure. The component of 0 in the record graph of the trajectory in the top right figure is the same as the component of 0 in the SR-graph.</figcaption></figure>
where $x = (x_n)_{n \in \mathbb{Z}}$ is a sequence with $x_n \in \{-1, 0, 1\}, \forall n$ by

$$C(i) = \begin{cases} \inf\{n > i : \sum_{k=n}^{m} x_k \ge 0, \forall m > n\} & \text{if the infimum exists,} \\ i & \text{otherwise,} \end{cases}$$

for all $i \in \mathbb{Z}$. Note that $C(i) = k$ for some $k > i$ if and only if $k$ is the smallest integer larger than $i$ such that $S_k = \min\{S_n : n > i\}$. Since $\mathbb{P}[X_0] = p-q > 0$, the random walk $(S_n)_{n \ge 0}$ drifts to $+\infty$, where $S_0 = 0, S_n = \sum_{k=0}^{n-1} X_k$. Therefore, the event $C(i) > i$ for all $i \in \mathbb{Z}$ occurs with probability 1. Since, $S_{-n} = \sum_{k=-n}^{-1} X_k$ converges to $-\infty$ as $n \to \infty$, the random variable $\max\{S_{-n} : n \ge 0\}$ is finite a.s. Thus, some ancestor of 0 in the $C$-graph has infinitely many descendants. So, the component $[\mathbb{Z}_X^C(0), 0]$ of 0 in the $C$-graph is of class $\mathcal{I}/\mathcal{F}$. One can show that the smallest child of every vertex which lies on the bi-infinite path of $\mathbb{Z}_X^C(0)$ belongs to the bi-infinite path. Therefore, $[\mathbb{Z}_X^C(0), 0]$ is of class $\mathcal{I}/\mathcal{F}$ and has unique succession line (as it has ECS order).
<figure><img src="image_37.png" /><figcaption>Figure 6.4: An Illustration of Example 128. The top figure shows the trajectory of a realisation of the i.i.d. sequence $X = (X_n)_{n \in \mathbb{Z}}$, where $X_n \in \mathbb{Z}, \forall n$. The *C*-graph (**C** for climbing point vertex-shift) is drawn in red on the trajectory of the top figure. The vertices on the bi-infinite path are highlighted. The component of 0 in the *C*-graph is drawn in the middle figure. The bottom figure shows the trajectory of the sequence $Y = (Y_n)_{n \in \mathbb{Z}}$ which is obtained by applying the backward map $\Phi_R$ to the rooted tree shown in the middle figure. The component of 0 in the record graph of the trajectory in the bottom figure is the same as the component of 0 in the *C*-graph.</figcaption></figure>
<figure><img src="image_38.png" /></figure>
Bibliography

[1] Romain Abraham and Jean-François Delmas. An introduction to Galton-Watson trees and their local limits. arXiv:1506.05571 [math], June 2015.

[2] David Aldous. Asymptotic Fringe Distributions for General Families of Random Trees. *Annals of Applied Probability*, 1(2):228–266, May 1991.

[3] David Aldous and Russell Lyons. Processes on Unimodular Random Networks. *Electronic Journal of Probability*, 12:1454–1508, 2007.

[4] Søren Asmussen. *Applied probability and queues*. Springer, New York, 2003. OCLC: 51060198.

[5] François Baccelli and Pierre Brémaud. *Elements of Queueing Theory*. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.

[6] François Baccelli and Mir-Omid Haji-Mirsadeghi. Point-map-probabilities of a point process and Mecke's invariant measure equation. *The Annals of Probability*, 45(3):29.

[7] François Baccelli, Mir-Omid Haji-Mirsadeghi, and Ali Khezeli. Eternal Family Trees and dynamics on unimodular random graphs. In Florian Sobieczky, editor, *Contemporary Mathematics*, volume 719, pages 85–127. American Mathematical Society, 2018.

[8] Jürgen Bennies and Götz Kersting. A Random Walk Approach to Galton-Watson Trees. *Journal of Theoretical Probability*, 13(3):777–803, 2000.
[9] Rabi Bhattacharya and Edward C. Waymire. *Random Walk, Brownian Motion, and Martingales*, volume 292 of *Graduate Texts in Mathematics*. Springer International Publishing, Cham, 2021.

[10] Pierre Brémaud. *Probability Theory and Stochastic Processes*. University text. Springer International Publishing, Cham, 2020.

[11] Pablo Ferrari, Claudio Landim, and Hermann Thorisson. Poisson trees, succession lines and coalescing random walks. *Annales de l'Institut Henri Poincare (B) Probability and Statistics*, 40(2):141-152, April 2004.

[12] Sergey Foss and Stan Zachary. Stochastic Sequences with a Regenerative Structure that May Depend Both on the Future and on the Past. *Advances in Applied Probability*, 45(4):1083-1110, December 2013.

[13] Claude Godrèche, Satya N Majumdar, and Grégory Schehr. Record statistics of a strongly correlated time series: Random walks and Lévy flights. *Journal of Physics A: Mathematical and Theoretical*, 50(33):333001, August 2017.

[14] Jim Pitman. *Combinatorial Stochastic Processes*, volume 1875 of *Lecture Notes in Mathematics*. Springer-Verlag, Berlin/Heidelberg, 2006.

[15] Olav Kallenberg. *Foundations of Modern Probability*, volume 99 of *Probability Theory and Stochastic Modelling*. Springer International Publishing, Cham, 2021.

[16] Jean-François Le Gall. Random trees and applications. *Probability Surveys*, 2(0):245-311, 2005.

[17] Nicolas Curien. Lecture notes on random graphs. https://www.math.u-psud.fr/~curien/cours/cours-RG.pdf, February 2019.

[18] Nicolas Curien. Lecture notes on random walks and graphs. https://www.imo.universite-paris-saclay.fr/~nicolas.curien/enseignement.html, October 2022.

[19] Alexei Vladimirovich Stepanov. A Characterization Theorem for Weak Records. *Theory of Probability & Its Applications*, 38(4):762-764, December 1994.
[20] Hermann Thorisson. Coupling, stationarity, and regeneration. Probability and its applications (Springer-Verlag). Springer, New York, 2000.

[21] Gregor Wergen. Records in stochastic processes—theory and applications. Journal of Physics A: Mathematical and Theoretical, 46(22):223001, June 2013.
<figure><img src="image_39.png" /></figure>
<figure><img src="image_40.png" /></figure>
## RÉSUMÉ

Considérons une règle de navigation définie sur un graphe qui mappe chaque sommet du graphe à un sommet de telle manière que la règle de navigation commute avec chaque automorphisme du graphe. C'est à dire que la règle de navigation appliquée aux sommets reste la même après prise d'un éventuel automorphisme du graphe. Une telle règle de navigation est dite avoir la propriété de covariance. Cette étude se penche sur un ensemble de telles règles de navigation covariantes, indexées par des graphes localement finis et soumises à une condition de mesurabilité. Cet ensemble de règles est appelé déplacement de sommet. Plus généralement, on peut considérer les déplacements de sommets sur les réseaux, des graphes qui ont des étiquettes sur les arêtes et sur les sommets. Un déplacement de sommet induit une dynamique sur l'espace des réseaux enracinés localement finis. L'objectif central de ce travail réside dans l'étude de la dynamique associée à une règle de navigation spécifique appelée record vertex-shift. Il est défini sur les trajectoires de toute marche aléatoire discrète unidimensionnelle dont les incréments ont une moyenne finie et la marche aléatoire ne peut sauter que d'un pas vers la gauche. De plus, les travaux incluent plusieurs résultats notables concernant les déplacements de sommets d'enregistrement appliqués aux processus à incréments stationnaires. La thèse contient également des résultats sur les déplacements de sommets plus généraux sur les réseaux unimodulaires.

## MOTS CLÉS

unimodularité, graphe des records, limites locales, réseaux aléatoires

## ABSTRACT

Consider a navigation rule defined on a graph that maps every vertex of the graph to a vertex in such a way that the navigation rule commutes with every automorphism of the graph. It is to say that the navigation rule applied to the vertices remains the same after taking any automorphism of the graph. Such a navigation rule is said to have the covariance property. This study delves into a collection of such covariant navigation rules, indexed by locally finite graphs, and subject to a measurability condition. This ensemble of rules is termed a vertex-shift. More generally, one can consider vertex-shifts on networks, graphs that have labels on edges and on vertices. A vertex-shift induces a dynamic on the space of locally finite rooted networks. The central focus of this work lies in investigating the dynamic associated to a specific navigation rule called the record vertex-shift. It is defined on the trajectories of any one dimensional discrete random walk whose increments have finite mean and the random walk can jump only one step to the left. Additionally, the work includes several notable results concerning record vertex-shifts applied to processes with stationary increments. The thesis also contains results on more general vertex-shifts on unimodular networks.

## KEYWORDS

unimodularity, record graph, local limits, random networks