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 3. We start with a discrete rooted tree \((S, \upa)\) with root \(e\) and at least two vertices. 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 \(d(x) = d(e, x)\) and let \((S_x, \upa)\) denotes the subtee of \((S, \upa)\) rooted at \(x\).
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\).
For \(x \in S\), define the power series \(\varphi(x, \cdot)\) by \[\varphi(x, t) = \sum_{n = 0}^\infty \beta_n(x) t^{n + 1}, \quad t \in [0, 1]\]
Note that \(\varphi(x, 1) = \#(S_x)\). So if the subtree \((S_x, \upa)\) is finite (the most important case in this section), then \[\varphi(x, t) = \sum_{n = 0}^{m(x)} \beta_n(x) t^{n + 1}, \quad t \in [0, 1]\] where \(m(x) \in \N\) is the height of \((S_x, \upa)\). If \((S_x, \upa)\) is infinite, then \(\varphi(x, \cdot)\) has radius of convergence \(\rho(x) \in [0, 1]\). Recall that \(\beta_n(e)\) and \(\varphi(e, \cdot)\) were important in Section 3 on downward run graphs. The more general functions will be important in this section. Here is the main corollary that we will need:
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 walk 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 3.
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
The walks 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 (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 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 with 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)\).
Once again we have the upward run graph \((S, \rta)\) associated with the rooted tree \((S, \upa)\).
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)\).
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), \#)\) and defined on an underlying probability space \((\Omega, \ms F, \P)\). Let \(f\) denote the probability density function of \(X\) 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)\),
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
In this case, a density function \(f\) with reliability function \(F\) for \((S, \rta)\) can be constructed as follows:
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. For the following result, recall the power series defined in .
Suppose that \((S, \upa)\) is a finite rooted tree. For the unique constant rate distribution on the upward run graph \((S, \rta)\),
By definition, the density function \(f\) of the distribution with constant rate \(\alpha\) 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\) must satisfy the equation \(\varphi(e, \alpha) = 1\). Since \(\varphi(e, \cdot)\) is continuous and increasing on \([0, 1]\) with \(\varphi(0) = 0\) and \(\varphi(1) = \#(S) \ge 2\), there exist a unique \(\alpha \in (0, 1)\) with \(\varphi(e, \alpha) = 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)\).
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\),
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\).
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\).
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\).
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_+\). 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\). Recall that \(\N_m = \{0, 1, \ldots, m\}\) for \(m \in \N\).
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
Parts (a) and (b) are clear. Parts (c) and (d) follow from summing the finite geometric series.
Suppose that \(X\) has the unique constant rate distribution for \((S, \rta)\). Then
Of course, the rate constant \(\alpha\) depends on the parameters \(m, \, k \in \N_+\). More specific results depend on the relationship between the parameters \(m, \, k \in \N_+\).
Suppose that \(k = m + 1\) and that \(X\) has constant rate for \((S, \rta)\). Then
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 \(k \lt m + 1\) and that \(X\) has constant rate for \((S, \rta)\). Then
Parts (a) and (b) were shown in Section 3 for the corresponding downward run graph. For part (c), note that \(f(x)\) is proportional to \(1 - (k \alpha)^{m + 1 - d(x)}\) for \(x \in S\). Summing the geometric series then gives the normalizing constant.
Suppose that \(k \gt m + 1\). Then
Part (a) was shown in Section 3 for the corresponding downward run graph. The derivation of the normalizing constant is essentially the same as for .
The asymptotic behavior of the rate constant in was studied in Section 3. We repeat it below for completeness.
Let \(\alpha_k\) denote the rate constant for \((S, \rta)\) for fixed \(m \in \N_+\) and with \(k \in \N_+\) satisfying \(k \gt m + 1\), as described in . Then \(k^m \alpha_k^{m + 1} \to 1\) as \(k \to \infty\). As corollaries,
The case \(k = 1\) is a special case of , but is worth stating separately since the tree is the directed path of height \(m \in \N_+\). As usual we can let \(S = \N_m\) with 0 as the root and \(x = d(x)\).
Suppose that \(k = 1\). Then
The case \(m = 1\) is a special case of or or (depending on \(k \in \N_+\)). This case is interesting because 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 \(m = 1\) and that \(X\) has the unique constant rate distribution for the corresponding upward run graph \((S, \rta)\). Then
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 3. A direct proof is also easy.
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
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 .
The standard upward run graph \((\N, \rta)\) does not have a constant rate distribution, but we can give the rate function in the special case that random variable \(X\) in \(\N\) 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\).
The follow ressult gives conditions for a random walk on \((\N, \rta)\) to be associated with a random variable.
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\]
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
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.
Success-runs chain
Remaining-life chain