For \(n \in \N\) and \(x \in S\), let \(\beta_n(x) = \#\{y \in S: d(x, y) = n\}\).

The upward run graph \((S, \rta)\) associated with the rooted tree \((S, \upa)\) is defined by \(x \rta y\) if and only if \(x \upa y\) or \(y = e\), for \(x, \, y \in S\).

Suppose that \((S, \upa)\) is an infinte tree and let \(u_n\) denote the left walk function of \((S, \rta)\) of order \(n \in \N_+\). Then

1. \(u_n(e) = \infty\).
2. \(u_n(x) = 1\) for \(x \in S_+\) and \(n \le d(x)\).
3. \(u_n(x) = \infty\) for \(x \in S_+\) and \(n \gt d(x)\).

Let \(A_x = \{y \in S: x \upa y\}\), the set of children of \(x \in S\) for the tree \((S, \upa)\), and let \(\ms A\) denote the collection of subsets of \(S\) that consists of \(\{e\}\) and \(A_x\) for \(x \in S\). Then the (right) \(\sigma\)-algebra associated with the upward run graph \((S, \rta)\) is \(\sigma(\ms A)\), the collection of all unions of sets in \(\ms A\).

The graph \((S, \rta)\) is (right) stochastic. That is, a probability measure \(P\) on the associated \(\sigma\)-algebra \(\sigma(\ms A)\) is uniquely determined by the reliability funciton \(F\) of \(P\) for \((S, \rta)\).

For the graph \((S, \rta)\),

1. The reliability function \(F\) of \(X\) is given by \[F(x) = f(e) + \sum_{x \upa y} f(y) \quad x \in S\]
2. The rate function \(r\) of \(X\) is given by \[r(x) = \frac{f(x)}{f(e) + \sum_{x \upa y} f(y)}, \quad x \in S\]
3. \(F\) uniquely determines \(f\) only when \((S, \upa)\) is a directed path.

A function \(F: S \to [0, 1]\) is a reliability function for \((S, \rta)\) if and only if there exists \(p \in (0, 1)\) such that

1. \(F(x) \ge p\) for all \(x \in S\).
2. \(F(x) = p\) if \(x \in S\) is a leaf of \((S, \upa)\).
3. \(\sum_{x \in S} [F(x) - p] = 1 - p\)

In this case, a density function \(f\) with reliability function \(F\) for \((S, \rta)\) can be constructed as follows:

3. Let \(f(e) = p\).
4. For \(x \in S\), define \(f(y) \in (0, 1)\) arbitrarily subject to \(\sum_{x \upa y} f(y) = F(x) - p\)

Suppose that \((S, \upa)\) is a finite rooted tree. For \(x \in S\) and \(t \in (0, 1)\), define \[\varphi(x, t) = \sum_{k = 0}^{n(x)} \beta_k(x) t^{k + 1}\]

Suppose that \((S, \upa)\) is a finite rooted tree. For the unique constant rate distribution on the upward run graph \((S, \rta)\),

1. The rate constant \(\alpha \in (0, 1)\) satisfies \( \varphi(e, \alpha) = 1\).
2. The probability density function \(f\) is given by \(f(x) = \varphi(x, \alpha) / c\) for \(x \in S\) where \(c\) is the normalizing constant \( c = \sum_{x \in S} \varphi(x, \alpha) \).

For \(x \in S\), the subtree \((S_x, \upa)\) is also a regular rooted tree of degree \(k\) but with root \(x\) and height \(m - d(x)\). Hence

1. \(\beta_j(x) = k^j\) for \(x \in S\) and \(j \in \{0, 1, \ldots d(x)\}\)
2. \(\varphi(x, t) = \sum_{j = 0}^{d(x)} k^j t^{j + 1} \) for \(x \in S\) and \(t \in [0, \infty)\).
3. The density function \(f\) of \(X\) satisfies \(f(x) = f(y)\) for \(x, \, y \in S\) with \(d(x) = d(y)\).
4. The density function \(g\) of \(d(X)\) is given by \(g(n) = k^n f_n\) for \(n \in \N_m\) where \(f_n\) is the common value of \(f(x)\) when \(d(x) = n\).

Suppose that \(k = m + 1\). Then

1. \(X\) has rate \(\alpha = 1 / k = 1 / (m + 1)\).
2. \(X\) has density function \(f\) given by \[f(x) = \frac{m + 1 - d(x)}{(m + 1)^m - 1} \left(\frac{m}{m + 1}\right)^2, \quad x \in S\]
3. \(d(X)\) has density function \(g\) given by \[g(n) = (m + 1)^n \frac{m + 1 - n}{(m + 1)^m - 1} \left(\frac{m}{m + 1}\right)^2, \quad n \in \N_m \]

Suppose that \(1 \lt k \lt m + 1\). Then

1. \(X\) has rate \(\alpha \in (0, 1 / k)\) satisfying \(k^{m + 1} \alpha^{m + 2} - (k + 1) \alpha + 1 = 0\).
2. \(X\) has density function \(f\) given by \(f(x) = \left[1 - (k \alpha)^{m - d(x) + 1}\right] / C\) for \(x \in S\) where \(C\) is the normalizing constant. \[C = \frac{k^{m + 1} - 1}{k - 1} - k^{m + 1} \alpha \frac{1 - \alpha^{m + 1}}{1 - \alpha} - \]

Suppose that \(k \gt m + 1\). Then

1. \(X\) has rate \(\alpha \in (1 / k, 1)\) satisfying \(k^{m + 1} \alpha^{m + 2} - (k + 1) \alpha + 1 = 0\).
2. \(X\) has density function \(f\) given by \(f(x) = \left[(k \alpha)^{m - d(x) + 1} - 1 \right] / C\) for \(x \in S\) where \(C\) is the normalizing constant. \[C = k^{m + 1} \alpha \frac{1 - \alpha^{m + 1}}{1 - \alpha} - \frac{k^{m + 1} - 1}{k - 1} \]

Suppose that \(k = 1\). Then

1. \(X\) has rate constant \(\alpha \in (0, 1)\) where \(\alpha^{m + 2} - 2 \alpha + 1 = 0\).
2. \(X\) has probability density function \(f\) given by \[ f(x) = \frac{1 - \alpha^{m - x + 1}}{m}, \quad x \in \N_m \]
3. \(\alpha \to \frac 1 2\) as \(m \to \infty\).

Suppose that \((S, \upa)\) is the regular rooted tree of degree \(k \in \N_+\) and height 1 and that \(X\) has the unique constant rate distribution for the corresponding upward run graph \((S, \rta)\). Then

1. \(X\) has rate \[\alpha = \frac{\sqrt{4 k + 1} - 1}{2 k}\]
2. The probability density function \(f\) is given by \(f(e) = \alpha\) and \(f(x) = \alpha^2\) for \(x \in S_+\).

Suppose that \(X\) has the geometric distribution on \(\N\) with success parameter \(p\), so that \(X\) has density function \(f\) given by \(f(x) = p (1 - p)^x\) for \(x \in \N\). The rate function \(r\) of \(X\) for \((\N, \rta)\) reduces to \[r(x) = \frac{(1 - p)^x}{1 + (1 - p)^{x + 1}}, \quad x \in \N\] So \(r(x)\) decreases to \(0\) as \(x\) increases to \(\infty\).

For \(m \in \N_+\), let \((S, \upa)\) be the binomial tree of order \(m\), and let \(o(x)\) denote the order of the binomial subtree \((S_x, \upa)\) for \(x \in S\). Suppose that \(X\) has the unique constant rate distribution on the upward run graph \((S, \rta)\). Then

1. \(X\) has rate constant \(\alpha \in (0, 1)\) where \(\alpha (1 + \alpha)^m = 1\).
2. \(X\) has probability density function \(f\) given by \[ f(x) = \frac{(1 - \alpha)(1 + \alpha)^{o(x)}}{2^m - 1}, \quad x \in S \]
3. \(N = o(X)\) has probability density funcntion \(g\) given by \[g(k) = \frac{2^{m - 1 - k}}{2^m - 1} (1 - \alpha)^m (1 + \alpha)^k, \quad k \in \{0, 1, \ldots, m\}\]
4. \(\alpha \to 0\) as \(m \to \infty\).

Let \(\bs{Y} = (Y_1, Y_2, \ldots)\) denote the random walk on \((S, \rta)\) associated with \(X\). The transition probability function \(P\) of \(\bs Y\) is given by \[P(x, y) = \frac{f(y)}{f(e) + \sum_{x \upa z}f(z)}, \quad x \upa y \text{ or } y = e\]

For the random walk \(\bs Y\),

1. Let \(T_e\ = \min\{n \in \N_+: Y_n = e\}\) denote the hitting time to \(c\)
2. Let \(G: S \to (0, 1) \) be the function defined as follows: \(G(e) = 1\). If \(x \in S_+\) and \(e \upa x_1 \upa x_2 \upa \cdots \upa x_{n - 1} \upa x \) is the unique path in \((S, \upa)\) from \(e\) to \(x\) (so that \(d(x) = n \in \N_+)\) then \[G(x) = P(e, x_1) P(x_1, x_2) \cdots P(x_{n - 1}, x)\]

Properties of \(G\).

1. \(\P(T_e \gt n \mid Y_0 = e) = \sum_{d(x) = n} G(x)\) for \(n \in \N\)
2. \(\E(T_e \mid Y_0 = e) = \sum_{x \in S} G(x)\)
3. \(\bs Y\) is recurrent if and only if \(\sum_{d(x) = n} G(x) \to 0\) as \(n \to \infty\).
4. In the recurrent case, \(G\) is invariant for \(\bs Y\).
5. \(\bs Y\) is positive recurrent if and only if \(\sum_{x \in S} G(x) \lt \infty\).

Suppose that \(\bs Y\) is the random walk on \((S, \rta)\) associated with random variable \(X\). Let \(a_n = \beta_n(e) / [1 + f(e)]^n\) where \(f\) is the density function of \(X\).

1. If \(a_n \to 0\) as \(n \to \infty\) then \(\bs Y\) is reccurrent.
2. If \(\sum_{n = 0}^\infty a_n \lt \infty\) then \(\bs Y\) is positive recurrent.

Consider the random walk \(\bs Y\) on \((\N, \rta)\) with transition probability function \(P\) given by \[P(x, x + 1) = a(x), \; P(x, 0) = 1 - a(x), \quad x \in \N\] where \(a: \N \to (0, 1)\). Then \(\bs Y\) is associated with a probability density function \(f\) on \(\N\) if and only if \[c := \sum_{x = 0}^\infty \frac{a(x)}{1 - a(x)} \lt \infty\] in which case \(f\) is given by \[f(0) = \frac{1}{1 + c}, \quad f(x + 1) = \frac{a(x)}{(1 + c)[1 - a(x)]}, \; x \in \N\]

The apps below simulate the standard success-runs chain with parameter \(p\) and the standard remaining-life chain with paramter \(p\). These chains are time reversals of each other.