1. Introduction
To each integer n we assign a positive random integer an. Then, n is mapped an units to the right. Given a probability space (Ω, ℱ, P) supporting the random sequence {an}n∊ℤ, we consider the function f : Ω × ℤ → ℤ defined by f (ω, n) = n + an(ω). We assume the sequence {an}n∊ℤ is i.i.d. We study two objects arising from the random map f : a population dynamics and a directed random graph. When there is no chance of ambiguity, we omit ω in our notation.
In the population dynamics, individual n is born at time n and dies at time f(n). More precisely, the lifespan of individual n is assumed to be [n, n + an). Let N :={Nn}n∊ℤ be the discrete-time random process of the number of individuals alive at time n, or simply the population process. The process N can be seen as the number of customers at arrival epochs in a D/GI/∞ queue, namely a queueing system with one arrival at every integer time and i.i.d. integer-valued service times, all distributed like a 0. As a new arrival takes place at each integer, the population never goes extinct or, equivalently, the queue is never empty. Nonetheless, as we shall see, when E[a 0] < ∞ the stationary population process is regenerative. To visualize the number of individuals alive at time 0 we count the edges that cross over 0 and add the individual born at time 0 (Figure 1).
Figure 1: The population process. Here, a −6 = 8, a −5 = 3, a −4 = 8, a −3 = 3, a −2 = 3, and a −1 = 5. Assuming a −i < ifor all i > 6, there are four edges crossing 0. Individuals −6, −4, −2, and −1 are still alive at time 0. Hence, N 0 = 5, as it includes the individual born at 0.
By letting Vf = ℤ and Ef = {(n, f(n)) : n ∊ ℤ}, the random map f also induces a random directed graph Tf. Further, assuming the distribution of a 0 is aperiodic, we will show that Tfis a directed tree.
We interpret Tf as a family tree and connect it to the population process N. In order to gain insight, we draw a parallel with the classical age-dependent branching process. Such a process is built upon a lifetime distribution L on ℝ+ and an offspring distribution O on N. In this classical model, the first individual is born at time 0 and has a lifetime l sampled from L. When the first individual dies at l, it is replaced by its offspring, whose cardinality is sampled from O. From then on, each individual statistically behaves as the first one, with all individuals having independent lifetimes and offspring cardinalities (see e.g. [Reference Waugh10]).
Our family tree, in which individuals are indexed by ℤ, is obtained by declaring that the individual f(n) is the parent of n, f 2(n) is its grandparent, and so on. In terms of interpretation, this requires that we look at the population dynamics in reverse time. In ‘reverse time’, individual n ‘dies’ at time n (note that it is the only one to die at that time) and was ‘born earlier’, namely at time n + an. Since individual m is born at time n if f(n) = m, the setof children of m is f −1(m), the set of its grandchildren is f −2(m), and so on. As in the age-dependent branching process, each individual has exactly one parent, but may have no children, and the death time of an individual coincides with the birth time of its children. Also notice that f −1(n) ⊂ (−∞, n − 1]. That is, as in the natural enumerations used in branching processes, the children of individual n have ‘larger’ indices than that of individual n (recall that individuals are enumerated using their ‘death times’). Hence, each individual is born at the death of its parent and dies ‘after’ its parent. Figure 2 illustrates the relation between the population process and Tf. However, our age-dependent family tree is far from being that of the age-dependent branching process discussed above. In particular, there is no first individual: our family tree is eternal [Reference Baccelli, Haji-Mirsadeghi and Khezeli3]. More importantly, it lacks the independence properties of branching processes. In particular, the offspring cardinalities of different individuals are dependent.
Figure 2: From the population process to the family tree. The top figure depicts the f dynamics running on ℤ. The curved black lines represent individual lifespans. For example, individual 7 lives three units of time. The bottom figure depicts the tree representation of the dynamics on ℤ, with the directed edges representing parenthood. There, 7 is the child of 10, and has four children: 1, 4, 5, and 6. Individual 8, for example, has no children.
In the age-dependent branching process described above, if we set L = 1 we recover the Bienaymé–Galton–Watson process. Despite the fact that the building block of both our model and the Bienaymé–Galton–Watson model is just a sequence of i.i.d. random variables, the two models are quite different. In the former, the i.i.d. random variables define the offspring cardinalities. In the latter, they define the lifespans of individuals.
Moreover, in our model, the expected offspring cardinality of a typical individual is one. Hence, we follow the standard terminology of branching processes and say the population process is critical. In branching processes, the critical case leads to extinction unless there is no variability at all. In contrast, in our model there is no chance extinction regardless of the distribution of a 0 (Section 3).
The fact that when P [a 0 = 1] > 0 and E [a 0] < ∞ Tf, rooted at 0, is a unimodular directed tree, allows us to complement the classical queueing and regenerative analysis by structural observations that we believe to be new:
1. this tree is two ended;
2. an integer (individual) is either successful or ephemeral depending on whether the number of its descendants (pre-images by f) of all orders is infinite or finite almost surely (a.s.);
3. the set of successful (resp. ephemeral) integers forms a stationary point process;
4. there is a stationary thinning of the successful point process consisting of individuals such that all individuals born after one of them are its descendants; these are called original ancestors;
5. each individual has a finite number of cousins of all orders.
These structural observations are completed by closed-form expressions for the intensities of the point processes in question.
The last interpretation of the family tree pertains to renewal theory. One can see n, f(n), f 2(n), ... as a renewal process on the integers with interarrivals distributed like a 0and starting from time n. The graph Tf = (Vf, Ef) can hence be seen as the mesh of all such renewal processes. By mesh, we mean that the renewal process of n merges with that of m at the first time when the orbits {fp(n)}n ∊ℕ and {fq(m)}m ∊ℕ meet.
Section 2 is dedicated to the study of the population process. Section 3 investigates the family tree. Section 4 contains our final remarks.
2. Population and queue dynamics
In this section we study the population process
$${N_n} = \# \{ {\rm{all}} \;m \in \;{\mathbb {Z}}\; {\rm{such\;that}}\; m \lt n \;{\rm{and}} \; f(m) \gt n\} + 1,\quad n \in {\mathbb {Z}}.$$
Section 2.1 introduces our definitions and notation. In Section 2.2 we show that the population process is regenerative with independent cycles. In Section 2.3 an explicit formula for the moment-generating function of N 0 is given and it is indicated that this random variable is always light-tailed, regardless of the distribution of a 0. Finally, in Section 2.4 we work out the case in which a 0 follows a geometric distribution and the population process is consequently Markovian. The notions and proof techniques in this section are classical and details are kept to a minimum.
2.1. Definitions and assumptions
Let (Ω, ℱ, P, {θn}n∊ℤ) be the underlying probability space supporting all random elements discussed in this paper, endowed with a discrete flow. We assume P is preserved by θn, i.e. for all n,
$${\rm{P}} \circ \theta _n^{ - 1} = {\rm{P}}.$$
A random integer-valued discrete sequence W = {Wn}n∊ℤ defined on Ω is compatible with the flow {θn}n∊ℤ if Wn(ω) = W 0(θnω) for all n ∊ ℤ. Notice that, given (2.2), if a process W is compatible with {θn}n∊ℤ then it is strictly stationary. All integer-valued discrete sequences considered here are {θn}n∊ℤ-compatible (or, for short, stationary).
In particular, since a := {an}n∊ℤ is stationary, so is N := {Nn}n∊ℤ, assuming the population process starts at −∞.
Consider a stationary integer-valued discrete sequence {Un}n∊ℤ in which Un equals 0 or 1. Let {kn}n∊ℤ, with
$$ \cdots \lt {k_{ - 1}} \lt {k_0} \le 0 \lt {k_1} \lt {k_2} \lt \cdots ,$$
be the sequence of times at which Un = 1. A simple stationary point process (henceforth s.s.p.p.) on ℤ is then a random counting measure 
$$\Phi ( \cdot ) = \sum\nolimits_{n \in {\mathbb {Z}}} {\delta _{{k_n}}}( \cdot )$$, where 
$${\delta _{{k_n}}}( \cdot )$$ is the Dirac measure at kn. We often identify Φ with the sequence {kn}n∊ℤ, writing kn ∊Φ, whenever ({kn}) = 1.
The intensity of a s.s.p.p., denoted by λ Φ, is given by P [0 ∊Φ].
Let Φ be a s.s.p.p. on ℤ such that λ Φ > 0 and let PΦ[·] := P[·|0 ∊ Φ]. Then PΦ is the Palm probability of Φ. We denote by EΦ the expectation operator of PΦ. Consider the operator 
$${\theta _{{k_1}}}$$, i.e.
$$\Phi \circ {\theta _{{k_1}}}{\kern 1pt} : = \{ {k_{n + 1}} - {k_1}{\} _{n \in {\mathbb {Z}}}}.$$
Since 
$${\theta _{{k_1}}}$$ is a bijective map on Φ0 := {k 0(ω) = 0}, the following holds [Reference Heveling and Last5].
Lemma 2.1. The operator 
$${\theta _{{k_1}}}$$ preserves the Palm probability PΦ.
A s.s.p.p. Ψ on ℤ is an integer-valued renewal process if {kn − k n−1}n∊ℤ is i.i.d. under PΨ.
Finally, we say that a stationary process R := {Rn}n∊ℤ is regenerative if there exists an integer-valued renewal process Ψ = {kn}n∊ℤ such that under PΨ ({kn − k n−1}n>j, {Rn}n ≥kj) is independent of {k n − k n−1}n ≤j for all j ∊ℤ and its distribution does not depend on j. Moreover, R is regenerative with independent cycles if R is regenerative and {Rn}n< 0 is independent of {Rn}n ≥0 under PΦ. We call {k n}n∊ℤ the regeneration epochs of R.
For most of this work, unless otherwise stated, we assume {an}n∊ℤ is i.i.d., E [a 0] < ∞, and P[a 0 = 1] > 0.
Remark 2.1. Since randomness in this model comes from the sequence {an}n∊ℤ and θ 1 preserves P, by assuming {an}n∊ℤ is i.i.d. there is no loss of generality in assuming that (Ω, ℱ, P, {θn}n∊ℤ) is strongly mixing, i.e. lim
$$\mathop {\lim }\limits_{n \to \infty } {\rm{P}}{\kern 1pt} [A \cap {\theta _{ \pm n}}B] = {\rm{P}}{\kern 1pt} [A]{\kern 1pt} {\rm{P}}{\kern 1pt} [B]\quad {\rm{for}}\,{\rm{all}}\;A,B \in {\cal F}.$$
2.2. General case: main results
Theorem 2.1. LetΨo := {m ∊ ℤ : Nm = 1}. Then, Ψo is an integer-valued renewal process with intensity 
$${\lambda ^{\rm{o}}}{\kern 1pt} : = {\lambda _{{\Psi ^{\rm{o}}}}} = \prod\nolimits_{i = 1}^\infty {\rm{P}}{\kern 1pt} [{a_0} \le i] \gt 0$$.
The atoms of Ψo are called original ancestors as all individuals born after any of them are necessarily its descendants in the family tree Tf studied in Section 3.
Proof of Theorem 2.1. By (2.1), 
$${\rm{P}}{\kern 1pt} [{N_0} = 1] = {\rm{P}}{\kern 1pt} [ \cap _{j = 1}^\infty {a_{ - j}} \le j]$$. Then, as the sequence {an}n∊ℤ is i.i.d.,
$${\rm{P}}{\kern 1pt} [{N_0} = 1] = \prod\limits_{j = 1}^\infty {\rm{P}}{\kern 1pt} [{a_0} \le j].$$
Since P [a 0 = 1] > 0, none of the elements of the above product equals 0. Then, as E [a 0] < ∞, 
$$\prod\nolimits_{j = 1}^\infty {\rm{P}}{\kern 1pt} [{a_0} \le j] = {\rm{P}}{\kern 1pt} [{N_0} = 1] \gt 0$$ (see Appendix A, Lemma A.1). The stationarity of N implies that, for all n ∊ ℤ, P[Nn = 1] = P[N 0 = 1] > 0.
Since (Ω, ℱ, P, {θn}n∊ℤ) is strongly mixing (Remark 2.1), it is ergodic. Therefore, by Birkhoff’s pointwise ergodic theorem, for all measurable functions g : Ω → ℝ+ such that E[g] < ∞,
$$\mathop {\lim }\limits_{n \to \pm \infty } {1 \over n}\sum\limits_{i = 1}^{ \pm n} g \circ {\theta _{ \pm i}} = {\rm{E}}{\kern 1pt} [g]\quad {\rm{P}}{\kern 1pt} {\rm{- a.s.}}{\kern 1pt} $$
Let g = 1{N 0 = 1}. Then
$$\mathop {\lim }\limits_{n \to \pm \infty } {1 \over n}\sum\limits_{i = 1}^{ \pm n} 1\{ {N_0} = 1\} \circ {\theta _{ \pm i}} = {\rm{P}}{\kern 1pt} [{N_0} = 1] \gt 0\quad {\rm{P}}{\rm{ - a.s.}} $$
Hence, there exists a.s. a subsequence of distinct integers 
$${\Psi ^{\rm{o}}}{\kern 1pt} : = \{ k_n^{\rm{o}}{\} _{n \in {\mathbb {Z}}}}$$ satisfying (2.3) such that 
$${N_{k_n^{\rm{o}}}} = 1$$ for all n ∊ ℤ. Since {an}n∊ℤ is stationary, Ψo is a s.s.p.p. That Ψo is a renewal process is proved in Appendix A, Proposition A.1.
In order to show that N is a stationary regenerative process with respect to Ψo with independent cycles, we rely on the following lemma.
Lemma 2.2. Under PΨo , {an}n<0 is independent of {an}n ≥0.
Proof. Let g, f : Ω → ℝ+ be two measurable, continuous, bounded functions. Using the fact that the event 
$$\{ k_0^{\rm{o}} = 0\} $$ is equal, by definition, to {N 0 = 1} = {∩i>0a −i ≤ i}, we have
$$\matrix{
{{{\rm{E}}_{{\Psi ^{\rm{o}}}}}[g(\{ {a_n}{\} _{n \lt 0}}){\kern 1pt} f(\{ {a_n}{\} _{n \ge 0}})]} \hfill & = \hfill & {{\rm{E}}{\kern 1pt} [g(\{ {a_n}{\} _{n \lt 0}}){\kern 1pt} f(\{ {a_n}{\} _{n \ge 0}}){\kern 1pt} |{\kern 1pt} k_0^{\rm{o}} = 0]} \hfill \cr
{} \hfill & = \hfill & {{\rm{E}}{\kern 1pt} [g(\{ {a_n}{\} _{n \lt 0}}){\kern 1pt} f(\{ {a_n}{\} _{n \ge 0}}){\kern 1pt} |{ \cap _{i \gt 0}}{a_{ - i}} \le i].} \hfill \cr
} $$
Now, as {an}n≥0 is independent of {an}n<0 under P,
$$\eqalign{ & {\rm{E}}{\kern 1pt} [g(\{ {a_n}{\} _{n \lt 0}}){\kern 1pt} f(\{ {a_n}{\} _{n \ge 0}}){\kern 1pt} |{ \cap _{i \gt 0}}{a_{ - i}} \le i] \cr & \, = {\rm{E}}{\kern 1pt} [g(\{ {a_n}{\} _{n \lt 0}}){\kern 1pt} |{ \cap _{i \gt 0}}{a_{ - i}} \le i]{\kern 1pt} \,{\rm{E}}{\kern 1pt} [\,f(\{ {a_n}{\} _{n \ge 0}}){\kern 1pt} |{ \cap _{i \gt 0}}{a_{ - i}} \le i] \cr & \, = {{\rm{E}}_{{\Psi ^{\rm{o}}}}}[g(\{ {a_n}{\} _{n \lt 0}})]\,{{\rm{E}}_{{\Psi ^{\rm{o}}}}}[f(\{ {a_n}{\} _{n \ge 0}})], \cr} $$
completing the proof.
Corollary 2.1. The population process N is a stationary regenerative process with respect to Ψo with independent cycles.
Proof. Given 
$$k_0^{\rm{o}} = 0$$, i.e. under PΨo, we have N 0 = 1. Then 
$$(\{ k_n^{\rm{o}} - k_{n - 1}^{\rm{o}}{\} _{n \gt 0}}{\rm{ }}{\{ {N_n}\} _{n \ge 0}})$$ is a function of {an}n≥0, while 
$${\{ k_n^{\rm{o}}\} _{n \le 0}}$$ is a function of {an}n<0. Then, by Lemma 2.2, ({k n − k n−1}n> 0, {Nn}n≥0) is independent of {k n − k n−1}n≤0. By the same reasoning as in Lemma 2.2, 
$${\{ {a_n}\} _{n \ge {k_j}}}$$ is independent of $${\{ {a_n}\} _{n \lt {k_j}}}$$ for all j ∊ ℤ. It follows that 
$$(\{ {k_n} - {k_{n - 1}}{\} _{n \gt j}},\{ {N_n}{\} _{n \ge {k_j}}})$$ is independent of {k n − k n−1}n≤j for all j. We conclude that {Nn}n∊ℤ is a regenerative process.
The independence of the random vectors 
$${\{ {a_n}\} _{{k_j} \lt n \le {k_{j + 1}}}}$$ for j ∊ ℤ, which holds by the same reasoning used in Lemma 2.2, implies that {N n}n∈𝕫 is regenerative with independent cycles.
Remark 2.2. When we do not assume that P [a 0 = 1] > 0, let 
$$\underline m \gt 1$$ be the smallest integer such that 
$${\rm{P}}{\kern 1pt} [{a_0} = \underline m ] \gt 0$$. Then 
$${\rm{P}}{\kern 1pt} [{N_0} \lt \underline m ] = 0$$, while 
$${\rm{P}}{\kern 1pt} [{N_0} = \underline m ] = \prod\nolimits_{j = \underline m }^\infty {{\rm{P}}^0}[{a_0} \le j] \gt 0$$. Proceeding as in the proof of Theorem 2.1, we conclude that there exists an integer-valued renewal process 
$$\tilde \Phi $$ such that 
$${k_n} \in \tilde \Phi $$
if and only if 
$${N_{{k_n}}} = \underline m $$.
2.3. Analytical properties of Nn
We now turn to some analytical properties of N. Some of our results are adapted from the literature on GI/GI/∞ queues, i.e. queues with an infinite number of servers, and independently distributed arrival and service times. Proofs can be found in Appendix A. The results in this subsection do not depend on the assumption P [a 0 = 1] > 0.
The following proposition can be extended to the case in which {an}n∊ℤ is stationary rather than just i.i.d.
Proposition 2.1. For all n ∊ ℤ, E[a 0] = E[Nn].
Proposition 2.1 is Little’s law for the infinite server queue, i.e. the expected number of individuals being served equals the arrival rate multiplied by the expected service time given that there is an arrival at the origin a.s. (see e.g. [Reference Asmussen2]). This shows that the mean number of customers in steady state is finite if and only if the expected service time is finite.
A general formula for the moment-generating function of the number of customers in steady state in a GI/GI/∞ queue can be found in [Reference Szechtman and Glynn9]. We limit ourselves to showing that N 0 is a light-tailed random variable regardless of the distribution of a 0. The latter property has the following intuitive basis: N 0 is large only if several realizations of {an}n<0 are large as well. Another way to get an intuition for this result is if we let the arrival times be exponentially distributed with parameter λ. Then one can show that N 0 has a Poisson distribution with parameter λE[a 0], and it is light-tailed regardless of the tail of a 0.
Proposition 2.2. The moment-generating function of N 0 is given by
$${\rm{E}}{\kern 1pt} [{{\rm{e}}^{t{N_0}}}] = {{\rm{e}}^t}\prod\limits_{i = 1}^\infty ({{\rm{e}}^t}{\rm{P}}{\kern 1pt} [{a_0} \gt i] + {\rm{P}}{\kern 1pt} [{a_0} \le i])\quad for\,all\;t \in {\mathbb {R}}.$$
Moreover, 
$${\rm{E}}{\kern 1pt} [{{\rm{e}}^{t{N_0}}}] \lt \infty $$ for all t ∊ ℝ.
2.4. Geometric marks
In general, the process N is not Markovian. However, it is when the marks are geometrically distributed. Let us assume a 0 is geometrically distributed supported on ℕ+ with parameter s. Let r = 1 − s. Then, due to the memoryless property, N is a time-homogeneous, aperiodic, irreducible Markov chain with state space {1, 2, 3,...}, whose transition matrix is given by
$${\rm{P}}{\kern 1pt} [{N_n} = n|{N_{n - 1}} = k] = \left(\begin{array}{c}k\\ n-1\end{array}\right) {r^{\,n - 1}}{s^{k - n + 1}},\quad 1 \le n \le k + 1.$$
Proposition 2.3. In the geometric case, the probability-generating function of Nn at steady state observes the functional relation
$$G(z) = zG(sz + r).$$
Proof. Let 
$${\{ {\tilde N_n}\} _{n \ge 0}}$$ be the population process starting at 0 and Gm(z), z ∊ [0, 1], the probability-generating function of 
$${\tilde N_m}$$. Using (2.5),
$${\rm{E}}{\kern 1pt} [{z^{{{\tilde N}_n}}}{\kern 1pt} |{\kern 1pt} {\tilde N_{n - 1}} = k] = \sum\limits_{n = 1}^{k + 1} \left(\begin{array}{c}k\\ n-1\end{array}\right){r^{\,n - 1}}{s^{k - n + 1}}{z^n} = z\sum\limits_{n' = 0}^k \left(\begin{array}{c}k\\ n'\end{array}\right)(rz{)^{n'}}{s^{k - n'}},$$
where n ′ = n − 1. So,
$${\rm{E}}{\kern 1pt} [{z^{{{\tilde N}_n}}}{\kern 1pt} |{\kern 1pt} {\tilde N_{n - 1}} = k] = z{(rz + s)^k}.$$
Hence,
$${G_m}(z) = \sum\limits_{k = 1}^m {\rm{P}}{\kern 1pt} [{\tilde N_{m - 1}} = k](z{(rz + s)^k}) = z{G_{m - 1}}(rz + s).$$
Letting m →∞ we get (2.6).
Using (2.6) we can easily compute the moments of N 0. For example, by differentiating both sides and setting z = 1 we get
$${\rm{E}}{\kern 1pt} [{N_0}] = {1 \over s},$$
which is the mean of a 0, as expected. Proceeding the same way, the second moment is given by
$${\rm{E}}{\kern 1pt} [N_0^2] = {{2r} \over {s(1 - {r^2})}}.$$
Remark 2.3. By (2.4), and noticing that P [ai > i] = ri, we get
$$G(z) = z\prod\limits_{i = 1}^\infty (z{r^{\,i}} + 1 - {r^{\,i}}).$$
By Lemma A.1 in Appendix A, 
$$\prod\nolimits_{i = 1}^\infty (z{r^{\,i}} + 1 - {r^{\,i}})$$ converges for all z ∊ ℝ as 
$$\sum\nolimits_{i = 1}^\infty {r^{\,i}} \lt \infty $$.
3. The eternal family tree
In this section we study the directed graph Tf = (Vf, Gf), where Vf = ℤ and Ef = {(n, f(n)) : n ∊ ℤ}. In Section 3.1 we show that Tf is an infinite tree containing a unique bi- infinite path. The indexes of the nodes on this bi-infinite path form a s.s.p.p. on ℤ with positive intensity. We derive this result by exploiting the fact that Tf is an eternal family tree, i.e. the out-degrees of all vertices are exactly one [Reference Baccelli, Haji-Mirsadeghi and Khezeli3].
In the following two sections we delve deeper into the genealogy of Tf. In Section 3.2 we give the basic properties of certain s.s.p.p.s derived from Tf. First, the process of integers forming the bi-infinite path: each integer in it is called successful, since its lineage (the set of its descendants) has infinite cardinality a.s. Second, we consider the process coming from the complement of the bi-infinite path: each integer in it is called ephemeral, since its lineage is finite a.s. Third, we consider the process of original ancestors defined in Theorem 2.1, which is a subprocess of the first.
In Section 3.3 we look at the set of direct ephemeral descendants of a successful integer n, whose path to n on Tf consists only of ephemerals. The conservation law that defines unimodular networks allows us to establish probabilistic properties of the set of direct ephemeral descendants and the set of cousins of a typical successful node.
3.1. The global properties of Tf
Theorem 3.1. The directed random graph Tf is a tree with a unique bi-infinite path for which the corresponding nodes, when mapped to ℤ, form a s.s.p.p. with positive intensity.
In order to prove Theorem 3.1 we resort to recent results on dynamics on unimodular networks [Reference Baccelli, Haji-Mirsadeghi and Khezeli3]. In Appendix B we present a brief review of definitions and properties of unimodular networks that we use. First, we notice that the directed graph G = (V, E), where V = ℤ and E ={(n, n + 1) : n ∊ ℤ}, rooted at 0, in which each node n is assigned a mark an,is a locally finite unimodular random network. Second, we notice that f is a translation-invariant dynamics on this network; more precisely, it is a covariant vertex-shift (see Appendix B, Definition B.2).
Define the connected component of n as
$$C(n) = \{ m \in {\mathbb {Z}} \,{\rm{s.t.}}\;\exists \quad i,j \in {\mathbb {N}}\,{\rm{with}}\,{f^i}(n) = {f^j}(m)\} .$$
Proposition 3.1. The directed random graph Tf has only one connected component.
Proof. Consider the process of original ancestors, Ψo as defined in Theorem 2.1, and let m ∊ Ψo. Then, for every n < m, n ∊ C(m). Hence, the result follows from the fact that Ψo is a s.s.p.p. consisting of an infinite number of points a.s.
Let
$$D(n) = \{ m \in {\mathbb {Z}}\,{\rm{s}}.{\rm{t}}.\,\,\exists \quad j \in {\mathbb {N}}\,{\rm{with}}\,{f^i}(m) = n\} $$
denote the set of descendants of n. Also let
$$L(n) = \{ m \in {\mathbb {Z}}\,{\rm{s.t.}} \;\exists\, j \in {\mathbb {N}}\, {\rm{with}}\,{f^j}(m) = {f^j}(n)\} $$
denote the set of cousins of n of all degrees (this set is referred to as the foil of n in [Reference Baccelli, Haji-Mirsadeghi and Khezeli3]).
We further subdivide D(n) and L(n)in terms:
$${D_i}(n) = \{ m \in {\mathbb {Z}}\; {\rm{s.t.}} \;{f^i}(m) = n\} ,\quad i \ge 0$$
and
$${L_i}(n) = \{ m \in {\mathbb {Z}}\; {\rm{s.t.}} \;{f^i}(m) = {f^i}(n)\} ,\quad i \ge 0.$$
So Di(n) is the set of descendants of degree i of n and Li(n) the set of cousins of degree i of n.
Lower-case letters denote the cardinalities of the above sets. So c(n) is the cardinality of C(n), di(n) is the cardinality of Di(n), and so on. Moreover, d ∞(n) denotes the weak limit of di(n) (if such a limit exists).
It is shown in [Reference Baccelli, Haji-Mirsadeghi and Khezeli3] that each connected component of a graph generated by the action of a covariant vertex-shift on a unimodular network, C(n), falls within one of the following three categories:
Class F/F: c(n) < ∞ and for all v ∊ C(n), l(v) < ∞. In this case C(n) has a unique cycle.
Class I/F: c(n) = ∞ and for all v ∊ C(n), l(v) < ∞. In this case, C(n) is a tree containing a unique bi-infinite path. Moreover, the bi-infinite path forms a s.s.p.p. on ℤ with positive intensity.
Class I/I: c(n) = ∞ and for all v ∊ C(n), l(v) =∞. In this case, C(n) is a one-ended tree such that d ∞(v) = 0 for all v ∊ C(n).
Notice that the dynamics f precludes the connected component ℤ of being of class F/F. Theorem 3.1 follows from proving that, in our case, C(0) is of class I/F. We rely on the following lemma derived from the results found in [Reference Baccelli, Haji-Mirsadeghi and Khezeli3].
Lemma 3.1. A connected component C(m) is of class I/I if and only if for all n ∊ C(m),P[d(n) = ∞] = 0.
Proof of Theorem 3.1. For k ∊ Ψo, we have d(k) = ∞ a.s., and consequently C(k) is of class I/F. Since there is a unique component, the result follows.
The next proposition concerns the case in which it is not necessarily assumed that P[a 0 = 1] > 0.
Proposition 3.2. Let d = gcd{n ∊ ℤ : P[an > 0] > 0}, i.e. assume that the distribution of a 0 has period d. Then Tf has d connected components. Each connected component is a tree with a unique bi-infinite path. Hence, when d > 1,Tf is a forest.
Proof. First we deal with the aperiodic case, i.e. d = 1. Consider the processes {V (m)}m∊ℤ in which
$$u_n^{(0)} = \left\{ {\matrix{ 1 \hfill & {{\rm{if}}\;{\rm{there}}\;{\rm{exists}}\;j \ge \;0\,{\rm{s}}.{\rm{t}}.\;\sum\nolimits_{i = 0}^j {a_i^{\prime \prime }} = n,} \hfill \cr 0 \hfill & {{\rm{otherwise}}} \hfill \cr } } \right.$$
Since, for j > 0, 
$${f^j}(m) = {a_{{f^{j - 1}}(m)}} + {f^{j - 1}}(m)$$, we have, for all m ∊ ℤ, that V (m) is a renewal process starting from m, in which the distribution of the inter-arrivals is the same as the distribution of a 0.Let
$${\tau _{(0,m)}} = \inf \{ n \ge 0{\kern 1pt} :{\kern 1pt} v_n^{(m)} = v_n^{(0)} = 1\} .$$
Then m ∊ C(0) if and only if τ (0,m) < ∞ a.s.
Now let U (0) and U (m) be two independent renewal processes, which are also independent of {V (m)}m∊ℤ. We assume the first arrival of U (m) happens at m and that of U (0) happens at 0. The distributions of the inter-arrivals of U (0) and U (m) are the same as the distribution of a 0.
More precisely, let 
$${\{ {a'_n}\} _{n \ge 0}}$$ and 
$${\{ {a''_n}\} _{n \ge 0}}$$ be two independent sequences of i.i.d. random variables, also independent of {an}n∊ℤ, in which 
$${a'_0}\mathop = \limits^{\rm{D}} {a''_0}\mathop = \limits^{\rm{D}} {a_0}$$. Then 
$${U^{(0)}} = \{ u_n^{(0)}{\} _{n \ge 0}}$$ and 
$${U^{(m)}} = \{ u_n^{(m)}{\} _{n \ge m}}$$, where
$$u_n^{(0)} = \left\{ {\matrix{ 1 \hfill & {{\rm{if}}\;{\rm{there}}\;{\rm{exists}}\;j \ge \;0\,{\rm{s}}.{\rm{t}}.\;\sum\nolimits_{i = 0}^j {a_i^\prime } = n,} \hfill \cr 0 \hfill & {{\rm{otherwise}}} \hfill \cr } } \right.$$;
and
$$u_n^{(0)} = \left\{ {\matrix{ 1 \hfill & {{\rm{if}}\;{\rm{there}}\;{\rm{exists}}\;j \ge \;0\,{\rm{s}}.{\rm{t}}.\;\sum\nolimits_{i = 0}^j {a_i^{\prime \prime }} = n,} \hfill \cr 0 \hfill & {{\rm{otherwise}}} \hfill \cr } } \right.$$
Notice that 
$${V^{(0)}}\mathop = \limits^{\rm{D}} {U^{(0)}}$$ and 
$${V^{(m)}}\mathop = \limits^{\rm{D}} {U^{(m)}}$$.
Define 
$${\sigma _{(0,m)}} = \inf \{ n \ge 0{\kern 1pt} :{\kern 1pt} u_n^{(m)} = u_n^{(0)} = 1\} $$. We will show that 
$${\sigma _{(0,m)}}\mathop = \limits^{\rm{D}} {\tau _{(0,m)}}$$. For any n > 0 and p, q ∊ ℕ, let
$$\eqalign{ & {\cal A}(p,q;\;n) = \{ ({k_0}, \ldots ,{k_p}) \in {\mathbb {N}}{^p},({l_0}, \ldots ,{l_p}) \in {\mathbb {N}}{^q}{\kern 1pt} :{\kern 1pt} 0 = {k_0} \lt {k_1} \lt \cdots \lt {k_p} = n, \cr & m = {l_0} \lt {l_1} \lt cdots \lt {l_q} = n, {\kern 1pt} {\rm{and}}{\kern 1pt} \{ {k_1}, \ldots ,{k_{p - 1}}\} \cap \{ {l_1}, \ldots ,{l_{q - 1}}\} = {\rm{{\phi}}}\} . \cr} $$]></tex-math>
</alternatives>
</disp-formula></p>
<p>Then
<disp-formula id="disp23">
<alternatives>
<graphic xlink:href="S002190021900024X_eqn30" mime-subtype="gif" mimetype="image" xlink:type="simple"/>
<tex-math><
$$\{ {\sigma _{(0,m)}} = n\} = \bigcup\limits_{p,q \in {\mathbb {N}}} \bigcup\limits_{{\scriptstyle ({k_0}, \ldots ,{k_p},{l_0}, \ldots ,{l_q}) \atop \scriptstyle \in {\cal A}(p,q;n)} } \bigcap\limits_{{\scriptstyle i \in \{ 1, \ldots ,p\} \atop \scriptstyle j \in \{ 1, \ldots ,q\} } } \{ {a'_{i - 1}} = {k_i} - {k_j},{a''_{j - 1}} = {l_j} - {l_{j - 1}}\} .$$
By the definition of f, and since {an}n∊ℤ is i.i.d., we have
$$\eqalign{ & {\rm{P}}\;{\kern 1pt} [{\tau _{(0,m)}} = n] \cr & = \sum\limits_{p,q \in {\mathbb {N}}} \sum\limits_{{\scriptstyle ({k_0}, \ldots ,{k_p},{l_0}, \ldots ,{l_q}) \atop \scriptstyle \in {\cal A}(p,q;n)} } \prod\limits_{{\scriptstyle i \in \{ 1, \ldots ,p\} \atop \scriptstyle j \in \{ 1, \ldots ,q\} } } {\rm{P}}\;{\kern 1pt} [{a_{{k_{i - 1}}}} = {k_i} - {k_{i - 1}},{a_{{l_{j - 1}}}} = {l_j} - {l_{j - 1}}] \cr & = \sum\limits_{p,q \in {\mathbb {N}}} \sum\limits_{{\scriptstyle ({k_0}, \ldots ,{k_p},{l_0}, \ldots ,{l_q}) \atop \scriptstyle \in {\cal A}(p,q;n)} } \prod\limits_{{\scriptstyle i \in \{ 1, \ldots ,p\} \atop \scriptstyle j \in \{ 1, \ldots ,q\} } } {\rm{P}}\;{\kern 1pt} [{a_0} = {k_i} - {k_{i - 1}}]{\kern 1pt} {\rm{P}}\;{\kern 1pt} [{a_0} = {l_j} - {l_{j - 1}}]. \cr} $$
Similarly,
$$\eqalign{ & {\rm{P}}{\kern 1pt} [{\sigma _{(0,m)}} = n] \cr & = \sum\limits_{p,q \in {\mathbb {N}}} \sum\limits_{{\scriptstyle ({k_0}, \ldots ,{k_p},{l_0}, \ldots ,{l_q}) \atop \scriptstyle \in {\cal A}(p,q;n)} } \prod\limits_{{\scriptstyle i \in \{ 1, \ldots ,p\} \atop \scriptstyle j \in \{ 1, \ldots ,q\} } } {\rm{P}}\,{\kern 1pt} [{{a'}_{i - 1}} = {k_i} - {k_{i - 1}}]{\kern 1pt} {\rm{P}}\,[{{a''}_{j - 1}} = {l_j} - {l_{j - 1}}] \cr & = \sum\limits_{p,q \in {\mathbb {N}}} \sum\limits_{{\scriptstyle ({k_0}, \ldots ,{k_p},{l_0}, \ldots ,{l_q}) \atop \scriptstyle \in {\cal A}(p,q;n)} } \prod\limits_{{\scriptstyle i \in \{ 1, \ldots ,p\} \atop \scriptstyle j \in \{ 1, \ldots ,q\} } } {\rm{P}}\,[{a_0} = {k_i} - {k_{i - 1}}]{\kern 1pt} {\rm{P}}\,{\kern 1pt} [{a_0} = {l_j} - {l_{j - 1}}]. \cr} $$
From (3.2) and (3.3), we conclude that for all n ≥ 0, P [σ (0,m) = n] = P[τ (0,m) = n]. Therefore, 
$${\tau _{(0,m)}}\mathop = \limits^{\rm{D}} {\sigma _{(0,m)}}$$.
It is well known that P [σ (0,m) < ∞] = 1 (see e.g.[Reference Lindvall7]). This result is an incarnation of Doeblin’s coupling for independent discrete renewal processes. Therefore P [τ (0,m) < ∞] = 1 as well, so m ∊ C(0) a.s. As this result holds for any m ∊ ℤ, there exists a unique connected component.
Next we will show that the unique connected component is of class I/ F, so Tf is a tree with a unique bi-infinite path. From Proposition 2.1 we know N 0 < ∞. Assume N 0 = q and let {n 1,..., nq} be the set of individuals alive at time 0. This set of individuals must have, jointly, an infinite number of descendants, i.e. 
$$\sum\nolimits_{i = 1}^q d({n_i}) = \infty $$. If not, since there is a unique connected component, we would have N 0 = ∞, a contradiction. Consequently, there exists at least one individual alive at time 0 having an infinite number of descendants. We conclude, invoking Proposition 3.1, that C(0) is of class I/ F.
When d > 1, C(i) = i + dℤ for i ∊ {0,..., d − 1}, so there are d connected components. That C(i) ⊂ i + dℤ follows from the periodicity of a 0. For any m ∊ i + dℤ, the coupling argument used in the aperiodic case applies, so m ∊ C(i). Therefore i + dℤ ⊂ C(i) for i ∊ {0,..., d − 1}.
Since (i) there is at least one individual alive at time 0 which belongs to dℤ (namely, individual 0), (ii) N 0 < ∞, and (iii) the number of connected components is finite, we conclude that there is at least one individual alive at time 0 which both belongs to dℤ and has an infinite number of descendants in dℤ. It then follows that C(0) is of class I/ F,again from Proposition 3.1. The same reasoning implies that C(i) is of class I/ F for all i ∊{1,..., d − 1}, completing the proof.
Definition 3.1. (Diagonally invariant functions.) A measurable function h : Ω × ℤ × ℤ → ℝ is said to be diagonally invariant if h(θk(ω), m, n) = h(ω, m + k, n + k) for all k, m, n ∊ ℤ.
We notice that Tf, rooted at 0, is itself a unimodular network [Reference Baccelli, Haji-Mirsadeghi and Khezeli3]. Unimodularity is characterized by the fact that such a network satisfies the mass transport principle (see Appendix B). In our setting, the mass transport principle takes the following form: for all diagonally invariant functions h (Definition 3.1),
$${\rm{E}}\left[ {\sum\limits_{n \in {\mathbb {Z}}} h(n,0)} \right] = {\rm{E}}\left[ {\sum\limits_{n \in {\mathbb {Z}}} h(0,n)} \right].$$
3.2. Successful and ephemeral individuals, and original ancestors
From the analysis of the population process and the shape of Tf, we learned that f defines three s.s.p.p.s on ℤ related to the genealogy of Tf:
Φs: the set of successful individuals, consisting of individuals n ∊ ℤ having an infinite number of descendants in Tf.
Ψ o: the set of original ancestors (defined in Section 2), consisting of all individuals n ∊ ℤ such that for all m < n, m is a descendant of n in Tf. Clearly, Ψo ⊂ Φs.
Φ e: the set of ephemeral individuals, consisting of individuals n ∊ ℤ which have a finite number of descendants in Tf. Clearly, Φe ∪ Φs = ℤ.
We now look at the basic properties of these processes. In what follows we let Es := EΦs , i.e. Es is the expectation operator of the Palm probability of Φs. In the same vein, Ee := EΦe and Eo := EΦo.
Proposition 3.3. Let λ s be the intensity of Φs. Then
$${\lambda ^{\rm{s}}} = {1 \over {{\rm{E}}{\kern 1pt} [{a_0}]}}.$$
It follows that the intensity of Φe, λ e, equals 
$$1 - {1 \over {{\rm{E}}{\kern 1pt} [{a_0}]}}$$.
Proof. Let S 0 = 0 and Sn = a 1 + a 2 + ··· + an. Consider the associated renewal sequence U = {uk}k≥0 defined as
$${u_k} = {\rm{P}}{\kern 1pt} [{S_n} = k {\kern 1pt} {\rm{for}}\;{\rm{some}}\;n \ge \;0{\kern 1pt} ],$$
so uk is the probability that k is hit at some renewal epoch Sn. Since the distribution of {an}n∊ℤ is aperiodic, as P [a 0 = 1] > 0, 
$${u_k} \to {1 \over {{\rm{E}}{\kern 1pt} [{a_0}]}}$$, as k → ∞, P-a.s. As limk→∞ uk = P[0 ∊ Ψs] = λ s and λ s + λ e = 1, the result follows.
Remark 3.1. As 
$$\prod\nolimits_{i = 1}^\infty {\rm{P}}{\kern 1pt} [{a_0} \le i] \le {1 \over {{\rm{E}}{\kern 1pt} [{a_0}]}},{\rm{ }}{\lambda ^{\rm{o}}} \le {\lambda ^{\rm{s}}}$$, as expected.
We know from [Reference Baccelli, Haji-Mirsadeghi and Khezeli3] that E [dn(0)] = 1, i.e. the expected number of descendants of all degrees of a typical integer is one. This result follows from the mass transport principle. The process of successful individuals is locally supercritical, while the process of ephemeral individuals is locally subcritical, as the next proposition shows.
Proposition 3.4. Assume P[a 0 = 1] ∊ (0, 1). Then, for all n ≥ 1, Es[dn(0)] > 1, while Ee[dn(0)] < 1.
Proof. By the law of total probability and the definition of Ps and Pe,
$${{\rm{E}}^{\rm{s}}}[{d_n}(0)]{\lambda ^{\rm{s}}} + {{\rm{E}}^{\rm{e}}}[{d_n}(0)]{\lambda ^{\rm{e}}} = {\rm{E}}{\kern 1pt} [{d_n}(0)] = 1.$$
Since a successful individual has at least one descendant of degree n a.s., P [a 0 = 1] < 1, and λ e = 1 −λ s, it follows that Es[dn(0)] > 1 and Ee[dn(0)] < 1.
3.3. Cousins and direct ephemeral descendants
Given a successful node n, we say that an ephemeral individual m is a direct ephemeral descendant of n if n is the first successful individual in the ancestry lineage of m. The setof direct ephemeral descendants of n is given by
$${D^{\,{\rm{e}}}}(n) = \{ m \in D(n) \cap {\Phi ^{\rm{e}}}{\kern 1pt} :{\kern 1pt} {\kern 1pt} {\rm{for}}\;{\rm{the}}\;{\rm{smallest}}\;k \gt 0\;{\rm{s.t.}}\;{f^k}(m) = n \in \;{\Phi ^{\;{\rm{s}}}}{\kern 1pt} \} ,$$
where D(n) is the set of descendants of all degrees of n (Equation (3.1)). By Theorem 3.1, the cardinality of D e(n), denoted by d e(n), is finite. Moreover, for m ≠ n ∊ Ψs, D e(n) ∩ D e(m) = ø.
Figure 3: The direct ephemeral descendants and the cousins of 0. Above we have a realization of Tf and below the corresponding representation on ℤ. Here, −3, 0, 3, and 6 belong to the bi-infinite path (denoted by discs with dashed boundaries). The grey discs represent the individuals that are the direct ephemeral descendants of 0, while the black ones are cousins. Individual 0 has two ephemeral children (nodes −1 and −2), one successful (node −3), and one ephemeral grandchild (node −5). It has a first-degree cousin (node 2) and two second-degree cousins (nodes −6 and 4). While any descendant of 0 must be to the left of it on ℤ, cousins can be either to the left or the right.
Definition 3.2. (Direct ephemeral descendants partition.) Let
$${\tilde D^{\rm{e}}}(n){\kern 1pt} : = {D^{\,{\rm{e}}}}(n) \cup \{ n\} $$
be the directed ephemeral tree rooted at n ∊ Φs. The direct ephemeral descendant partition is
$${{\cal P}^D}{\kern 1pt} : = \{ {\tilde D^{\rm{e}}}(n){\kern 1pt} :{\kern 1pt} n \in {\Phi ^{\rm{s}}}\} .$$
By convention, any individual n is a cousin of itself (i.e. n is a 0-degree cousin of itself). Moreover, if m ≠ n both belong to Ψs, then L(n) ∩ L(m) = ø, as either m is a descendant or an ancestor of n. In other words, for n ∊ Φs, L(n)\{n} ⊂ Φe. Hence we get the following partition.
Definition 3.3. (Successful cousin partition.) The cousin partition of ℤ is
$${{\cal P}^L}{\kern 1pt} : = \{ L(n){\kern 1pt} :{\kern 1pt} n \in {\Phi ^{\rm{s}}}\} .$$
Figure 3 illustrates 
$${\tilde D^{\rm{e}}}(0)$$ and L(0). For all n ∊ Ψe and j > 0, let 
$$d_j^{\,{\rm{e}}}(n) = \# \{ {d^{\,{\rm{e}}}}(n) \cap {D_j}(n)\} $$ be the number of directed ephemeral descendants of degree j of n. By construction, the following equality holds for all j > 0 Ps-a.s. (see Figure 4):
$${l_j}(0) = d_j^{\,{\rm{e}}}(k_j^{\,{\rm{s}}}),$$
so that
$$l(0) = \sum\limits_{j = 1}^\infty d_j^{\,{\rm{e}}}(k_j^{\,{\rm{s}}}) + 1.$$
Figure 4: Cousins and the direct ephemeral descendants trees. The integers {k si}4i =1 represent the successful individuals. The notation I (n,m ) reads ‘individual I of the nth layer of the the direct ephemeral descendant tree (d.e.d.t.) of k sm’. For example, 2(2, 4) is the second individual in the second layer of the d.e.d.t. of k s4. Each box contains the cousins of k s0 of different degrees. The lower box contains the first-degree cousins, the middle box contains the second-degree cousins, and the top box contains the fourth-degree cousins (there are no third-degree cousins). Equivalently, the lower box contains all elements of the first layer of the d.e.d.t. of k s1, the middle box contains all elements of the second layer of the d.e.d.t. of k s2, and the top box contains all elements of the fourth layer of the d.e.d.t. of k s4.As the d.e.d.t. of k s3 has no third layer, k s0 has no third-degree cousins.
Proposition 3.5. For all j ≥ 1 and q ≥ 0, 
$${{\rm{P}}^{\rm{s}}}[d_j^{\,{\rm{e}}}(0) = q] = {{\rm{P}}^{\rm{s}}}[{l_j}(0) = q]$$.
Proof. From (3.4), for all j ≥ 1 and q ≥ 0,
$${{\rm{P}}^{\rm{s}}}[{l_j}(0) = q] = {{\rm{P}}^{\rm{s}}}[d_j^{\,{\rm{e}}}(k_j^{\,{\rm{s}}}) = q].$$
As 
$${\theta _{k_j^{\,{\rm{s}}}}}$$ preserves Ps,
$${{\rm{P}}^{\rm{s}}}[d_j^{\,{\rm{e}}}(k_j^{\,{\rm{s}}}) = q] \circ \theta _{k_j^{\,{\rm{s}}}}^{ - 1} = {{\rm{P}}^{\rm{s}}}[d_j^{\,{\rm{e}}}(0) = q],\quad {\rm{for}}\,{\rm{all}}\;q \ge 1.$$
We then get the result by combining Equations (3.5) and (3.6).
Proposition 3.6. Given 0 ∊ Φe, let n (d) be the unique random successful individual such that 
$$0 \in {\tilde D^{\rm{e}}}({n^{(d)}})$$. In the same way, letn (l) be the unique successful individual such that 0 ∊ L(n (l)).
Then, for any diagonally invariant function g (Definition 3.1),
$${\lambda ^{\rm{s}}}{{\rm{E}}^{\rm{s}}}\left[\sum\limits_{n \in {{\tilde D}^{\rm{e}}}(0)} g(0,n)\right] = {\lambda ^{\rm{s}}}{{\rm{E}}^{\rm{s}}}[g(0,0)] + {\lambda ^{\rm{e}}}{{\rm{E}}^{\rm{e}}}[g({n^{(d)}},0)]$$
and
$${\lambda ^{\rm{s}}}{{\rm{E}}^{\rm{s}}}\left[\sum\limits_{n \in L(0)} g(0,n)\right] = {\lambda ^{\rm{s}}}{{\rm{E}}^{\rm{s}}}[g(0,0)] + {\lambda ^{\rm{e}}}{{\rm{E}}^{\rm{e}}}[g({n^{(l)}},0)].$$
Proof. Equation (3.7) follows from applying the mass transport principle to the diagonally invariant function
$${h_1}(\omega ,0,n){\kern 1pt} : = 1\{ 0 \in {\Phi ^{\rm{s}}}(\omega )\} 1\{ n \in {\tilde D^{\rm{e}}}(0)(\omega )\} g(\omega ,0,n),$$
while (3.8) follows from applying the mass transport principle to the diagonally invariant function
$${h_2}(\omega ,0,n){\kern 1pt} : = 1\{ 0 \in {\Phi ^{\rm{s}}}(\omega )\} 1\{ n \in L(0)(\omega )\} g(\omega ,0,n).$$
Corollary 3.1. The following holds:
$${{\rm{E}}^{\rm{s}}}[{\tilde d^{\,{\rm{e}}}}(0)] = {{\rm{E}}^{\rm{s}}}[l(0)] = {\rm{E}}{\kern 1pt} [{a_0}],$$
where 
$${\tilde d^{\,{\rm{e}}}}(0)$$ is the cardinality of 
$${\tilde D^{\rm{e}}}(0)$$. Moreover,
$${{{{\rm{E}}^{\rm{s}}}[\sum\nolimits_{n \in {{\tilde D}^{\rm{e}}}(0)} {|n|} ]} \over {{{\rm{E}}^{\rm{e}}}[|{n^{(d)}}|]}} = {{{{\rm{E}}^{\rm{s}}}[\sum\nolimits_{n \in L(0)} {|n|} ]} \over {{{\rm{E}}^{\rm{e}}}[|{n^{(l)}}|]}} = {\rm{E}}{\kern 1pt} [{a_0}] - 1.$$
Proof. The results follow from choosing particular diagonally invariant functions in Proposition 3.6. Let g(0, n) ≡ 1. Then (3.9) holds as λ s + λ e = 1 and 
$${\lambda ^{\rm{s}}} = {1 \over {{\rm{E}}{\kern 1pt} [{a_0}]}}$$. Set g(0, n) = |n|. Again, using (3.7),
$${\lambda ^{\rm{s}}}{{\rm{E}}^{\rm{s}}}\left[\sum\limits_{n \in {{\tilde D}^{\rm{e}}}(0)} |n|\right] = {\lambda ^{\rm{s}}}{{\rm{E}}^{\rm{s}}}[0] + {\lambda ^{\rm{e}}}{{\rm{E}}^{\rm{e}}}[|{n^{(d)}}|] = {\lambda ^{\rm{e}}}{{\rm{E}}^{\rm{e}}}[|{n^{(d)}}|].$$
Hence,
$$\matrix{ {{{\rm{E}}^{\rm{e}}}[|n{|^{(d)}}]} \hfill & = \hfill & {\left( {{{{\rm{E}}{\kern 1pt} [{a_0}]} \over {{\rm{E}}{\kern 1pt} [{a_0}] - 1}}} \right){1 \over {{\rm{E}}{\kern 1pt} [{a_0}]}}{{\rm{E}}^{\rm{s}}}\left[ {\sum\limits_{n \in {{\tilde D}^{\rm{e}}}(0)} |n|} \right]} \hfill \cr {} \hfill & = \hfill & {{{{{\rm{E}}^{\rm{s}}}\left[ {\sum\nolimits_{n \in {{\tilde D}^{\rm{e}}}(0)} {|n|} } \right]} \over {{\rm{E}}{\kern 1pt} [{a_0}] - 1}}.} \hfill \cr } $$
4. Final remarks
When E [a 0] = ∞ the structure of the family random graph changes radically. A rich set of open questions for future research then arises, requiring different approaches to the ones used here. Proposition 3.3 still holds, and consequently the intensity of the point process of successful individuals is 0. Combined with the classification theorem of [Reference Baccelli, Haji-Mirsadeghi and Khezeli3], this implies that the connected component of 0 is of class I/I, namely, it is an eternal family tree with one end, in which all individuals have a finite lineage and an infinite number of cousins of all degrees.
Also, not only does E [Nn] = ∞, but also Nn = ∞ a.s. for all n ∊ ℤ. That E [Nn] = ∞ simply follows from Little’s law (Proposition 2.1). Moreover,
$${\rm{P}}{\kern 1pt} [{N_0} \le m] = {\rm{P}}\left[\bigcup\limits_{({q_1}, \ldots ,{q_{m - 1}}) \in {\mathbb {N}}{^{m - 1}}} \bigcap\limits_{j \notin ({q_1}, \ldots ,{q_{m - 1}})} \{ {a_{ - j}} \le j\} \right].$$
As E [a 0] = ∞, for any (q 1,..., qm −1) ∊ ℕm−1,
$$\prod\limits_{j \notin ({q_1}, \ldots ,{q_{m - 1}}) \in {\mathbb {N}}{^{m - 1}}} {\rm{P}}{\kern 1pt} [{a_{ - j}} \le j] = 0,$$
from which follows P [N 0 ≤ m] = 0. Hence, N 0 = ∞ a.s., which implies Nn = ∞ for all n ∊ ℤ.
The unimodular structure of Tf is preserved when E [a 0] =∞, and consequently the model remains critical, i.e. the expected value of the offspring cardinality of a typical individual is one. From [Reference Baccelli, Haji-Mirsadeghi and Khezeli3], it also follows that, despite d(n) < ∞ a.s. for all n ∊ ℤ, E[d(n)] = ∞. This result is obtained by applying the mass transport principle.
We conclude with a remark on the population dynamics interpretation of the model discussed in the core of this work, namely when E[a 0] < ∞. Our model is concerned with a dynamics in which the population is infinitely often close to extinction, as the original ancestor point process shows. In connection with this, we find it interesting to mention that there is some genetic and archaeological evidence that the human population was close to extinction several times in the distant past ([Reference Inglis-Arkell6] and [Reference Marean8]).
Appendix A. Section 2 proofs
Proposition A.1. The s.s.p.p. of original ancestors constructed in Theorem 2.1 is a renewal process.
Proof. Notice that, for all m,
$${{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_1^{\rm{o}} - k_0^{\rm{o}}) = m] = {\rm{P}}{\kern 1pt} [k_1^{\rm{o}} = m|k_0^{\rm{o}} = 0] = :{\kern 1pt} {y_m}.$$
Now, for any n ∊ ℤ, as θkn preserves PΨo,
$$\matrix{ {{{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{n + 1}^{\rm{o}} - k_n^{\rm{o}}) = m]} \hfill & = \hfill & {{{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{n + 1}^{\rm{o}} - k_n^{\rm{o}}) = m] \circ \theta _{k_n^{\rm{o}}}^{ - 1}} \hfill \cr {} \hfill & = \hfill & {{{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_1^{\rm{o}} - k_0^{\rm{o}}) = m] = {y_m}.} \hfill \cr } $$
Hence 
$${\{ k_{n + 1}^{\rm{o}} - k_n^{\rm{o}}\} _{n \in {\mathbb {Z}}}}$$ is identically distributed.
Now let i 0 < i 1 < i 2 < ··· < iq be a finite set of integers. Then, for m 0,..., mq ∊ ℕ,
$$\matrix{
{{{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{{i_0} + 1}^{\rm{o}} - k_{{i_0}}^{\rm{o}}) = {m_0},(k_{{i_2} + 1}^{\rm{o}} - k_{{i_2}}^{\rm{o}}) = {m_1}, \ldots ,(k_{{i_q} + 1}^{\rm{o}} - k_{{i_q}}^{\rm{o}}) = {m_q}]} \cr
{\quad = {{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{{i_0} - {i_q} + 1}^{\rm{o}} - k_{{i_0} - {i_q}}^{\rm{o}}) = {m_0},(k_{{i_1} - {i_q} + 1}^{\rm{o}} - k_{{i_1} - {i_q}}^{\rm{o}}) = {m_1}, \ldots ,k_1^{\rm{o}} = {m_q}].} \cr
} $$
Now, under PΨo the realization of 
$$k_1^{\rm{o}}$$ is a function of {an}n≥0, and for all i < 0, 
$$(k_i^{\rm{o}} - k_{i - 1}^{\rm{o}})$$ is a function of {an}n<0. Hence, as {an}n≥0 is independent of {an}n<0 (Lemma 2.2),
$$\matrix{
{{{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{{i_0} - {i_q} + 1}^{\rm{o}} - k_{{i_0} - {i_q}}^{\rm{o}}) = {m_0},(k_{{i_1} - {i_q} + 1}^{\rm{o}} - k_{{i_1} - {i_q}}^{\rm{o}}) = {m_1}, \ldots ,k_1^{\rm{o}} = {m_q}]} \hfill \cr
{\quad = {{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{{i_0} - {i_q} + 1}^{\rm{o}} - k_{{i_0} - {i_q}}^{\rm{o}}) = {m_0},(k_{{i_1} - {i_q} + 1}^{\rm{o}} - k_{{i_1} - {i_q}}^{\rm{o}}) = {m_1}, \ldots ,} \hfill \cr
{\quad \quad \quad \quad \quad (k_{{i_{q - 1}} - {i_q} + 1}^{\rm{o}} - k_{{i_{q - 1}} - {i_q}}^{\rm{o}}) = {m_{q - 1}}]{\kern 1pt} {{\rm{P}}_{{\Psi ^{\rm{o}}}}}[k_1^{\rm{o}} = {m_q}]} \hfill \cr
{\quad = {{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{{i_0} + 1}^{\rm{o}} - k_{{i_0}}^{\rm{o}}) = {m_0},(k_{{i_2} + 1}^{\rm{o}} - k_{{i_2}}^{\rm{o}}) = {m_1}, \ldots ,(k_{{i_{q - 1}} + 1}^{\rm{o}} - k_{{i_{q - 1}}}^{\rm{o}}) = {m_{q - 1}}]} \hfill \cr
{\quad \quad \quad \times {{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{{i_q} + 1}^{\rm{o}} - k_{{i_q}}^{\rm{o}}) = {m_q}].} \hfill \cr
} $$
By continuing to apply the same reasoning, we conclude that
$$\matrix{
{{{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{{i_0} + 1}^{\rm{o}} - k_{{i_0}}^{\rm{o}}) = {m_0},(k_{{i_2} + 1}^{\rm{o}} - k_{{i_2}}^{\rm{o}}) = {m_1}, \ldots ,(k_{{i_q} + 1}^{\rm{o}} - k_{{i_q}}^{\rm{o}}) = {m_q}]} \cr
{\quad = \prod\limits_{j = 0}^q {{\rm{P}}_{{\Psi ^{\rm{o}}}}}[(k_{{i_j} + 1}^{\rm{o}} - k_{{i_j}}^{\rm{o}}) = {m_j}].{\rm{ }}} \cr
} $$
Therefore, 
$${\{ k_{n + 1}^{\rm{o}} - k_n^{\rm{o}}\} _{n \in {\mathbb {Z}}}}$$ is also an independent sequence.
Proof of Proposition 2.1. Let Zn,m = 1{f(m)>n}. Notice that
$${N_n} = \sum\limits_{ - \infty \lt m \lt n} {Z_{n,m}} + 1.$$
For m ≤ 0, let Mm = ∑m<l<0 Z 0,l + 1, so limm→−∞ Mm = N 0 a.s. Then, as 
$${a_m}\mathop = \limits^{\rm{D}} {a_0}$$ for all m ∊ ℤ,
$$\matrix{
{{\rm{E}}[{M_m}]} \hfill & = \hfill & {\sum\limits_{m \le l \lt 0} {\rm{P}}[{a_{ - l}} \gt l] + 1} \hfill \cr
{} \hfill & = \hfill & {\sum\limits_{l = 1}^m {\rm{P}}[{a_0} \gt l] + \sum\limits_{l = 1}^m {\rm{P}}[{a_0} = l] + \sum\limits_{l \gt m} {\rm{P}}[{a_0} = l]} \hfill \cr
{} \hfill & = \hfill & {\sum\limits_{l = 1}^m {\rm{P}}[{a_0} \ge l] + \sum\limits_{l \gt m} {\rm{P}}[{a_0} = l].} \hfill \cr
} $$
Letting m → ∞, by monotone convergence we get E[N 0] = E[a 0].
Lemma A.1. Consider the infinite product 
$$\prod\nolimits_{i = 1}^\infty (1 \pm {b_i})$$, where bi ≥ 0 for all i. Then if 
$$\sum\nolimits_{i = 1}^\infty {b_i}$$ converges (resp. diverges to infinity), then 
$$\prod\nolimits_{i = 1}^\infty (1 \pm {b_i})$$ also converges to a non-negative number (resp. diverges).
For a proof, see e.g. [Reference Heinbockel4].
Proof of Proposition 2.2. Using (A.1), we can compute the moment-generating function of N 0 as follows. For t ∊ ℝ:
$$\matrix{ {{\rm{E}}[{{\rm{e}}^{t{N_0}}}]} \hfill & = \hfill & {{\rm{E}}[{{\rm{e}}^t}{{\rm{e}}^{t\sum\nolimits_{i = 1}^\infty {Z_{0, - i}}}}] = {{\rm{e}}^t}\prod\limits_{i = 1}^\infty {\rm{E}}[{{\rm{e}}^{t{Z_{0, - i}}}}]} \hfill \cr {} \hfill & = \hfill & {{{\rm{e}}^t}\prod\limits_{i = 1}^\infty ({{\rm{e}}^t}{\rm{P}}[{a_0} \gt i] + {\rm{P}}[{a_0} \le i]).} \hfill \cr } $$
Thus, 
$${\rm{E}}[{{\rm{e}}^{t{N_0}}}] = {{\rm{e}}^t}\prod\nolimits_{i = 1}^\infty ({b_i} + 1),$$, where bi = P[a 0 > i](et − 1). As E[a 0] < ∞, 
$$\sum\nolimits_{i = 1}^\infty {b_i} \lt \infty $$, and therefore by Lemma A.1, 
$${\rm{E}}[{{\rm{e}}^{t{N_0}}}] \lt \infty $$.
Appendix B. Dynamics on unimodular networks
We review the necessary concepts on unimodular networks dynamics used in this paper. We borrow the concepts of this section from [Reference Baccelli, Haji-Mirsadeghi and Khezeli3] and [Reference Aldous and Lyons1], which contain a more complete treatment of the subject.
Definition B.1. (Locally finite rooted networks.) A network is a quadruple (G, Ξ, u 1, u 2) where:
• G = (V, E) is a (multi-)graph;
• Ξ is a complete separable metric space;
• u 1 : V → Ξ (the element u 1(v) is called the mark of the vertex v);
• u 2 : {(v, e): v ∊ V, e ∊ E, v ∼ e} → Ξ (the element u 2(v, e) is called the mark of the pair (v, e)).
If G has a distinguished vertex, we call the network rooted. A network is locally finite if all its vertices have finite degrees. We also consider the case in which G has two distinguished vertices.
An isomorphism between graphs G and G ′ is a bijection that preserves the (direct) vertices. An isomorphism between rooted networks also preserves its marks and maps the distinguished vertex (or vertices) of G to G′.
Let 𝒢 * (resp. 𝒢 **) be the space of all isomorphism classes of locally finite rooted (resp. with two distinct vertices) networks and ℬ(𝒢 *) (resp. ℬ(𝒢 **)) its Borel-σ algebra. An element of 𝒢* (resp. 𝒢 **) is denoted by [G, o] (resp. [G, o, o′]). We denote the set of vertices of any representative of the isomorphism class [G, o](or [G, o, o′]) by V.
A random rooted (resp. with two distinct vertices) network is a measurable mapping from a general probability space (Ω, ℱ, P) to (𝒢 *, ℬ(𝒢 *)) (resp. (𝒢 **, ℬ(𝒢 *))). We denote a random network by [G, o] (resp. [G, o, o′]).
A locally finite network is unimodular if for all measurable functions g : 𝒢 ** → ℝ≥:
$${\rm{E}}\left[\sum\limits_{v \in V} g[{\bf{G}},{\bf{o}},v]\right] = {\rm{E}}\left[\sum\limits_{v \in V} g[{\bf{G}},v,{\bf{o}}]\right].$$
This definition does not depend on the choice of representative of [G, o, v].
Definition B.2. A covariant vertex-shift is a map XG which associates with each unimodular network a function xG : V → V such that
• xG is covariant under isomorphisms and
• the function [G, o, o′] → 1{xG(o) = o } is measurable on 𝒢 **.
From vertex-shift XG acting on [G, o, o′] we let GX = (VX, EX) be the graph such that VX = V and EX = {v, xG(v)}v ∊V. We then define the following subsets of VX.
Definition B.3. (Connected component.) The connected component of v under the action of vertex-shift xG is given by
$$C(v) = \{ w \in V \,{\rm{s.t.}}\, \exists \; i,\, j \in {\mathbb {N}}\; {\rm{with}} \, x_G^j(v) = x_G^j(w)\} .$$
Definition B.4. (Foil.)The foil of v is defined as
$$L(v) = \{ w \in V \;{\rm{ s.t.}} \; \exists \, j \in {\mathbb {N}} \;{\rm{with}}\; x_G^j(w) = x_G^j(v)\} .$$
We let c(v) (resp. l(v)) denote the cardinality of C(v) (resp. L(v)). In [Reference Baccelli, Haji-Mirsadeghi and Khezeli3], it is shown that each connected component of GX, in particular C(o), falls within one of the following categories:
Class F/F: c(o) < ∞ and for all v ∊ C(o), l(v) < ∞.
Class I/F: c(o) =∞ and for all v ∊ C(o), l(v) < ∞.
Class I/I: c(o) =∞ and for all v ∊ C(o), l(v) =∞.
Acknowledgements
This work was supported by a grant of the Simons Foundations (#197982 to the University of Texas at Austin). The authors would like to thank James Murphy III as well as the anonymous reviewers for their very valuable comments on this work.
