\(\newcommand{\P}{\mathbb{P}}\) \(\newcommand{\E}{\mathbb{E}}\) \(\newcommand{\R}{\mathbb{R}}\) \(\newcommand{\N}{\mathbb{N}}\) \(\newcommand{\ms}{\mathscr}\) \(\newcommand{\bs}{\boldsymbol}\) \(\newcommand{\rta}{\rightarrow}\) \(\newcommand{\lfa}{\leftarrow}\) \(\newcommand{\upa}{\uparrow}\)
  1. Reliability
  2. 5. Rooted Trees and Related Spaces
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5
  8. 6

6. Upward Run Graphs

Preliminaries

This section studies a class of graphs that generalize the graph in the classical success-runs Markov chain, and are complementary to the downward run graphs in Section 5. 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\}\). For \(x, \, y \in S\) with \(x \preceq y\), let \(d(x, y)\) denote the distrance from \(x\) to \(y\) in \((S, \preceq)\), that is, the length of the unique path in \((S, \upa)\) from \(x\) to \(y\). Finally, for \(x \in S\), let \((S_x, \upa)\) denotes the subtee of \((S, \upa)\) rooted at \(x\) and let \(n(x)\) denote the height of \((S_x, \upa)\).

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

So \(\beta_n(x)\) is the number of vertices at distance \(n\) from \(x\) in the subtree \((S_x, \upa)\), and in particular, \(\beta_0(x) = 1\).

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\).

So a path in \((S, \rta)\) moves successively up the tree at each step, or back to the root \(e\). The upward run graph \((\N, \rta)\) associated with the standard tree \((\N, \upa)\) (the covering graph of \((\N, \le))\) is the leads to relation in the classical success-runs Markov chain. Generally, the upward run graph \((S, \rta)\) associated with a rooted tree is the inverse of the downward run graph associated with the tree, as studied in Section 5.

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

  1. \(\gamma_n(e) = \infty\).
  2. \(\gamma_n(x) = 1\) for \(x \in S_+\) and \(n \le d(x)\).
  3. \(\gamma_n(x) = \infty\) for \(x \in S_+\) and \(n \gt d(x)\).
Details:
  1. This follows since \(S\) is infinite and \(x \rta e\) for every \(x \in S\).
  2. If \(x \in S_+\) and \(n \le d(x)\) then the only path of length \(n\) terminating in \(x\) is the portion of the unique path from \(e\) to \(x\).
  3. If \(x \in S_+\) and \(n \gt d(x)\) then there are infinitely many paths of length \(n - d(x)\) terminating in \(e\) and each of these can be appended by the path of length \(d(x)\) from \(e\) to \(x\).

The path functions for the upward run graph corresponding to a finite tree is generally complicated, but can be computed in some special cases.

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 \(\sigma\)-algebra associated with the upward run graph \((S, \rta)\) is \(\sigma(\ms A)\), the collection of all unions of sets in \(\ms A\).

Details:

The collection of subsets \(\{A_x: x \in S\}\) partitions \(S_+\). The (right) neighbor set of \(x \in S\) for \((S, \rta)\) is \(B_x = A_x \cup \{e\}\). If \(x, \, y \in S\) are distinct then \(B_x \cap B_y = \{e\}\) and \(A_x = B_x - \{e\}\). So the \(\sigma\)-algebra associated with \((S, \rta)\) is \(\sigma\{B_x: x \in S\} = \sigma(\ms A)\). The collection \(\ms A\) partitions \(S\) and so \(\sigma(\ms A)\) consists of all unions of sets in \(\ms A\).

So \(\sigma(\ms A)\), the \(\sigma\)-algebra associated with \((S, \rta)\), is the same as the \(\sigma\)-algebra associated wiht the tree \((S, \upa)\). Unless \((S, \upa)\) is a directed path, \(\sigma(\ms A)\) is a proper subset of the reference \(\sigma\)-algebra \(\ms P(S)\).

Probability

Once again we have the upward run graph \((S, \rta)\) associated with the rooted tree \((S, \upa)\).

The graph \((S, \rta)\) is 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)\).

Details:

From , note that \(F(x) = P(\{e\}) + P(A_x)\) for \(x \in S\). Since \(\ms A\) partitions \(S\) and \(\sigma(\ms A)\) consists of all unions of sets in \(\ms A\), it suffices to show that \(P(\{e\})\) and \(P(A_x)\) for \(x \in S\) can be written in terms of \(F\). If \((S, \upa)\) has a leaf \(l\) then \(P(\{e\}) = F(l)\) and then also \(P(A_x) = F(x) - F(l)\) for \(x \in S\). If \((S, \upa)\) has no leaves, let \(\{x_n: n \in \N_+\}\) be a set of distinct points. Since \(\sum_{x \in S} P(A_x) = P(S_+) \le 1\) it follows that \(\sum_{n = 1}^\infty P\left(A_{x_n}\right) \le 1\) and therefore \(\lim_{n \to \infty} P\left(A_{x_n}\right) = 0\). Hence \(\lim_{n \to \infty} F(x_n) = P(\{e\})\) and then \[P(A_x) = F(x) - \lim_{n \to \infty} F(x_n), \quad x \in S\]

Suppose now that \(X\) is a random variable relative to our standard reference space \((S, \ms P(S), \#)\), with probability density function \(f\) so that \(f(x) = \P(X = x)\) for \(x \in S\). We assume that \(f(x) \gt 0\) for \(x \in S\).

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.
Details:

Parts (a) and (b) follow from the definition of the upward run graph. Part (c) is a consequence of and .

It's easy to characterize reliability functions for \((S, \rta)\).

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:

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

Suppose that \(F\) satisfies (a)—(c) and that \(f\) is defined by (d) and (e). Then \(f(x) \ge 0\) for \(x \in S\) and \[\sum_{x \in S} f(x) = f(e) + \sum_{x \in S_+} f(x) = f(e) + \sum_{x \in S} \sum_{x \upa y} f(y) = p + \sum_{x in S} [F(x) - p] = p + (1 - p) = 1\] So \(f\) is a probability density function. Also \[f(e) + \sum_{x \upa y} f(y) = p + [F(x) - p] = F(x), \quad x \in S\] so the reliability function of \(f\) for \((S, \rta)\) is \(F\).

Once again we see that unless \((S, \upa)\) is a path, \(F\) does not determine \(f\) uniquely. As always, we are particularly interested in the existence of constant rate distributions. If \((S, \upa)\) is an infinite tree then as a consequence of , there are no constant rate distributions for the upward run graph \((S, \rta)\). On the other hand, if \((S, \upa)\) is a finite tree then \((S, \rta)\) is a finite, stongly connected graph and hence has a unique constant rate distribution. Interestingly, the rate constant is the same as for the corresponding downward run graph, but the constant rate distributions for the upward and downward run graphs are generally quite different. To state the result succinctly, some additional notation will help, extending the notation in Section 5.

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}\]

So for fixed \(x \in S\) the function \(t \mapsto \varphi_k(x, t)\) is the ordinary generating function of the sequence \((\beta_k(x): k \in \{0, 1, \ldots, n(x)\})\).

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) \).
Details:

By definition, the density function \(f\) of the distribution with constant rate \(\alpha \in (0, 1)\) satisfies \(f(x) = \alpha f(e) + \alpha \sum_{x \upa y} f(y)\) for \(x \in S\). Using this result recursivley gives \(f(x) = \varphi(x, \alpha) f(e)\) for \(x \in S\). In particular, with \(x = e\) we have \(f(e) = \varphi(e, \alpha) f(e)\) and hence \(\alpha\) is the unique solution of the equation \(\varphi(e, \alpha) = 1\) in the interval \((0, 1)\). The condition \(\sum_{x \in S} f(x) = 1\) then gives \(f(e) = 1 / c\) for \(c\) given in the proposition, and then more generally, \(f(x) = \varphi(x, \alpha) / c\).

Note that the constant rate density function \(f\) is constant on the leaves of the tree. More generally, if the subtrees \((S_x, \upa)\) and \((S_y, \upa)\) are isomorphic for some \(x, \, y \in S\) then \(f(x) = f(y)\).

Examples

Regular Trees

In this subsection, we consider the upward run graph \((S, \rta)\) associated with the 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)\). The corresponding downward run graphs were studied in Section 5, and as in that section, the results depend on a critical relationship between the parameters \(m\) and \(k\). The following preliminary result will help in the analysis.

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 \]
Details:

From \(\varphi[e, 1 / (m + 1)] = 1\) and hence \(\alpha = 1 / (m + 1)\). Then \[\varphi(x, \alpha) = \frac{m + 1 - d(x)}{m + 1}, \quad x \in S\] The normalizing constant is \[c = \frac{[(m + 1)^m - 1](m + 1)}{m^2}\]

In example , it's easy to see that \(g\) is increasing with \(n\) for fixed \(m\) and that \(g(m) \to 1\) as \(m \to \infty\). So the distribution of \(d(X)\) converges to point mass at \(\infty\) as \(m \to \infty\). The convergence is very rapid. Even for relatively small \(m\) most of the probability is concentrated very close to \(m\). For example, with \(m = 10\), we have \(g(10) = 0.826446\) \and \(g(9) = 0.150263\)

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} - \]
Details:

From , \(\varphi(e, 1 / k) \gt \varphi[e, 1 / (m + 1)] = 1\) and hence \(\alpha \lt 1 / k\). Moreover, \[\varphi(x, t) = t \frac{1 - (k t)^{m + 1 - d(x)}}{1 - k t}, \quad t \in [0, \infty), \; t \ne 1 / k \] Solving \(\varphi(e, \alpha) = 1\) gives the equation for \(\alpha\). It then follows that \(f(x)\) is proportional to \(1 - (k \alpha)^{m + 1 - d(x)}\) for \(x \in S\). Geometric series then gives the normalizing constant.

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} \]
Details:

The proof is essentially just like the proof in , except for the observation that \(\varphi(e, 1 / k) \lt \varphi[e, 1 / (m + 1)] = 1\) and hence \(\alpha \gt 1 / k\).

The only case remaining is \(k = 1\). In this case, the tree is the directed path of height \(m \in \N_+\), and as usual we can let \(S = \N_m\) with 0 as the root and \(x = d(x)\).

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\).
Details:

From , \(f(x) = (1 - \alpha^{m - x + 1}) / C\) for \(x \in \N_m\) where \[ C = \sum_{x = 0}^m (1 - \alpha^{m - x + 1}) = m + 1 - \frac{\alpha - \alpha^{m + 2}}{1 - \alpha}\] But from the equation defining \(\alpha\) in (a), \((\alpha - \alpha^{m + 2}) / (1 - \alpha) = - 1\).

In the special case \(m = 1\) in example , the rooted tree is a rooted star and then the upward run graph is the ordinary undirected star with a loop at \(e\), the center of the star. In this case, the upward run and downward run graphs are the same and the rooted star is the only rooted tree with this property.

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_+\).
Details:

Since the upward run graph corresponding to \((S, \upa)\) is the same as the downward run graph, this result follows from the corresponding result in Section 5. A direct proof is also easy.

Our last result in this subsection concerns the standard upward run graph \((\N, \rta)\). This graph does not have a constant rate distribution, but we can give the rate function in the special case that \(X\) has a geometric distribution.

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\).

Binomial Trees

Recall the (directed) binomial trees defined in Section 1.

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\).
Details:

Recall that \((S_x, \upa)\) is also a binomial tree for every \(x \in S\). If \((S_x, \upa)\) has order \(k \in \{0, 1, \ldots, m\}\) then \(\beta_j(x) = \binom{k}{j}\) for \(j \in \{0, 1, \ldots, k\}\). Hence \[ \varphi(x, t) = \sum_{j = 0}^{k} \binom{k}{j} t^{j + 1} = t (1 + t)^k \] In particular, \( \varphi(e, t) = t (1 + t)^m \) so the rate constant \(\alpha\) satisfies \(\alpha (1 + \alpha)^m = 1 \). There are \(2^{m - 1 - k}\) binomial subtrees of order \(k \in \{0, 1, \ldots, m - 1\}\) and hence the normalizing constant is \[c = \sum_{x \in S} \varphi(x, \alpha) = 1 + \sum_{k = 0}^{m - 1} 2^{m - 1 - k} \alpha (1 + \alpha)^k\] which simplifies to \[ (2^m - 1) \frac{\alpha}{1 - \alpha} \] The form of \(f\) then follows from .

Random Walks

Suppose again that \((S, \rta)\) is the upward runs graph associated with a rooted tree \((S, \upa)\) and that \(X\) is a random variable in \(S\) with density function \(f\).

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\]

A bit more generally, let \( \bs Y = (Y_0, Y_1, \ldots) \) be a random walk on \((S, \rta)\), not necessarily associated with a random variable \(X\) and without a specified initial distribution. For the standard graph \((\N, \rta)\), the random walk \(\bs Y\) is success-run chain in the classical sense. In general, note that \(\bs Y\) is irreducible and aperiodic since we assume that the transition probability \(P\) satisfies \(P(x, y) \gt 0\) when \(x \rta y\). For the main result that follows we need a couple of definitions.

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)\]

In words, \(G(x)\) is the probability that \(\bs Y\) hits state \(x\) without an intermediate return to \(e\), given \(Y_0 = e\).

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\).
Details:

Part (a) is clear from the definition of \(G\) and parts (b), (c), and (e) follow from (a) and the general theory of discret-time Markov chains. For part(d), note that \[ (G P)(e) = \sum_{x \in S} G(x) P(x, e) = \sum_{n = 0}^\infty \sum_{d(x) = n} G(x) P(x, e) \sum_{n = 0}^\infty \P(T_e = n + 1 \mid Y_0 = e) = \P(T_e \lt \infty \mid Y_0 = e) = 1 = G(e) \] On the other hand, \((G P)(x) = G(x^-) P(x^-, x) = G(x) \) for \(x \in S_+\). In words, \(\bs Y\) hits \(x\) without an intermediate return to \(e\) if and only if \(\bs Y\) hits the parent \(x^-\) without an intermediate return to \(x\) and then in the next step goes to \(x\).

Of course, in the positive recurrent case, the invariant probability density function \(g\) is given by \[g(x) = \frac{G(x)}{\sum_{y \in S} G(y)} = \frac{G(x)}{\E(T_e \mid Y_0 = e)}, \quad x \in S\] Here are some simple sufficient conditions for recurrence and positive recurrence in the case that the random walk is associated with a random variable.

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.
Details:

From note that \(P(x, e) \ge f(e) / [f(e) + 1] \gt 0\) for \(x \in S\). Hence if \(x \upa y\) then \(P(x, y) \le 1 - P(x, e) \le 1 / [f(e) + 1] \lt 1\) and so \(G(x) \le \beta_n(e) / [1 + f(e)]^n\) if \(d(x) = n\). The results then follows from

From the general theory of reliability chains, the time reversal of a random walk on the upward run graph \((S, \rta\)) is a random walk on the corresponding downward run graph \((S, \lfa)\). Clearly not every random walk on \((S, \rta)\) is the random walk associated with a random variable \(X\). Here are conditions for the standard upward run graph \((\N, \rta)\).

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\]

Details:

Our goal is to find a density function \(f\) on \(\N\) with \[a(x) = \frac{f(x + 1)}{f(0) + f(x + 1)}, \quad x \in \N\] Equivalently, \[f(x + 1) = \frac{a(x)}{1 - a(x)} f(0), \quad x \in \N\] and so the results follow

Open the simulation of the success runs chain with parameter \(p\). This is the chain with \(P(x, x + 1) = p\) and \(P(x, 0) = 1 - p\) for \(x \in \N\). Tne initial state is 0. The limiting distribution is the geometric distribution on \(\N\) with parameter \(1 - p\). Vary \(p\) and note the shape of the limiting probability density function. Run the simulation 1000 times and compare the empirical density function to the probability density function.

Open the simulation of the success runs chain and the simulation of the remaining life chain. These chains are time reversals of one another. For a given value of \(p\), run the two simulations side by side and note the behavior.