A measurable function from a measure space to another measure space with a graph leads to a graph on the domain space in a natural way. This section explores this setting in general and in a number of important special cases.
Suppose that \((S, \ms S, \lambda)\) and \((T, \ms T, \mu)\) are \(\sigma\)-finite measure spaces and that \(\varphi\) is a measurable function from \(S\) onto \(T\).
The measure \(\nu\) on the measurable space \((T, \ms T)\) induced by \(\varphi\) is defined by \(\nu(B) = \lambda[\varphi^{-1}(B)]\) for \(B \in \ms T\).
So we have two measure on the space \((T, \ms T)\)—the referece measure \(\mu\) and the induced measure \(\nu\), and of course in general they are not the same. The reference measure is usually a natural measure in some sense, such as counting measure if the space is discrete or Lebesgue measure if the space is Euclidean. The measure structures are linked together by the assumption given next and proposition that follows.
We assume that there is a finite, positive measure \(\lambda_t\) on \((S_t, \ms S_t)\) for each \(t \in T\) such that \(t \mapsto \lambda_t(A \cap S_t)\) is measurable for \(A \in \ms S\) and \[\lambda(A) = \int_T \lambda_t(A \cap S_t) \, d\mu(t), \quad A \in \ms S\] Let \(\beta(t) = \lambda_t(S_t) \in (0, \infty)\) for \(t \in T\).
The induced measure \(\nu\) is absolutely continuous with respect to the reference measure \(\mu\), with density function \(\beta\).
Let \(A \in \ms T\). Then by the basic assumption, \[\nu(A) = \lambda[\varphi^{-1}(A)] = \int_T \lambda_t[\varphi^{-1}(A) \cap S_t] \, d\mu(t) = \int_T \lambda_t[\varphi^{-1}(A \cap \{t\})] \, d\mu(t)\] But \(\varphi^{-1}(A \cap \{t\}) = \varphi^{-1}\{t\} = S_t\) if \(t \in A\) and is \(\emptyset\) otherwise, so \[\nu(A) = \int_A \lambda_t(S_t) \, d\mu(t) = \int_A \beta(t) \, d\mu(t)\]
Since \(\beta\) is strictly positive, the reference measure \(\mu\) is also absolutely continuous with respect to the induced measure \(\nu\), with density function \(1 / \beta\). Hence, the two measures are equivalent, under the natural equivalence relation associated with absolute continuity. Taken together, assumption and proposition are a special version of a basic theorem in analysis known as the disintegration theorem (a generalization of Fubini's theorem). Indeed if the measure spaces are standard \(\sigma\)-finite Borel spaces, as discussed in the Preface, and if holds then also holds, although the measures \(\lambda_t\) are not necessarily finite. Moreover, the measures \(\lambda_t\) for \(t \in T\) are unique, up to a set of \(\mu\) measure 0. So and are simply the disintegration theorem, but with the added assumption that the slices
have positive, finite measure: \(\lambda_t(S_t) \in (0, \infty)\) for \(t \in T\). As we will see, assumption is satisfied in the important special cases that are of most interest to us—the discrete case studied below, and the norm graphs studied in Section 3.6. In the latter case, the graphs are on Euclidean spaces where the basic assumption is essentially the co-area formula. Naturally, there is an integral versions of :
If \(f: S \to \R\) is integrable then \[\int_S f(x) \, d \lambda(x) = \int_T \int_{S_t} f(x) \, d\lambda_t(x) \, d \mu(t)\]
Here is our basic definition:
Suppose that \((T, \rta)\) is a graph. The graph \((S, \Rta)\) induced by \((T, \rta)\) and the mapping \(\varphi\) is defined by \(x \Rta y\) if and only if \(\varphi(x) \rta \varphi(y)\) for \((x, y) \in S^2\).
We need to show that \((S, \Rta)\) is a valid graph. The function \((\varphi, \varphi)\) from \(S^2\) into \(T^2\) is measurable, and \[\{(x, y) \in S^2: x \Rta y\} = \{(x, y) \in S^2: \varphi(x) \rta \varphi(y)\}\] is the inverse image under \((\varphi, \varphi)\) of \(\{(u, v) \in T^2: u \rta v\}\).
The main point of this section is to see how results for the graph \((T, \rta)\) can be leveraged to obtain corresponding results for the induced graph \((S, \Rta)\). As we will see, the graph \((S, \Rta)\) is essentially the same (in ways that matter to us) as the graph \((T, \rta)\) but with the induced measure \(\nu\). In turn, this graph can be viewed as a weighted version of the graph \((T, \rta)\) with reference measure \(\mu\), where vertex \(t\) is given weight \(\beta(t)\) for \(t \in T\). So another take away from this section is that the general results of this text apply to weighted graphs, but with a change of measure on the underlying base space. Unless stated otherwise, the reference meausre \(\mu\) is used for the space \((T, \ms T)\) and of course \(\lambda\) is the measure on \((S, \ms S)\) and \(\lambda_t\) is the measure on \((S_t, \ms S_t)\) for \(t \in T\). We will often use our usual notation for mathematical objects associated with the graphs \((S, \Rta)\) and \((T, \rta)\) but with the latter augmented by a circumflex.
For the graph \((S, \Rta)\),
Note that \(v_n\) and \(V\) are the walk function of order \(n \in \N\) and the generating function for the graph \((T, \rta)\) but with the induced measure \(\nu\). Of course, \(V(t, \cdot)\) is a power series and so has a radius of convergence.
There is a direct relationship between the walk and generating functions for \((S, \Rta)\) and \((T, \rta, \mu)\) if \(\beta\) is constant on \(T\), so that all of the partition sets have the same size.
Suppose that \(\beta\) is constant on \(T\). Then relative to the graphs \((S, \Rta)\) and \((T, \rta)\),
Let \(B_t = \{u \in T: t \rta u\}\) denote the set of right neighbors of \(t \in T\) for the graph \((T, \rta)\). If \(x \in S_t\) then the set of right neighbors of \(x\) for the graph \((S, \Rta)\) is \[A_x = \bigcup \left\{S_u: u \in B_t\right\}\]
This follows from the defintion of the induced graph. If \(x \in S_t\) for \(t \in T\) then \(x \Rta y\) if and only if \(y \in S_u\) for some \(u \in T\) with \(t \rta u\).
Recall that the \(\sigma\)-algebras associated with \((S, \Rta)\) and \((T, \rta)\) are \(\ms A = \sigma(\{A_x: x \in S\})\) and \(\ms B = \sigma(\{B_t: t \in T\})\), resepectively. In the discrete case, we will be able to say more about how they are related.
Suppose now that \(X\) is a random variable in \(S\) and let \(\hat X = \varphi(X)\), the associated random variable in \(T\). There is a trivial relationship between the reliability functions of \(X\) and \(\hat X\).
Let \(F\) and \(\hat F\) denote the reliability functions of \(X\) and \(\hat X\) for the graphs \((S, \Rta)\) and \((T, \rta)\), respectively. Then \[F(x) = \hat F(t), \quad t \in T, \, x \in S_t \]
By definition, \[F(x) = \P(x \Rta X) = \P[\varphi(x) \rta \varphi(X)] = \P[\varphi(x) \rta \hat X] = \hat F[\varphi(x)], \quad x \in S\]
So \(F\) is constant on \(S_t\) for each \(t \in T\). We assume that \(\hat X\) is supported by \((T, \rta)\), so that \(\hat F(t) \gt 0\) for \(t \in T\). It then follows that \(X\) is supported by \((S, \Rta)\).
Suppose that \(X\) has density function \(f\). Then \(\hat X\) has density function given by \[\hat f(t) = \int_{S_t} f(x) \, d\lambda_t(x), \quad t \in T\]
Let \(A \in \ms T\). Then \[\P(\hat X \in A) = \P[X \in \varphi^{-1}(A)] = \int_{\varphi^{-1}(A)} f(x) \, d\lambda(x) = \int_S \bs 1[x \in \varphi^{-1}(A)] f(x) \, d\lambda(x)\] So by , \[\P(\hat X \in A) = \int_T \int_{S_t} \bs 1[x \in \varphi^{-1}(A)] f(x) \, d\lambda_t(x) \, d\mu(t) = \int_T \int_S \bs 1[x \in \varphi^{-1}(A) \cap S_t] f(x) \, d\lambda_t(x) \, d\mu(t)\] But \(\varphi^{-1}(A) \cap S_t = \varphi^{-1}(A) \cap \varphi^{-1}\{t\} = \varphi^{-1}(A \cap \{t\})\) and this set is \(S_t\) if \(t \in A\) and is \(\emptyset\) otherwise. Hence \[\P(\hat X \in A) = \int_A \int_{S_t} f(x) \, d\lambda_t(x) \, d\mu(t)\] Note that he density of \(\hat X\) with respect to \(\nu\) is \(\hat f / \beta\).
For \(t \in T\), a conditional density of \(X\) given \(\hat X = t\) is defined by \[f(x \mid t) = \frac{f(x)}{\hat f(t)}, \quad x \in S_t\]
Fix \(t \in T\). Then for \(A \in \ms S\) and with \(f(\cdot \mid t)\) as defined, \begin{align*} & \int_T \hat f(t) \int_{A \cap S_t} f(x \mid t) \, d\lambda_t(x) \, d\mu(t) = \int_T \hat f(t) \int_{A \cap S_t} \frac{f(x)}{\hat f(t)} \, d\lambda_t(x) \, d\mu(t) \\ &= \int_T \int_{A \cap S_t} f(x) \, d\lambda_t(x) \, d\mu(t) = \int_A f(x) \, d\lambda(x) = \P(X \in A) \end{align*} where again we have used . So it follows by definition that \[\P(X \in A \mid \hat X = t) = \int_A f(x \mid t) \, d\lambda_t(x), \quad A \in \ms S_t\]
Let \(r\) and \(\hat r\) denote the rate functions of \(X\) and \(\hat X\) for the graphs \((S, \Rta)\) and \((T, \rta)\), respectively. Then \[r(x) = f(x \mid t) \hat r(t), \quad t \in T, \, x \in S_t\]
As usual, let \(f\) and \(\hat f\) denote density functions of \(X\) and \(\hat X\), and let \(F\) and \(\hat F\) denote the reliability functions of \(X\) and \(\hat X\) for \((S, \Rta)\) and \((T, \rta)\), respectively. Then \[r(x) = \frac{f(x)}{F(x)} = \frac{f(x)}{\hat f(t)} \frac{\hat f(t)}{\hat F(t)} = f(x \mid t) \hat r(t), \quad t \in T, \; x \in S_t \] Note that \(\hat X\) has rate \(\hat r / \beta\) with respect to the induced measure \(\nu\).
From note that \[\int_{S_t} r(x) \, d\lambda_t(x) = \hat r(t), \quad t \in T\]
Once again, suppose that \(X\) is a random variable in \(S\).
For the graph \((S, \Rta)\), using the notation in ,
The results follow from . Of course, in part (a), the graph moments may be infinite and in part (b) the generating function will have an interval of convergence. Note that \(\E[v_n(\hat X)]\) and \(\E[V(\hat X, \cdot)]\) are the moment of order \(n \in \N\) and the generating function of \(\hat X\) for \((T, \rta)\), but relative to the induced measure \(\nu\).
When \(\beta\) is constant, there is a direct relationship.
Supposee that \(\beta\) is constant on \(T\). Then relative to the graphs \((S, \Rta)\) and \((T, \rta)\),
The standard recursive moment formula has a special form.
Let \(u_n\) denote the walk function of order \(n \in \N\) for \((S, \Rta)\), and let \(\hat F\) denote the reliability function of \(\hat X\) for \((T, \rta)\). Then \[\int_{t_1 \rta \cdots \rta t_n \rta t} \beta(t_1) \cdots \beta(t_n) \beta(t) \hat F(t) \, d\mu^{n + 1}(t_1, \ldots, t_n, t) = \E[u_{n + 1}(X)], \quad n \in \N\]
This follows from the general recuvsive moment formula in Section 3, and the results in and . In terms of the induced measure \(\nu\), the formula is not special at all, and simple reduces to the recursive moment formula for \(\hat X\): \[\int_{t_1 \rta \cdots \rta t_n \rta t} \hat F(t) \, d\nu^{n + 1}(t_1, \ldots, t_n, t) = \int_T \hat F(t) v_n(t) \, d\nu(t)= \E[v_{n + 1}(\hat X)], \quad n \in \N\]
Let \(H\) denote the entropy operator, and suppose again that \(X\) is a random variable in \(S\). Then \(H(X) = H(\hat X) + H(X \mid \hat X)\)
This is a general result in entropy, since the distribution of \(X\) completely determines the distribution of \((X, \hat X)\), but we give a separate proof in this context. \begin{align*} H(X) &= -\E[\ln f(X)] = -\E[\E[\ln f(X) \mid \hat X]] = -\E(\E[\ln(\hat f(\hat X) f(X \mid \hat X)) \mid \hat X]) \\ &= -\E[\ln \hat f(\hat X)] - \E(\E[\ln f(X \mid \hat X) \mid \hat X]) = H(\hat X) + H(X \mid \hat X) \end{align*}
As usual, we are particularly interested in constant rate distributions for the induced graph \((S, \Rta)\). Here is the main result:
Random variable \(X\) has constant rate \(\alpha \in (0, \infty)\) for \((S, \Rta)\) if and only if
As before, let \(\hat F\) denote the reliability function of \(\hat X\) for \((T, \rta)\), so that the reliability function \(F\) of \(X\) for \((S, \Rta)\) is given by \(F(x) = \hat F[\varphi(x)]\) for \(x \in S\). Suppose first that \(X\) has constant rate \(\alpha \in (0, \infty)\) for \((S, \Rta)\). Then \(f = \alpha F\) is a density of \(X\) and hence by , a density \(\hat f\) for \(\hat X\) is given by \[\hat f(t) = \int_{S_t} f(x) \, d\lambda_t(x) = \int_{S_t} \alpha \hat F[\varphi(x)] \, d\lambda_t(x) = \alpha \hat F(t) \beta(t), \quad t \in T\] Hence the rate function of \(\hat X\) for \((T, \rta)\) is \(\hat r = \alpha \beta\). Moreover, by , for \(t \in T\), the conditional density of \(X\) given \(\hat X = t\) is \[f(x \mid t) = \frac{f(x)}{\hat f(t)} = \alpha \frac{F(x)}{\hat f(t)} = \alpha \frac{\hat F(t)}{\hat f(t)} = \frac{1}{\beta(t)}, \quad x \in S_t\] Conversely, suppose that (a) and (b) hold, so in particular a density \(\hat f\) of \(\hat X\) is given by \(\hat f(t) = \alpha \beta(t) \hat F(t)\) for \(t \in T\). Let \(f = \alpha F\) so that \(f(x) = \alpha \hat F([\varphi(x)]\) for \(x \in S\). We need to show that \(f\) is a density of \(X\). For \(A \in \ms S\), \begin{align*} \P(X \in A) &= \E[\P(X \in A \mid \hat X)] = \int_T \hat f(t) \P(X \in A \mid \hat X = t) \, d\mu(t) \\ &= \int_T \hat f(t) \frac{\lambda_t(A \cap S_t)}{\lambda_t(S_t)} \, d\mu(t) = \int_T \alpha \beta(t) \hat F(t) \frac{\lambda_t(A \cap S_t)}{\beta(t)} \\ &= \int_T \alpha \hat F(t) \lambda(A \cap S_t) \, d\mu(t) \end{align*} But on the other hand, \(f(x) = \alpha \hat F(t)\) for \(x \in S_t\) and \(t \in T\), so by , \[\int_A f(x) \, d\lambda(x) = \int_T \int_{A \cap S_t} f(x) \, d\lambda_t(x) \, d\mu(t) = \int_T \alpha \hat F(t) \lambda_t(A \cap S_t) \, d\mu(t)\] Note that if random variable \(X\) has constant rate \(\alpha \in (0, \infty)\) for \((S, \Rta)\) then \(\hat X\) also has constant rate \(\alpha\) for \((T, \rta)\), but relative to the induced measure \(\nu\).
Note that if \(\beta\) is constant on \(T\), then \(X\) has constant rate \(\alpha\) for \((S, \Rta)\) if and only if \(\hat X\) has constant rate \(\alpha \beta\) for \((T, \rta)\).
Let \(H\) denote the entropy operator, and suppose that \(X\) is a random variable in \(S\) with constant rate for \((S, \Rta)\). Then \(H(X) = H(\hat X) + \E[\ln \beta(\hat X)]\)
Let \(X\) be a random variable in \(S\) with probability density function \(f\) and with reliability function \(F\) for \((S, \Rta)\). Let \(\hat X = \varphi(X)\) be the corresponding variable in \(T\) with probability density function \(\hat f\) and with reliability function \(\hat F\) for \((T, \rta)\). As before, we assume that \(\hat f(t) \gt 0\) for almost all \(t \in T\).
Suppose that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on \((S, \Rta)\) associated with \(X\) and let \(\hat Y_n = \varphi(Y_n)\) for \(n \in \N_+\).
Note that for \(u, \, v \in T\) and \(x \in S_u\), \[\int_{S_v} P_n(x, y) \, d\lambda_t(y) = \hat P_n(u, v)\] The next two corollaries give more information about the connections between the random walks \(\bs Y\) and \(\bs{\hat Y}\).
Consider again the random walks \(\bs Y\) on \((S, \Rta)\) and \(\bs{\hat Y}\) on \((T, \rta)\) and fix \(n \in \N_+\).
Note that \begin{align*} \int_{S_{t_1} \times \cdots \times S_{t_n}} g_n(x_1, \ldots, x_n) \, d(\lambda_{t_1} \cdots \lambda_{t_n})(x_1, \ldots, x_n) &= \hat g(t_1, \ldots, t_n), \quad (t_1, \ldots, t_n) \in T^n \\ \int_{S_t} f_n(x) \, d\lambda_t(x) &= \hat f_n(t), \quad t \in T \end{align*}
Consider again the random walks \(\bs Y = (Y_1, Y_2, \ldots)\) on \((S, \Rta)\) and \(\bs{\hat Y} = (\hat Y_1, \hat Y_2, \ldots)\) on \((T, \rta)\).
The results follow directly from .
The following theorem gives the connection for the point processes \(\bs N\) and \(\bs {\hat N}\) associated with the random walks \(\bs Y\) on \((S, \Rta)\) and \(\bs{\hat Y}\) on \((T, \rta)\). Recall that \(N_A = \#\{n \in \N_+: Y_n \in A\}\) for \(A \in \ms S\), and similarly \(\hat N_B = \#\{n \in \N_+: \hat Y_n \in B\}\) for \(B \in \ms T\).
Define the measure \(\eta\) on \((T, \ms T)\) by \(\eta(B) = \E(\hat N_B)\) for \(B \in \ms T\). Then \[\E(N_A) = \int_T \P(X \in A \cap S_t \mid \hat X = t) \, d\eta(t), \quad A \in \ms S\]
Note that \begin{align*} \E(N_A) &= \sum_{n = 0}^\infty \P(X_n \in A) = \sum_{n = 0}^\infty \int_A f_n(x) \, d\lambda(x) \\ &= \sum_{n = 0}^\infty \int_T \int_{A \cap S_t} f_n(x) \, d\lambda_t(x) \, d\mu(t) = \sum_{n = 0}^\infty \int_T \int_{A \cap S_t} f(x \mid t) \hat f_n(t) \, d\lambda_t(x) \, d\mu(t) \\ &= \sum_{n = 0}^\infty \int_T \hat f_n(t) \int_{A \cap S_t} f(x \mid t) \, d\lambda_t(x) \, d\mu(t) = \sum_{n = 0}^\infty \int_T \hat f_n(t) \P(X \in A \cap S_t \mid \hat X = t) \, d\mu(t) \\ &= \int_T \P(X \in A \cap S_t \mid \hat X = t) \, d\eta(t) \end{align*} since \(t \mapsto \sum_{n = 0}^\infty \hat f_n(t)\) is the density of \(\eta\).
In the case that \(X\) has constant rate \(\alpha \in (0, \infty)\) for the graph \((S, \Rta)\), the random walk results simplify significantly since \(f(x \mid t) = 1 / \beta(t)\) for \(x \in S_t\), the density function of the uniform distribution on \(S_t\) for \(t \in T\). Here is a summary of the results, using the same notation as above.
Suppose that \(X\) has constant rate \(\alpha \in (0, \infty)\), and that \(\bs Y = (Y_1, Y_2, \ldots)\) and \(\bs{\hat Y} = (\hat Y_1, \hat Y_2, \ldots)\) are the random walks on \((S, \Rta)\) and \((T, \rta, \mu)\) corresponding to \(X\) and \(\hat X\) respectively. Let \(n \in \N_+\). In the notation of and ,
Suppose that \((S, \ms S, \lambda)\) is a general \(\sigma\)-finite measure space as above, but that the second measure space \((I, \ms P(I), \#)\) is discrete, so that \(I\) is countable, the reference \(\sigma\)-algebra is \(\ms P(I)\) (the collection of all subsets of \(I\)), and the reference measure \(\#\) is counting measure. Once again, \(\varphi\) is a measurable function from \(S\) onto \(I\), so that \(\ms P = \{S_i: i \in I\}\) is a countable, measurable partition of \(S\). We assume that \(\beta(i) = \lambda(S_i) \in (0, \infty)\) for \(i \in I\), and this in turn guarantees assumption with \(\lambda_i\) simply \(\lambda\) restricted to \((S_i, \ms S_i)\) for \(i \in I\). That is,
\[\lambda(A) = \sum_{i \in I} \lambda(A \cap S_i) = \sum_{i \in I} \lambda_i(A \cap S_i), \quad A \in \ms S\]
To complete the setup, \((I, \rta)\) is a discrete graph and \((S, \Rta)\) the corresponding induced graph. The general results in the subsections above simplify, with integrals over \(T\) replaced by sums over \(I\).
The walk function \(u_n\) of order \(n \in \N_+\) for the graph \((S, \Rta)\) is given by \[u_n(x) = \sum_{i_1 \rta i_2 \rta \cdots \rta i_n \rta i} \beta(i_1) \beta(i_2) \cdots \beta(i_n), \quad i \in I, \, x \in S_i\]
Let \(\ms A\) and \(\ms B\) denote the \(\sigma\)-algebras associated with the graphs \((S, \Rta)\) and \((I, \rta)\) respectively. Then \[\ms A = \left\{\bigcup_{j \in J} S_j: J \in \ms B\right\}\]
Define a basic subset of \(S\) to be a set of the form \(\bigcup_{j \in J} S_j\) where the index set \(J\) is a subset of \(I\). The critical facts that we need are
Let \(\ms A_0 = \left\{\bigcup_{j \in J} S_j: J \in \ms B\right\}\). Then from (a)–(c) above, \(\ms A_0\) is a \(\sigma\)-algebra of subsets of \(S\), and from , \(\ms A_0\) contains the right neighbor sets of \((S, \Rta)\). Hence, \(\ms A \subseteq \ms A_0\). Next, let \(\ms B_0 = \left\{J \subseteq I: \bigcup_{j \in J} S_j \in \ms A\right\}\). Then using (a)–(c) and again, \(\ms B_0\) is a \(\sigma\)-algebra of subsets of \(I\) that contains the right neighbor sets of \((I, \rta)\). Hence \(\ms B \subseteq \ms B_0\) and so \(\ms A_0 \subseteq \ms A\).
In particular, if the \(\sigma\) algebra associated with \((I, \rta)\) is the reference \(\sigma\)-algebra \(\ms P(I)\), then the \(\sigma\)-algebra associated with \((S, \Rta)\) is \[\ms A = \left\{\bigcup_{j \in J} S_j: J \subseteq I\right\}\]
If \((I, \rta)\) is stochastic then so is \((S, \Rta)\).
As before, let \(\ms A\) and \(\ms B\) denote the \(\sigma\) algebras associated with \((S, \Rta)\) and \((I, \rta)\), respectively. Suppose that \(P_1\) and \(P_2\) are probability measures on \(\ms A\), with the same reliability function for \((S, \Rta)\). Define \begin{align*} Q_1(J) & = P_1\left(\bigcup_{j \in J} S_j\right), \quad J \in \ms B\\ Q_2(J) & = P_2\left(\bigcup_{j \in J} S_j\right), \quad J \in \ms B \end{align*} Note that the definition makes sense, since \(\ms A = \left\{\bigcup_{j \in J} S_j: J \in \ms B\right\}\) by . Moreover, \(Q_1\) and \(Q_2\) are probability measure on \(\ms B\) with the same reliability function for \((I, \rta)\): To see this, suppose that \(i \in I\) and \(x \in S_i\). If \(J_i\) denotes the neighbor set of \(i\) for \((I, \rta)\) then \(A_x = \bigcup_{j \in J_i} S_j\) is the neighbor set of \(x\) for \((S, \Rta)\). Hence \[Q_1(J_i) = P_1(A_x) = P_2(A_x) = Q_2(J_i)\] Since \((I, \rta)\) is stochastic, \(Q_1 = Q_2\) and it then follows that \(P_1 = P_2\).
Suppose now that \(X\) is a random variable in \(S\) and density function \(f\). The corresponding index variable \(\hat X = \varphi(X)\) takes values in \(I\) and has density function \(\hat f\) given by \[\hat f(i) = \P(\hat X = i) = \P(X \in S_i) = \int_{S_i} f(x) \, d\lambda(x), \quad i \in I\]
Suppose that \((I, \rta)\) is a finite, strongly connected graph. Then there exists a unique constant rate distribution for the induced graph \((S, \Rta)\).
As with the general result in Section 5, this is just the Peron-Frobenius theorem. Define the matrix \(K\) on \(I\) by \(K(i, j) = \beta(i)\) for \(i, \, j \in I\) with \(i \rta j\) (and 0 otherwise). Then \(K\) has a unique positive eigenvalue with multiplicity 1 (the largest eigenvalue) and a corresponding eigenfunction that is strictly positive. The normalized eigenfunction \(\hat f\) is a probability density function on \(I\) that satisfies part (a) in . Then \(f\) defined by \(f(x) = \hat f(i) / \beta(i)\) for \(i \in I\) and \(x \in S_i\) is the probability density function of a constant rate distribution for \((S, \Rta)\).
For the point processes, suppose that \(A \in \ms S\). Then \[\E(N_A) = \sum_{i \in I} \P(X \in A \mid X \in S_i) \E(\hat N_i)\]
Equivalence relations provide one of the simplest examples of induced graphs.
Suppose that the discrete graph is \((I, =)\), so that the only edges are loops at each vertex. The corresponding relation \(\equiv\) on \(S\) is given by \(x \equiv y\) if and only if \(x, \, y \in S_i\) for some \(i \in I\). So as the notation suggests, \(\equiv\) is the equivalence relation associated with the partition \(\ms P = \{S_i: i \in I\}\) (or equivalently the index function \(\varphi\)).
The sets in the partition \(\ms P\) are the equivalence classes and the relation \(\equiv\) is reflexive, symmetric, and transitive. By symmetry, all left and right objects are the same, so we can drop the adjectives. Except for the special symbols for the relations, we use the definitions, notation, and assumptions in the subsections above. Many of the general results simplify considerably.
For the graph \((S, \equiv)\),
Of course \(S = \bigcup_{i \in I} S_i\) but also the relation \(\equiv\) (as a set of ordered pairs) is the set \(\bigcup_{i \in I} S_i^2\), and more generally the set of walks of length \(n \in \N_+\) is the set \(\bigcup_{i \in I} S_i^{n+1}\). For \(n \in \N\), the walk function \(u_n\) for \((S, \equiv)\) is given by \[u_n(x) = \beta^n(i), \quad i \in I, \, x \in S_i \]
So \(u_n = u^n\) for \(n \in \N\) where \(u = u_1\) is the walk function of order 1.
The generating function \(U\) of \((S, \equiv)\) is given by \[U(x, t) = \frac{1}{1 - \beta(i) t}, \quad i \in I, \, x \in S_i, \, |t| \lt 1 / \beta(i)\]
Suppose now that \(X\) is a random variable in \(S\) with density function \(f\). Relative to the graph \((S, \equiv)\),
As usual, let \(\hat X\) denote the corresponding index variable in \(I\).
Suppose again that \(X\) is a random variable in \(S\). Relative to the graph \((S, \equiv)\),
So the generating function is finite on an interval about 0 if the function \(\beta\) is bounded. Every distribution on \(I\) has constant rate 1 for \((I, =)\). Constant rate distributions for \((S, \equiv)\) exist if and only if the equivalence classes have the same size.
A constant rate distribution for \((S, \equiv)\) exists if and only if \(\beta\) is constant on \(I\). In this case, the rate constant is \(\alpha = 1 / \beta\) and the constant rate distribution is uniform on \(S_i\) for each \(i \in I\).
So if \(\beta\) is constant on \(I\) then there is an infinite family of distributions with constant rate \(\alpha = 1 / \beta\), parametrized by \(\hat f\). That is, given a density function \(\hat f\) on \(I\), the function \(f\) on \(S\) defined by \(f(x) = \hat f(i) / \beta\) for \(x \in S_i\) and \(i \in I\) is a density function that has constant rate \(1 / \beta\) for \((S, \equiv)\). Random walks on \((S, \equiv)\) are particularly simple. Once again, suppose that \(X\) is a random variable on \(S\) and that \(\hat X\) is the corresponding index variable.
Suppose that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on \((S, \equiv)\) associated with \(X\), and that \(\bs N = \{N_A: A \in \ms S\}\) is the corresponding point process. Then
The results follows from the results in the subsection on random walks above since the corresponding random walk \(\bs{\hat Y} = (\hat Y_1, \hat Y_2, \ldots)\) on \((I, =)\) is constant: \(\hat Y_n = \hat Y_1\) for \(n \in \N_+\).
Suppose that \(\beta \in (0, \infty)\) is constant on \(I\) and that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on \((S, \equiv)\) associated with a random variable \(X\) that has constant rate \(\alpha = 1 / \beta\).
The density function \(f\) of \(X\) is constant on the equivalence classes, and \(f(x) = \alpha \hat f(i)\) for \(x \in S_i\) and \(i \in I\). The distribution in (b) is a mixture of uniform distributions on \(S_i^n\) for \(i \in I\), with mixture density \(\hat f\).
The following exercises explore some very simple special cases:
Consider the general measure space \((S, \ms S, \lambda)\) where the only set in the partition is \(S\) itself, so that \(\equiv\) is the set \(S^2\) and is the complete reflexive relation. This corresponds to the discrete graph \((I, =)\) where \(I\) is a singleton. Let \(\beta = \lambda(S) \in (0, \infty)\).
At the opposite extreme, suppose that the underlying measure space \((S, \ms P(S), \#)\) is discrete and that the equivalence relation is simply equality \(=\), so that the graphs \((S, =)\) and \((I, =)\) are essentially the same.
Suppose that \(S = [0, \infty)\) with the usual Borel \(\sigma\)-algebra \(\ms S\) and Lebesgue measure \(\lambda\). Let \(S_k = [k, k + 1)\) for \(k \in \N\).
The induced equivalence relation \(\equiv\) corresponds to the discrete graph \((\N, =)\) and the index function \(\varphi\) is given by \(\varphi(x) = \lfloor x \rfloor\) for \(x \in [0, \infty)\).
Complete multipartite graphs are another simple example of induced graphs and are a bit more interesting.
Suppose that the discrete graph is \((I, \ne)\), the complete irreflexive graph on \(I\). The relation \(\lfrta\) on \(S\) induced by \((I, \ne)\) is given by \(x \lfrta y\) if and only if \(x \in S_i\) and \(y \in S_j\) for distinct \(i, \, j \in I\). The graph \((S, \lfrta)\) is the complete multipartite graph associated with the partition \(\ms P = \{S_i: i \in I\}\).
Note that the discrete graph \((I, \ne)\) is the complement of the graph \((I, =)\) in previous subsection on equivalence relations. Note also that the complete multipartite graph can be fromed by joining the null graphs on \(S_i\) over \(i \in I\), in the sense of Section 1. The relation \(\lfrta\) is symmetric and anti-reflexive. In particular, all left and right objects are the same and so we can drop the adjectives. Except for the special symbols used for the relations, we will use the same definitions, notation, and assumptions as in the subsections above.
The walk function of order \(n\) is given by \[u_n(x) = \sum_{i_1 \ne i_2 \ne \cdots \ne i_n \ne i} \beta({i_1}) \beta({i_2}) \cdots \beta({i_n}), \quad i \in I, \, x \in S_i\]
In particular, \[u(x) = \sum_{j \ne i} \beta(j) = \lambda(S) - \beta(i) \quad i \in I, \, x \in S_i\] The walk functions and the generating function have simple, closed forms only in some special cases.
For the graph \((S, \lfrta)\),
Since most of our theory depends on local finiteness of the graph, we make the following assumption:
Assume that \[\lambda(S) = \sum_{i \in I} \beta(i) \lt \infty\] so that \((S, \ms S, \lambda)\) is a finite measure space.
Of course, holds automatically if \(I\) is finite.
Suppose now that \(X\) is a random variable in \(S\). As usual, define the index variable \(\hat X = \varphi(X)\) in \(I\) with density function \(\hat f\) given by \(\hat f(i) = \P(\hat X = i) = \P(X \in S_i)\) for \(i \in I\). Relative to the graph \((I, \ne)\),
Note that \(\hat r(i)\) is the odds ratio of the event \(\{X \in S_i\}\) for \(i \in I\). It follows that the reliability function \(F\) of \(X\) for \((S, \lfrta)\) is given by \(F(x) = 1 - \hat f(i)\) for \(i \in I\) and \(x \in S_i\). The basic equation in part (a) of for a distribution on \((S, \lfrta)\) with constant rate \(\alpha \in (0, \infty)\) is \(\hat f(i) = \alpha \beta(i) [1 - \hat f(i)]\) for \(i \in I\), or equivalently, \[\hat f(i) = \frac{\alpha \beta(i)}{1 + \alpha \beta(i)}, \quad i \in I\] Here is our main result.
There exists a unique constant rate distribution for the complete multipartite graph \((S, \lfrta)\).
The equation for the rate constant and the form of \(f\) follow from . So we just need to show that the equation has a unique solution. Define \(\psi\) on \([0, \infty)\) by \(\psi(\alpha) = \sum_{i \in I} \alpha \beta(i) / [1 + \alpha \beta(i)]\). First we note that \(\psi(\alpha) \lt \infty\) for all \(\alpha \in (0, \infty)\). This is obvious of course if \(I\) is finite. In the case that \(I\) is countably infinite, we can take \(I = \N_+\). Since \(\sum_{i=1}^\infty \beta(i) \lt \infty\), it follows that \(\beta(i) \to 0\) as \(i \to \infty\). Comparing the series \(\sum_{i=1}^\infty \alpha \beta(i) / [1 + \alpha \beta(i)]\) with the convergent series \(\sum_{i=1}^\infty \beta(i)\) we have \[\frac{\alpha \beta(i) / [1 + \alpha \beta(i)]}{\beta(i)} = \frac{\alpha}{1 + \alpha \beta(i)} \to \alpha \text{ as } i \to \infty\] Hence \(\psi(\alpha) = \sum_{i=1}^\infty \alpha \beta(i) / [1 + \alpha \beta(i)] \lt \infty\) for \(\alpha \in [0, \infty)\). Next, since \(\alpha \mapsto \alpha \beta(i) / [1 + \alpha \beta(i)]\) is increasing on \([0, \infty)\) for each \(i\), the function \(\psi\) is also increasing on \([0, \infty)\). Moreover, \(\psi(0) = 0\) and by the monotone convergence theorem, \[\lim_{\alpha \to \infty} \psi(\alpha) = \sum_{i \in I} \lim_{\alpha \to \infty} \frac{\alpha \beta(i)}{1 + \alpha \beta(i)} = \sum_{i \in I} 1 = \#(I) \gt 1\] Also by the monotone convergence theorem, the function \(\psi\) is continuous. By the intermediate value theorem, there exists a unique \(\alpha \in (0, \infty)\) with \(\psi(\alpha) = 1\).
Explicit results are difficult except in a few special cases. The case where the partition sets have the same size is particularly simple.
Suppose that \(\#(I) = k \in \{2, 3, \ldots\}\) and \(\beta_i = \beta \in (0, \infty)\) for \(i \in I\).
Another tractable case is when \(\#(I) = 2\) so that \((I, \ne)\) is simply the (undirected) path on two vertices, and \((S, \lfrta)\) is a complete bipartite graph. For the remainder of this subsection, suppose \(I = \{0, 1\}\), so the partition sets are \(S_0\) and \(S_1 = S_0^c\), with sizes \(\beta_0 = \lambda(S_0)\) and \(\beta_1 = \lambda(S_1)\), respectively.
The walk function \(u_n\) of order \(n \in \N\) for \((S, \lfrta)\) is given as follows for \(x \in S_i\) and \(i \in \{0, 1\}\): \begin{align*} u_n(x) & = \beta_i^{n / 2} \beta_{1 - i}^{n / 2}, \quad n \text{ even} \\ u_n(x) & = \beta_i^{(n - 1) / 2} \beta_{1 - i}^{(n + 1) / 2}, \quad n \text{ odd} \end{align*}
Note that a walk in \((S, \lfrta)\) must alternate between the sets \(S_i\) and \(S_{1 - i}\).
For the complete bipartite graph \((S, \lfrta)\)
Let \(\bs Y = (Y_1, Y_2, \ldots)\) denote the random walk on \((S, \lfrta)\) associated with the constant rate distribution.
So for \(n \in \N_+\), if \(Y_n \in S_0\) then \(Y_{n + 1}\) is uniformly distributed on \(S_1\) and if \(Y_n \in S_1\) then \(Y_{n+1}\) is uniformly distributed on \(S_0\). The star graph in the next exercise has been studied in previous sections of this chapter, but we revisit it becasue it's a simple example of a bipartite graph.
For \(k \in \N_+\), recall that the star of order \(k\) has a central vertex labeled 0 and \(k\) endpoints, labeled from 1 to \(k\). The star of order \(k\) is a complete bipartite graph with \(\beta_0 = 1\) and \(\beta_1 = k\).
For the star of order \(k \in \N_+\),
The app below is a simulation of the constant rate distribution on the star of order \(k\). The parameter \(k\) can be varied with the scrollbar.
The app below is a simulation of the random walk on the star of order \(k\) assoicated with the constant rate distribution. The parameter \(k\) can be varied with the scrollbar.