In this section we study a class of graphs that generalize the graph in the classical remaining life Markov chain. We start with a discrete rooted tree \((S, \upa)\) with root \(e\). The graph \((S, \upa)\) is the covering graph of a partial order graph \((S, \preceq)\), as discussed in Section 1, but now we are interested in a different graph that can be constructed from the tree. To review the notation, let \(S_+ = S - \{e\}\) and for \(x \in S_+\), let \(x^-\) denote the parent of \(x\) in the tree, so that \(x^- \upa x\) (and is the unique such element). For \(x \in S\), recall that \(d(x)\) denotes the distance from \(e\) to \(x\) in \((S, \preceq)\), that is, the length of the (unique) path in \((S, \upa)\) from \(e\) to \(x\).
For \(n \in \N\) let \(\beta_n = \#\{x \in S: d(x) = n\}\). Let \(\varphi\) denote the power series \(\varphi(t) = \sum_{n = 0}^\infty \beta_n t^{n + 1}\) for \(t \in [0, \infty)\).
Of coure \(\beta_0 = 1\). In general, the sequence \((\beta_n: n \in \N)\) and the generating function \(\varphi\) will play a fundamental role in our analysis. Here is our main definition.
The downward run graph \((S, \rta)\) associated with the tree \((S, \upa)\) is defined by \(x \rta x^-\) for \(x \in S_+\) and \(e \rta x\) for every \(x \in S\).
We will refer to the downward run graph \((\N, \rta)\) associated with \((\N, \upa)\), the covering graph of \((\N, \le)\), as the standard downward run graph. This is the graph of the classical remaining life Markov chain, which in turn is the time-reversal of the success-runs chain. Generalizations of success runs graphs will be studied in Section 6. For the remiander of this section, we assume that \((S, \rta)\) is the downward run graph associated with a rooted tree \((S, \upa)\) with at least two elements. A path in \((S, \rta)\) moves successivley down the tree from the starting point, and then if the path hits \(e\), the next state can be any element of \(S\), including \(e\). The path functions are complicated except in some special cases.
Suppose that \((S, \upa)\) is the regular rooted tree of degree \(k \in \N_+\), as described in Section 1. The path function \(\gamma_n\) of length \(n \in \N\) for the downward run graph \((S, \rta)\) is given by \(\gamma_n(x) = (k + 1)^n\) for \(x \in \N\).
There is an easy combinatorial proof. A path of length \(n \in \N\) terminating in \(x \in S\) for the graph \((S, \rta)\) has \(n + 1\) vertices. The last one by definition is \(x\). If \(y\) is a vertex in the path that is not the inital vertex, there are \(k + 1\) choices for the previous vertex, namely one of the \(k\) children of \(y\) or the root \(e\). Hence to construct the path we have \(k + 1\) choices for each of \(n\) vertices.
In particular, for the standard downward run graph \((\N, \rta)\), we have \(\gamma_n(x) = 2^n\) for \(n \in \N\) and \(x \in \N\).
Consider the general downward run graph \((S, \rta)\). Suppose that \(x \in S\) with \(d(x) = k \in \N\). For every one of the \(2^n\) paths \(k_1 \rta k_2 \rta \cdots \rta k_n \rta k\) of length \(n \in \N\) that terminate in \(k\) in the standard downward run graph \((\N, \rta)\), there are \(\beta_{k_1} \beta_{k_2} \cdots \beta_{k_n}\) paths in \((S, \rta)\) of length \(n\) terminating in \(x\).
Let \(L\) denote the set of leaves (vertices without children) in the rooted tree \((S, \upa)\). The \(\sigma\)-algebra associated with the downward run graph \((S, \rta)\) is \(\ms P(L^c) \cup \{L, \emptyset\}\).
The (right) neighbor set of \(x \in S_+\) for the graph \((S, \rta)\) is \(\{x^-\}\), the singleton set with the parent of \(x\). If \(x \in S_+\) then \(x^- \in L^c\). The neighbor set of the root \(e\) is \(S\) (which belongs to every \(\sigma\)-algebra of subsets of \(S\)). So the \(\sigma\)-algebra \(\ms A\) associated with \((S, \rta)\) is \(\sigma\{\{x^-\}: x \in S_+\} = \sigma\{\{x\}: x \in L^c\} = \ms P(L^c) \cup \{L, \emptyset\}\).
In particular, if \((S, \upa)\) has no leaves or a single leaf, then the \(\sigma\)-algebra associated with \((S, \rta)\) is the reference \(\sigma\)-algebra \(\ms P(S)\). But if \((S, \upa)\) has two or more leaves then the associated \(\sigma\)-algebra is a proper subset of \(\ms P(S)\).
Once again, we have a downward run graph \((S, \rta)\) associated with a rooted tree \((S, \upa)\) that has a set of leaves \(L\) (possibly empty).
The graph \((S, \rta)\) is stochastic. That is, a probability measure \(P\) on the associated \(\sigma\)-algebra \(\ms P(L^c) \cup \{L, \emptyset\}\) is uniquely determined by the reliability function \(F\) of \(P\) for \((S, \rta)\).
From it follows that we must show that \(P(\{x\})\) can be computed from \(F\) for \(x \in L^c\) and that \(P(L)\) can be computed from \(F\). If \(x \in L^c\) then \(x\) has a child, so select a particular child \(x^+\). Then by definition, \(F(x^+) = P(\{x\})\). But then also, \(P(L) = 1 - \sum_{x \in L^c} F(x^+)\).
But if the tree has two or more leaves, then the reliability function \(F\) of a probability measure \(P\) on the reference \(\sigma\)-algebra \(\ms P(S)\) does not uniquely determine \(P\). Specifically we cannot determine \(P(\{x\})\) individually for \(x \in L\), but only \(P(L)\) in total. Let us restate the baisc facts in terms of a random variable \(X\) relative to the standard reference space \((S, \ms P(S), \#)\) and defined on an underlying probability space \((\Omega, \ms F, \P)\). Let \(f\) denote the density function so that \(f(x) = \P(X = x)\) for \(x \in S\). We impose our usual support assumption so that \(f(x) \gt 0\) for \(x \in S\).
For \((S, \rta)\),
The next proposition is the main result on constant rate distributions for downward run graphs. The power series \(\varphi\) defined in will play an important role.
If \(\varphi\) has positive radius of convergence then \((S, \rta)\) has a unique distribution with constant rate \(\alpha \in (0, 1)\) satisfying \(\varphi(\alpha) = 1\). If \(X\) has this distribution then
If \(\varphi\) has radius of convergence 0 then \((S, \rta)\) has no constant rate distribution.
To have constant rate \(\alpha\), \(f\) must satisfy \(f(e) = \alpha\) and \(f(x) = \alpha f(x^-)\) for \(x \in S_+\). So \(\alpha \in (0, 1)\) and \(f(x) = \alpha^{d(x) + 1}\) for \(x \in S\). But we must have \[\sum_{x \in S} f(x) = \sum_{n = 0}^\infty \sum_{d(x) = n} \alpha^{n + 1} = \sum_{n = 0}^\infty \beta_n \alpha^{n + 1} = \varphi(\alpha) = 1\] Let \(\rho\) denote the radius of convergence of \(\varphi\). If \(\rho = 0\) there is no constant rate distribution. If \(\rho \gt 0\) then \(\varphi\) is continuous and increasing on the interval \([0, \rho)\) and satisfies \(\varphi(0) = 0\) and \(\lim_{t \to \rho} \varphi(t) = \infty\). So there exists a unique \(\alpha \in (0, \rho)\) with \(\varphi(\alpha) = 1\). Since \(\varphi(1) = \#(S) \gt 1\) we must have \(\alpha \in (0, 1)\).
So if \(\beta_n = \infty\) for some \(n \in \N_+\) (that is, some vertex has infinitely many children) or if \(\beta_n\) grows too fast with \(n\) then \((S, \rta)\) has no constant rate distribution. For example, a downward run graph with \(\beta_n = n!\) for \(n \in \N\) has no constant rate distribution. On the other hand, the downward run graph corresponding to a finite rooted tree always has a unique constant rate distribution. But of course, we already knew that since every finite, strongly connected graph has a unique constant rate distribution. The next subsection gives a few other examples.
Suppose that \((S, \rta)\) is the downward run graph corresponding to the (infinite) regular rooted tree of degree \(k \in \N_+\). Then \((S, \rta)\) has the unique constant rate distribution with rate \(\alpha = 1 / (k + 1)\). If \(X\) has constant rate then
The results follow from . Note that \(\beta_n = k^n\) for \(n \in \N\) so \(\varphi(t) = \sum_{n = 0}^\infty k^n t^{n + 1} = k / (1 - k t)\) for \(|t| \lt 1 / k\). Hence the rate constant \(\alpha\) satisfies \(k / (1 - \alpha k) = 1\) so \(\alpha = 1 / (k + 1)\).
In particular, the unique constant rate distribution for the standard downward run graph \((\N, \rta)\) is the geometric distribution on \(\N\) with parameter \(1/2\) and so with density function \(f\) given by \[f(x) = \left(\frac 1 2\right)^{x + 1}, \quad x \in \N\]
For the next several exercises, we consider the downward run graph \((S, \rta)\) associated with the finite regular rooted tree \((S, \upa)\) of degree \(k \in \N_+\) and height \(m \in \N_+\). Suppose that \(X\) has the unique constant rate distribution for \((S, \rta)\), with rate \(\alpha \in (0, 1)\). Since we know that \(X\) has density function \(f\) given by \(f(x) = \alpha^{d(x) + 1}\) for \(x \in S\), we concentrate on properties of \(\alpha\) and \(d(X)\). A critical relationship between the parameters \(k\) and \(m\) plays an important role. Recall that \(\N_m = \{0, 1, \ldots, m\}\).
Suppose that \(k = m + 1\). Then
Suppose that \(k \lt m + 1\). Then
Suppose that \(k \gt m + 1\). Then
In the special case that \(m = 1\) the underlying tree is a rooted star
and then the downward run graph is the ordinary undirected star with the addition of a loop at the center \(e\). This case is interesting because, as we will see in Section 5, the corresponding downward and upward graphs are the same.
Suppose that \(m = 1\) and \(k \in \N_+\). Then \(X\) has rate \[\alpha = \frac{\sqrt{4 k + 1} - 1}{2 k}\]
In the special case that \(k = 1\) the underlying tree is a finite directed path. As described in Section 1, we can let \(S = \N_m\) with root 0 and \(d(x) = x\) for \(x \in \N_m\). This case gives a corollary to
Suppose that \(k = 1\) and \(m \in \N_+\). Then
For \(m \in \N_+\), let \((S_m, \upa)\) denote the rooted binomial tree of order \(m\), as described in Section 1. Suppose that \(X\) has the unique constant rate distribution for the downward run graph \((S, \rta)\).
The results follow from and from basic properties of binomial trees in Section 1.
So this result gives new meaning to the term binomial tree.
Once again, we have a rooted tree \((S, \upa)\) and the corresponding downward run graph \((S, \rta)\). Recall also that \((S, \upa)\) is the covering graph for the partial order graph \((S, \preceq)\).
Suppose again that \(X\) has density function \(f\). The random walk \(\bs{Y} = (Y_1, Y_2, \ldots)\) on \((S, \rta)\) associated with \(X\) has transition probability function \(P\) given by \begin{align*} P(x, x^-) &= 1, \quad x \in S_+\\ P(e, x) &= f(x), \quad x \in S \end{align*}
In the case of the standard downward run graph, \(\bs Y\) is a downward run Markov chain in the usual elementary formulation, with lifetime distribution \(f\).
Consider again the random walk \(\bs{Y}\) on \((S, \rta)\) associated with \(X\).
Note that \(g\) and \(1 + m\) are the density function and mean, respectively, of \(d(X) + 1\), which is the return time to \(e\), starting at \(e\) for the chain \(\bs Y\). It's interesting that the reliability function for the partial order graph \((S, \preceq)\) plays a fundamental role in the analysis of the random walk on the downward run graph \((S, \rta)\). In particular, the special case where \(X\) has constant rate for \((S, \preceq)\) is interesting. Recall that the constant rate distributions for \((S, \preceq)\) were characterized in Section 2.
Suppose that \(X\) has constant rate for \((S, \preceq)\). The random walk \(\bs Y\) on \((S, \rta)\) associated with \(X\) is positive recurrent and the density function \(f\) of \(X\) is also the density function of the invariant distribution of \(\bs Y\).
Suppose that \(X\) has constant rate \(\alpha \in (0, 1)\) for \((S, \preceq)\). From , the reliability function \(G\) of \(X\) for \((S, \preceq)\) is invariant for \(\bs Y\). But \(f = \alpha G\) so \(f\) is also invariant for \(\bs Y\). Recall also from Section 2, that \(d(X)\) has the geometric distribution with parameter \(\alpha\). and hence \(\E[d(X)] = 1 / (1 - \alpha) \lt \infty\).
The following result gives a recursive scheme for computing the density function of the random walk variables in the case of the standard remaining life graph \((\N, \rta)\), that is, the remaining life graph associated with the covering tree \((\N, \upa)\) of \((\N, \le)\).
Consider the random walk \(\bs{Y} = (Y_1, Y_2, \ldots)\) on \((\N, \rta)\). associated with random variable \(X\). Let \(f\) denote the density function of \(X\) and \(f_n\) the density function of \(Y_n\) for \(n \in \N_+\). Then recursively for \(n \in \N\), \[f_{n + 1}(x) = \sum_{k = 0}^{n - 1} f(k) f_{n - k}(x) + f(x + n), \quad x \in \N\]
Fix \(n \in \N_+\). Note that a path \(\bs x = (x_1, x_2, \ldots, x_n)\) of length \(n\) in \((\N, \rta)\) must start with a subsequence decreasing by 1 from term to term, perhaps to 0, and if so, followed by another subsequence of the same form, and so forth. Now let \(k \in \N\) denote the number of times 0 occurs in \(\bs x\). Then let \(j_1 = 1\) and \(j_i\) the index following the \(i\)th 0 for \(i \in \{1, 2, \ldots, k\}\). Then the probability density function of \((Y_1, Y_2, \ldots, Y_n)\) at \(\bs x\) has the form
\[f(x_{j_1}) f(x_{j_2}) \cdots f(x_{j_k})\]
This makes sense. The only source of randomness in the sequence \(\bs Y\) are the rebirth
terms following the \(0\)s. For the density function \(f_n\) of \(Y_n\), we use the general formula \(f_n(x) = v_{n-1}(x) f(x)\) for \(y \in \N\). This leads to the following, each for \(x \in \N\):
\begin{align*}
f_1(x) &= f(x)\\
f_2(x) &= f(0) f(x) + f(x + 1)\\
f_3(x) &= f^2(0) f(x) + f(0) f(x + 1) + f(1) f(x) + f(x + 2)\\
\end{align*}
The next term is
\begin{align*}
f_4(x) = & f^3(0) f(x) + f^2(0) f(x + 1) + f(0) f(x + 2) + f(0) f(1) f(x) \\
& + f(1) f(0) f(x) + f(1) f(x + 1) + f(2) f(x) + f(x + 3)
\end{align*}
In general, \(f_n(x)\) has \(2^{n - 1}\) terms, one for each of the \(2^{n - 1}\) paths of length \(n - 1\) in \((\N, \rta)\) terminating in \(x\). Recursively, for \(n \in \N\), we have the formula in the proposition.
Open the simulation of the remaining life chain. In this app, \(X\) has the geometric distribution with parameter \(1 - p\) which is also the invariant density function. Vary \(p\) with the scrollbar and note the shape of the density function. For selected values of \(p\), run the simulation 1000 times and compare the empirical density function to the limiting density function.