For this section, please recall the discussion of graph basics in Section 1.1 and in particular the discussion of partial order graphs in Section 1.2.
A rooted, directed tree with root \(e \in S\) is a discrete, acyclic graph \((S, \upa)\) with the property that there is a unique finite path from \(e\) to \(x\) for each \(x \in S\).
A rooted directed tree \((S, \upa)\) is the covering graph for a partial order graph \((S, \preceq)\), so that \(x \preceq y\) if and only if \(x = y\) or there is a (unique) finite path from \(x\) to \(y\) in \((S, \upa)\).
By definition \(x \preceq x\) so the relation is reflexive. If \(x \preceq y\) and \(y \preceq x\) for \(x, \, y \in S\) then there is a path from \(x\) to \(y\) and a path from \(y\) to \(x\) in the covering graph \((S, \upa)\). But then \(x = y\) for otherwise there would be a cycle in the covering. So the antisymmetric property holds. Finally if \(x \preceq y\) and \(y \preceq z\) for \(x, \, y, \, z \in S\) then there exists a path from \(x\) to \(y\) and a path from \(y\) to \(z\) in the covering graph \((S, \upa)\). Concatenating the paths gives a path from \(x\) to \(z\) in the covering graph so \(x \preceq z\). Hence the transitive property holds.
Note that the root \(e\) is the minimum element of \((S, \preceq)\) and that \((S, \preceq)\) is well founded. Often our primary interest in the partial order graph \((S, \preceq)\), but the analysis of this graph depends very much on the covering graph \((S, \upa)\), and more generally on \((S, \upa^n)\) where \(\upa^n\) is the \(n\)-fold composition power of \(\upa\) for \(n \in \N\). In the terminology of Section 1.2, \((S, \preceq)\) is completely uniform since there is one path from \(x\) to \(y\) for \(x, \, y \in S\) with \(x \prec y\). Here are some graphs of secondary interest:
Let \((S, \upa)\) be a rooted tree with associated partial order graph \((S, \preceq)\).
In addition, we will consider downward run graphs and upward run graphs that can be constructed in natural ways from a rooted tree. In general, the base set \(S\) may be finite or countably infinite, but by assumption, \((S, \preceq)\) is locally finite, so that \([e, x]\) is finite for each \(x \in S\). The graph \((S, \preceq)\) is uniform since there is a unique path from \(x\) to \(y\) whenever \(x \prec y\). Here are some other basic definitions, some of which we have seen before:
Let \((S, \upa)\) be a rooted tree with associated partial order graph \((S, \preceq)\).
Suppose again that \((S, \upa)\) is a rooted tree. The corresponding partial order graph \((S, \preceq)\) is a lower semi-lattice.
For \(x, \, y \in S\), \(x \wedge y \) is the largest common ancestor of \(x\) and \(y\).
Note however that unless \((S, \upa)\) is a directed path, \((S, \preceq)\) is not an upper semi-lattice. If \(x, \, y \in S\) and \(x \parallel y\) then there is no upper bound of \(\{x, y\}\). Also, even though the tree \((S, \upa)\) is locally finite, it's possible for a vertex to have infinitely many children. Note that \(d(x, y) = d(y) - d(x)\) if \(x \preceq y\). Note also that for \(d(x, y) = n\) if and only if \(x \upa^n y\) for \((x, y) \in S^2\) and \(n \in \N\). Thus the collection \[\{\{y \in S: x \upa^n y\}: n \in \N\} = \{\{y \in S: d(x, y) = n\}: n \in \N\}\] partitions \(S_x\). In particular, when \(x = e\), the collection partitions \(S\). For the next result, recall that the \(\sigma\)-algebra associated with a graph is the \(\sigma\)-algebra generated by the collection of (right) neighbor sets. Of course since we are in a discrete setting, the reference \(\sigma\)-algebra is \(\ms P(S)\), the collection of all subsets of \(S\).
Let \(A_x = \{y \in S: x \upa y\}\), the set of children of \(x \in S\), Let \(\ms A\) be the collection of subsets that consists of \(\{e\}\) and \(A_x\) for \(x \in S\).
Since \((S, \preceq)\) is a discrete, left-finite partial order graph, part (b) holds by a result in Section 1.2. By another result in that section, the \(\sigma\)-algebras associated with \((S, \upa)\) and \((S, \prec)\) are the same and hence the common \(\sigma\)-algebra is \(\sigma(\ms A)\). The countable collection \(\ms A\) partitions \(S\). That is, the subsets in \(\ms A\) are pairwise disjoint and their union is \(S\). So the \(\sigma(\ms A)\) consists of all unions of sets in \(\ms A\).
Unless \((S, \upa)\) is a directed path, the (right) \(\sigma\)-algebra \(\ms A\) associated with \((S, \upa)\) and \((S, \prec)\) is a strict subset of \(\ms P(S)\).
Suppose again that \((S, \upa)\) is a rooted tree as given in , with corresponding partial order graph \((S, \preceq)\).
The left walk function function \(u_n\) of order \(n \in \N\) for \((S, \preceq)\) is given by \[u_n(x) = \binom{n + d(x)}{n} = \frac{[d(x) + 1] [d(x) + 2] \cdots [d(x) + n]}{n!}, \quad x \in S\]
Recall that by definition, \(u_0(x) = 1\) for \(x \in S\). To construct a path of length \(n\) ending in \(x\) in the graph \((S, \preceq)\), we need to select a multiset of size \(n\) from the \(d(x) + 1\) vertices on the unique simple path of length \(d(x)\) in \((S, \upa)\) form \(e\) to \(x\). The number of ways to do this is \(\binom{n + d(x) + 1 - 1}{d(x)}\).
Find the left walk function of order \(n \in \N\) for the following graphs:
The left generating function \(U\) for \((S, \preceq)\) is given by \[U(x, t) = \frac{1}{(1 - t)^{d(x)+1}}, \quad x \in S, \, t \in (-1, 1) \]
From the definition, \[U(x, t) = \sum_{n = 0}^\infty \binom{n + d(x)}{d(x)} t^n = \frac{1}{(1 - t)^{d(x) + 1}}, \quad |t| \lt 1, \; x \in \N\]
Find the left generating function for the following graphs:
The results follow form geometric and binomial series:
The Möbius kernel \(M\) of \((S, \preceq)\) is given as follows: \[M(x, y) = \begin{cases} 1, & y = x \\ -1, & x \upa y \\ 0, & \text{otherwise} \end{cases}\]
This is well known, but a proof is also easy from the definition: \(M(x, x) = 1\) for \(x \in S\), and \[M(x, y) = -\sum_{x \preceq t \prec y} M(x, t), \quad x \preceq y\]
Suppose now that \(X\) is a random variable in \(S\) with density function \(f\). By definition, the (right) reliability function of \(X\) for one of the graphs is the function that assigns probabilities to the (right) neighbor sets. Recall that the graph is (right) stochastic if a probability measure on the associated \(\sigma\)-algebra is uniquely determined by the reliability function. By , the \(\sigma\)-algebra associated with \((S, \preceq)\) and with \((S, \upa)\) is the reference \(\sigma\)-algebra \(\ms P(S)\).
The graph \((S, \preceq)\) is stochastic. A function \(F: S \to [0, 1]\) is a reliability function for \((S, \preceq)\) if and only if
In this case, the unique density function is given by \[ f(x) = F(x) - \sum_{x \upa y} F(y), \quad x \in S \]
The characterization follows from the Möbius inversion formula in Section 1.4, using the Möbius kernel in , but we will give a direct proof. Suppose first that \(F\) is the reliability function on \((S, \preceq)\) for random variable \(X\) with density function \(f\). Then
and then \[ f(x) = \P(X = x) = \P(X \succeq x) - \P(X \succ x) = \P(X \succeq x) - \sum_{x \upa y} \P(X \succeq y) = F(x) - \sum_{x \upa y} F(y)\] Conversely, suppose that \(F\) satisfies the conditions in the theorem, and let \(f\) be defined by the displayed equation. By (b), \(f(x) \ge 0\) for \(x \in S\). Next, for \(x \in S\), \begin{align*} \sum_{x \preceq y} f(y) &= \sum_{n = 0}^\infty \sum_{x \upa^n y} f(y) = \sum_{n=0}^\infty \sum_{x \upa^n y} \left[F(y) - \sum_{y \upa z} F(z)\right] = \lim_{m \to \infty} \sum_{n = 0}^m \sum_{x \upa^n y} \left[F(y) - \sum_{y \upa z} F(z)\right] \\ &= \lim_{m \to \infty} \left[\sum_{n = 0}^m \sum_{x \upa^n y} F(y) - \sum_{n = 0}^m \sum_{x \upa^n y} \sum_{y \upa z} F(z)\right] = \lim_{m \to \infty} \left[\sum_{n = 0}^m \sum_{x \upa^n y} F(y) - \sum_{n = 0}^m \sum_{x \upa^{n + 1} z} F(z)\right] \\ &= \lim_{m \to \infty} \left[\sum_{n = 0}^\infty \sum_{x \upa^n y} F(y) - \sum_{n = 1}^{m + 1} \sum_{x \upa^n y} F(y)\right] = \lim_{m \to \infty} \left[F(x) - \sum_{x \upa^{m + 1} y} F(y)\right] = F(x) \end{align*} Letting \(x = e\) shows that \(\sum_{x \in S} f(x) = 1\) so that \(f\) is a probability density function. For general \(x \in S\), it then follows that \(F\) is the reliability function of \(f\).
The graph \((S, \Upa)\) is stochastic. If \(G\) is the reliability function for \((S, \Upa)\) corresponding to density function \(g\), then \(g\) can be recovered from \(G\) by \[ g(x) = \sum_{n = 0}^\infty (-1)^n \sum_{x \upa^n y} G(y), \quad x \in S\]
Suppose that \(X\) is a random variable in \(S\) with density \(g\) and with reliability function \(G\) for \((S, \Upa)\). For \(n \in \N\), \[ \sum_{x \upa^n y} G(y) = \sum_{x \upa^n y} \P(X = y \text{ or } y \upa X) = \P[d(x, X) = n] + \P[d(x, X) = n + 1], \quad x \in S\] Hence the partial sum up to \(m \in \N_+\) collapses: \[\sum_{n = 0}^m (-1)^n \sum_{x \upa^n y} G(y) = \P(X = x) + (-1)^n \P[d(x, X) = m + 1], \quad x \in S\] Letting \(m \to \infty\) gives the result.
Next, let \(A_x = \{y \in S: x \upa y\}\), the set of children of \(x \in S\) and the neighbor set of \(x\) for the graph \((S, \upa)\). By , for both the graph \((S, \upa)\) and the graph \((S, \prec)\), the associated \(\sigma\)-algebra is \(\sigma(\ms A)\) where \(\ms A\) is the collection of subsets that consists of \(\{e\}\) and \(A_x\) for \(x \in S\). This collection of sets partitions \(S\) and so \(\sigma(\ms A)\) consists of all unions of sets in \(\ms A\). Unless \((S, \upa)\) is a directed path, \(\sigma(\ms A)\) is a strict subset of \(\ms P(S)\) and so in general, a reliability function of a distribution on \(\ms P(S)\) does not determine the distribution. Nonetheless, the graphs are stochastic.
The graphs \((S, \upa)\) and \((S, \prec)\) are stochastic.
Suppose that \(P\) is a probability measure on \(\sigma(\ms A)\). That \((S, \upa)\) is stochastic is trivial, since the reliability function \(F\) of \(P\) for the graph is simply \(F(x) = P(A_x)\) for \(x \in S\). Let \(G\) denote the reliability function of \(P\) for the graph \((S, \prec)\). We simply need to show that \(P(A_x)\) can be written in terms of \(G\) for each \(x \in S\). Let \(B_x = \{y \in S: x \prec y\}\), the neighbor set of \((S, \prec)\) for \(x \in S\), so that \(G(x) = P(B_x)\) for \(x \in S\). Then \(A_x = B_x - \bigcup_{x \upa y} B_y\) for \(x \in S\) and therefore since the sets in the union are disjoint, \(P(A_x) = G(x) - \sum_{x \upa y} G(y)\) for \(x \in S\).
Suppose again that \(X\) is a random variable in \(S\).
The moment of \(X\) of order \(n \in \N\) for the graph \((S, \preceq)\) is \[\E \binom{d(X) + n}{n} = \frac{1}{n!} \E([d(X) + 1] [d(X) + 2] \cdots [d(X) + n])\]
Find the moment of \(X\) of order \(n \in \N\) for the following graphs:
Of course, the fundamental moment formula applys to all of the graphs: If \(u_n\) denotes the left walk function of order \(n\) for the graph and \(F\) is the reliability function of \(X\) for the graph then \[\sum_{x \in S} u_n(x) F(x) = \E[u_{n + 1}(X)]\]
The moment generating function \(M\) of \(X\) for the graph \((S, \preceq)\) is given by \[M(t) = \E\left[\frac{1}{(1 - t)^{d(X)+1}}\right], \quad t \in (-1, 1) \]
Find the moment generating function of \(X\) for the following graphs:
We will identify a class of probability distributions that have constant rate for all of the graphs under discussion, and we will identify the rate constants. A tree with leaves cannot have a constant rate distribution, so we will assume for the rest of this section that \((S, \preceq)\) has no leaves, and hence that \(S\) is countably infinite.
Fix \(\alpha \in (0, 1)\). The following recursive scheme defines a probability density functions \(f\) on \(S\):
Note first that \((S, \preceq)\) is a well-founded partial order graph, and hence the recursive definition makes sense. Since the tree has no leaves, \(\{y \in S: x \upa y\}\) is nonempty for each \(x \in S\), and there is always some way to define \(f(y)\) for \(x \upa y\) so that (a) and (b) are satisfied. In fact, if \(\#\{y \in S: x \upa y\} \ge 2\) then this can be done in infinitely many ways. We show by induction that \[\sum_{e \upa^n x} f(x) = \alpha (1 - \alpha)^n, \quad n \in \N\] First, this holds for \(n = 0\) by definition. If it holds for a given \(n \in \N\), then by construction \[\sum_{e \upa^{n+1} x} f(x) = \sum_{e \upa^n x} \sum_{x \upa y} f(y) = \sum_{e \upa^n x} (1 - \alpha) f(x) = (1 - \alpha) \alpha (1 - \alpha)^n = \alpha (1 - \alpha)^{n + 1}\] So then \[\sum_{x \in S} f(x) = \sum_{n = 0}^\infty \sum_{e \upa^n x} f(x) = \sum_{n = 0}^\infty \alpha(1 - \alpha)^n = 1\]
Suppose that random variable \(X\) in \(S\) has density function \(f\) with parameter \(\alpha \in (0, 1)\) constructed in . Then
Note also that parts (a) and (e) follow from (b) by the general results in Section 1.5, since \((S, \preceq)\) is completely uniform, with a single path from \(x\) to \(y\) for \(x, \, y \in S\) with \(x \prec y\).
Clearly if \(F\) is the reliability function for \((S, \preceq)\) corresponding to a density function \(f\) constructed in , then \(F\) also satisfies the recursive relation, but with initial condition replaced by \(F(e) = 1\).
Suppose again that \(X\) has density function \(f\) with parameter \(\alpha \in (0, 1)\) constructed in , and let \(N = d(X)\). Then \(N\) has the geometric distribution on \(\N\) with success parameter \(\alpha\).
From , \(\P(N = n) = \P(e \upa^n X) = \alpha (1 - \alpha)^n\) for \(n \in \N\). This result also follows from the general results in Section 1.5, since \((S, \preceq)\) is completely uniform, with a single path from \(x\) to \(y\) for \(x, \, y \in S\) with \(x \prec y\).
Recall that the geometric distribution has constant rate for \((\N, \le)\), \((\N, \lt)\), and for the covering graph \((\N, \upa)\). Of course, the last graph is a directed path and hence a rooted tree where each vertex has a single child.
Suppose again that \(X\) is a random variable in \(S\). Then for the graph \((S, \preceq)\), \(X\) has constant rate \(\alpha \in (0, 1)\) if and only if \(X\) has constant average rate \(\alpha^n\) of order \(n\) for each \(n \in \N_+\).
The proof is essentially the same as for \((\N, \le)\). We know that if \(X\) has constant rate \(\alpha\) for a graph then \(X\) has constant average rate \(\alpha^n\) of order \(n\) for each \(n \in \N\). Conversely, suppose that \(X\) has constant average rate \(\alpha^n\) of order \(n\) for the graph \((S, \preceq)\), for some \(n \in \N_+\). Let \(r\) and \(R_n\) denote the rate function and cumulative rate function of order \(n\) of \(X\) for \((S, \preceq)\). By assumption then, \[ R_n(x) = \sum_{x_1 \preceq x_2 \preceq \cdots \preceq x_n \preceq x} r(x_1) r(x_2) \cdots r(x_n) = \alpha^n u_n(x), \quad x \in S \] Where has usual, \(u_n\) is the left walk function of order \(n\). We will show by partial order induction that \(r(x) = \alpha\) for \(x \in S\). First, letting \(x = e\) in the displayed equation gives \(r^n(e) = \alpha^n\) so \(r(e) = \alpha\). Suppose now that \(x \in S_+\) and that \(r(y) = \alpha\) for \(y \prec x\). For \(k \in \{0, 1, \ldots n\}\) let \(A_k\) denote the set of walks \(\bs x = (x_1, x_2, \ldots, x_n)\) with \(x_1 \preceq x_2 \preceq \cdots \preceq x_n \preceq x\) and with \(x_i \prec x\) for exactly \(k\) indices. Hence \(x_i = x\) for \(n - k\) indices. Let \(x_-\) denote the parent of \(x\). The collection \(\{A_k: k = 0, 1, \ldots n\}\) partitions the set of walks of length \(n\) terminating in \(x\). Moreover, the elements in \(A_k\) are in one-to-one correspondence with the walks of length \(k\) terminating in \(x_-\) and hence there are \(u_k(x_-)\) such paths. By the induction hypothesis, note that if \(\bs x \in A_k\) then \(r(x_1) r(x_2) \cdots r(x_n) = \alpha^k r^{n-k}(x)\). Substituting into the displayed equation gives \[\sum_{k = 0}^n u_k(x_-) \alpha^k r^{n - k}(x) = \alpha^n u_n(x) = \sum_{k = 0}^n \alpha ^k \alpha^{n - k} u_k(x_-)\] or equivalently \[\sum_{k = 0}^n \alpha^k u_k(x_-)\left[r^{n-k}(x) - \alpha^{n - k}\right] = 0\] Hence \(r(x) = \alpha\).
Next we consider the random walks on the various graphs associated with the constant rate distributions.
Suppose next that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on \((S, \preceq)\) associated with \(X\), where \(X\) has density function \(f\) with parameter \(\alpha \in (0, 1)\) constructed in . Then \(Y_n\) has density function \(f_n\) for \(n \in \N\) given by \[f_n(x) = \alpha^{n - 1} \binom{n - 1 + d(x)}{d(x)} f(x), \quad x \in S\]
This follows from the general theory: \(f_n(x) = \alpha^n u_{n - 1}(x) F(x) = \alpha^{n - 1} u_{n - 1}(x) f(x) \) for \(x \in S\).
Suppose that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on each of the graphs below associated with \(X\), where \(X\) has density function \(f\) with parameter \(\alpha \in (0, 1)\) constructed in . For \(n \in \N_+\), find the density function of \(Y_n\) for each of the following graphs:
Once again, the results follow from the general theory: The density function \(f_n\) of \(Y_n\) is given by \(f_n(x) = \alpha^n u_{n - 1}(x) F(x) = \alpha^{n - 1} u_{n - 1}(x) f(x)\) for \(x \in S\).
Let \(\N_m = \{0, 1, \ldots, m\}\) for \(m \in \N_+\).
The infinite directed path is \((\N, \upa)\) where 0 is the root and \(x \upa x + 1\) for \(x \in \N\).
Of course, the infinite directed path was the basic graph studied in Chapter 4 and is associated the semigroup \((\N, +)\).
The (finite) directed path of height \(m \in \N_+\) is \((\N_m, \upa)\) where 0 is the root and \(x \upa x + 1\) for \(x \in \{0, 1, \ldots, m - 1\}\).
For both finite and infinite directed paths, as we have defined them, the corresponding order is the ordinary order \(\le\). Also \(d(x) = x\) for each vertex \(x\) and more generally, \(d(x, y) = y - x\) for verticies \(x, \, y\) with \(x \le y\).
The infinite regular rooted tree \((S, \upa)\) of degree \(k \in \N_+\) is defined by the property that every vertex \(x \in S\) has \(k\) children.
We can also consider the infinite regular rooted tree of infinite degree where every vertex \(x \in S\) has a (countably) infinite set of children. For \(x \in S\), the subtree \((S_x, \upa)\) of a regular rooted tree of order \(k \in \N \cup \{\infty\}\) is also a regular rooted tree of order \(k\). The partial order graphs associated with infinite regular rooted trees are the graphs of free semiroups as we will see in Section 2. Constant rate distributions for such graphs can be constructed via the procedure in .
The (finite) regular rooted tree \((S, \upa)\) of degree \(k \in \N_+\) and height \(m \in \N_+\) is defined by the property that every vertex at distance \(j \lt m\) from the root \(e\) has \(k\) children, but the vertices at distance \(m\) from \(e\) are leaves.
The regular rooted tree of degree 1 is isomorphic to the directed path, both in the finite and infinite cases. A regular rooted tree of degree 2 (either finite or infinite) is a binary tree. Suppose that \((S, \upa)\) is the regular rooted tree of degree \(k\) and height \(m\). If \(x \in S\) with then the subtree \((S_x, \upa)\) is a regular rooted tree of degree \(k\) with root \(x\) and height \(m - d(x)\).
Directed Binomial trees are defined recursively:
Starting with a directed binomial tree \((S, \upa)\) of order \(n \in \N\), a directed binomial tree of order \(n + 1\) can also be constructed by adding a new child by a new directed edge to every existing vertex in \(S\). The following proposition collects some basic facts about directed binomial trees.
Suppose that \((S, \upa)\) is a directed binomial tree of order \(n \in \N_+\).
So in particular, a directed binomial tree \((S, \upa)\) of order \(n \in \N_+\) has \(2^{n - 1}\) leaves and \(2^{n - 1}\) interior vertices. The vertices of a binomial tree of order \(n \in \N_+\) can be labeled with bit strings of length \(n\). There is a nice consistent way to do so.
Directed binomial trees can be labeled with bit strings as follows:
With the labeling above, vertices that end in 1 are leaves; vertices that end in 10 have one child; vertices that end in 100 have two children; and so forth. The root is labeled \(0 0 \cdots 0\) (\(n\) times). Undirected binomial trees are also interesting and are studied in Section 1.10.