The various models in this section and the one that follows are a good source of counterexamples and are good illustrations of some of the general theory. For the basic setup, we suppose that \((S, \ms S, \lambda)\) is a measure space (with a measurable diagonal) and that \(S\) has a measurable partition \(\ms P = \{S_n: n \in \N\}\) with \(a_n = \lambda(S_n) \in (0, \infty)\) for each \(n \in \N\) (so in particular, the measure space is \(\sigma\)-finite). Define the index function \(\varphi: S \to \N\) by \(\varphi(x) = n\) if \(x \in S_n\). In the discrete case, \(S\) is countable and \(a_n = \#(S_n) \in \N_+\) is for each \(n \in \N\). Functions on \(\N\) are usually given in subscript form.
In the following subsections, we will consider graphs that are induced, in the sense of Section 1.7, by the standard graphs on \(\N\) studied Section 1 and Section 2. Throughout this section, \(X\) denotes a random variable in \(S\) with density function \(f\) with respect to \(\lambda\). Let \(N = \varphi(X)\) denote the corresponding index variable in \(\N\), so that by \(N = n\) if and only if \(X \in S_n\) for \(n \in \N\). Let \(p\) denote the discrete density of \(N\) so that \[p_n = \P(N = n) = \P(X \in S_n) = \int_{S_n} f(x) \, d\lambda(x), \quad n \in \N\] Recall that if \(\rta\) is a relation on \(\N\) then the induced relation \(\Rta\) on \(S\) is defined by \(x \Rta y\) if and only if \(\varphi(x) \rta \varphi(y)\) for \(x, \, y \in S\). That is, \(x \Rta y\) if and only if \(x \in S_m\) and \(y \in S_n\) for some \(m, \, n \in \N\) with \(m \rta n\). We then let \(F\) denote the reliability function of \(X\) with respect to the graph \((S, \Rta)\) and \(P\) the reliability function of \(N\) with respect to \((\N, \rta)\) so that \[F(x) = \P(x \Rta X) = \P(n \rta N) = P_n, \quad x \in S_n, \, n \in \N\]
As before, let \((\N, \upa)\) denote the covering graph for the standard discrete total order graph \((\N, \le)\). The corresponding induced graph is \((S, \Upa)\) so that \(x \Upa y\) if and only if \(x \in S_n\) and \(y \in S_{n + 1}\) for some \(n \in \N\). Our first goal is to compute the left path functions for \((S, \Upa)\). As with all partitioned graphs, the path functions are constant on the partition sets \(S_n\) for \(n \in \N\).
The path function \(\gamma_m\) of order \(m \in \N\) for \((S, \Upa)\) is given by \[\gamma_m(x) = a_{n - m} a_{n - m + 1} \cdots a_{n - 1}, \quad x \in S_n, \, n \in \{m, m + 1, \ldots\} \] and \(\gamma_m(x) = 0\) otherwise.
This follows from the general theory of partitioned graph. If \(m, \, n \in \N_+\) and \(x \in S_n\) then a path (which is actually a simple path) of length \(m\) ending in \(x\) exists if and only if \(m \le n\). In this case, the path has the form \(x_1 \Upa x_2 \Upa \cdots \Upa x_m \Upa x\) where \(x_j \in S_{n - m + j -1}\) for \(j \in \{1, 2, \ldots, m\}\). The result then follows by the multiplication principle.
In the discrete case, the path function \(\delta_m\) of order \(m \in \N_+\) for the reflexive closure of \((S, \Upa)\) is given by \[\delta_m(x) = \sum_{j=0}^{m \wedge n} \binom{m}{j} a_{n-j} a_{n - j + 1} \cdots a_{n-1}, \quad x \in S_n, \, n \in \N\]
For the reliability functions, note that \(P_n = p_{n+1}\) for \(n \in \N\) and hence \(F(x) = p_{n+1}\) for \(x \in S_n\) and \(n \in \N\). Clearly \(F\) determines the distribution of \(N\) but not \(X\). Here is our main result on the existence of constant rate distributions.
A distribution on \(S\) with constant rate \(\alpha \in (0, \infty)\) for \((S, \Upa)\) exists if and only if \[ \frac{1}{p_0} = \sum_{n=0}^\infty \frac{1}{\alpha^n a_0 a_1 \cdots a_{n-1}} \lt \infty \] In this case, the probability density function \(f\) is given by \[f(x) = \frac{1}{\alpha^n a_0 a_1 \cdots a_n} p_0, \quad x \in S_n, \, n \in \N\]
The constant rate condition is \(f(x) = \alpha F(x)\) for \(x \in S\), so \(f(x) = \alpha p_{n+1}\) for \(x \in S_n\) and \(n \in \N\). Integrating over \(S_n\) gives \(p_n = \alpha a_n p_{n + 1}\) for \(n \in \N\), or equivalently \[p_{n + 1} = \frac{1}{\alpha a_n} p_n, \quad n \in \N\] Solving gives \[p_n = \frac{1}{\alpha^n a_0 a_1 \cdots a_{n - 1}} p_0, \quad n \in \N\] The condition \(\sum_{n = 0}^\infty p_n = 1\) then requires that \[\frac{1}{p_0} = \sum_{n=0}^\infty \frac{1}{\alpha^n a_0 a_1 \cdots a_{n-1}}\] Finally, substituting into \(f(x) = \alpha p_{n + 1}\) for \(x \in S_n\) and \(n \in \N\) gives the result.
The proof of also follows from basic results in Section 1.7 on induced graphs. In particular, a constant rate distribution exists if \(a_n\) is bounded away from 0 for \(n \in \N\).
If \(a_n \ge a\) for all \(n \in \N\) where \(a \in (0, \infty)\) then a distribution with constant rate \(\alpha\) for \((S, \Upa)\) exists for all \(\alpha \in (1 / a, \infty)\).
Since \(a_n \ge a \gt 0\) for all \(n \in \N\) we have \[\sum_{n=0}^\infty \frac{1}{\alpha^n a_0 \cdots a_n} \le \sum_{n=0}^\infty \left(\frac{1}{\alpha a}\right)^n \] The sum converges if \(\alpha a \gt 1\).
In the discrete case, \(a_n \in \N_+\) for each \(n \in \N\) and hence a constant rate distribution exists for every \(\alpha \in (1, \infty)\).
Suppose that \(X\) has constant rate \(\alpha \in (1, \infty)\) for \((S, \Upa)\). Then
So for the graph \((\N, \upa)\), \(N\) has increasing, decreasing, or constant rate if \(a_n\) is increasing, decreasing, or constant in \(n \in \N\), respectively. In the discrete case, note that if \(a_n \in \N_+\) is decreasing in \(n \in \N\) then \(a_n\) is eventually constant in \(n \in \N\). The distributions defined in part (a) are interesting, and include geometric and Poisson distributions as special cases.
Suppose that \(a_n = a \in (0, \infty)\) for all \(n \in \N\) and that \(\alpha \gt 1 / a\). Suppose that \(X\) has constant rate \(\alpha\) for \((S, \Upa)\).
Note that \(p_n = (\alpha a - 1) / (\alpha a)^{n+1}\) for \(n \in \N\), and in particular, \(p_0 = (\alpha a - 1) / \alpha a\).
That is, \(N\) has the geometric distribution on \(\N\), and hence the exponential distribution on \((\N, +)\) with rate \(1 - 1 / \alpha a\). As shown in Section 1 and Section 2, the geometric distribution has constant rate for each of the graphs \((\N, \le)\), \((\N, \lt)\) and \((\N, \upa)\).
Open the simulation of the geometric distribution. Vary the success parameter \(p\) with the scrollbar and note the shape of the probability density function and the value of the parameter \(\alpha a\). Run the simulation and compare the empirical density function to the probability density function.
Suppose that \(a_n = n + 1\) for \(n \in \N\) and that \(\alpha \gt 0\). Suppose again that \(X\) has constant rate \(\alpha\) for \((S, \Upa)\).
Note that \(p_0 = e^{-1/\alpha}\).
That is, \(N\) has the Poisson distribution with parameter \(1 / \alpha\), and has increasing rate for \((\N, \upa)\).
Let's return to the general case and suppose that the condition in holds, so that random variable \(X\) with constant rate \(\alpha \in (0, \infty)\) exists. Consider the random walk \(\bs{Y} = (Y_1, Y_2, \ldots)\) on \((S, \Upa)\) associated with \(X\). So in particular, \(Y_1\) has density function \(f\) and \(Y_m \Upa Y_{m+1}\) for each \(m \in \N_+\).
For \(m \in \N_+\), \(Y_m\) has probability density function \(f_m\) given by \[f_m(x) = \frac{1}{\alpha^{n - m + 1} a_0 \cdots a_{n - m} a_n} p_0, \quad x \in S_n, \, n \in \{m - 1, m , m + 1, \ldots\}\]
From our general theory, \(Y_m\) has density function \(f_m\) given by \[f_m(x) = \gamma_{m - 1}(x) \alpha^n F(x) = \gamma_{m - 1}(x) \alpha^{n - 1} f(x), \quad x \in S\] where \(\gamma_{m - 1}\) is the path function of order \(m - 1\) and \(F\) the reliability function for \((S, \Upa)\). Substituting the results from and gives the result Note that \(f_m(x) = 0\) for \(x \in S_n\) with \(n \lt m - 1\).
Let \(N_m = \varphi(Y_m)\), the index variable of \(Y_m\), for \(m \in \N_+\). Then
We know from the general theory that the constant rate distribution governs the most random way to put points in the graph \((S, \Upa)\), in the sense that given \(Y_{m+1} = x \in S\), the random sequence \((Y_1, Y_2, \ldots, Y_m)\) is uniformly distributed on \[\{(x_1, x_2, \ldots, x_m) \in S^m: x_1 \Upa x_2 \Upa \cdots \Upa x_m \Upa x\}\] For this simple graph, we can say more: given \(Y_m = x \in S_n\) for \(n \in \{m - 1, m, m + 1, \ldots\}\), \(Y_{m - 1}\) is uniformly distribution on \(S_{n - 1}\), \(Y_{m - 2}\) is uniformly distributed on \(S_{n - 2}\), and so forth, with \(Y_1\) uniformly distributed on \(S_{n - m + 1}\).
The rate function \(r_m\) of \(Y_m\) relative to \((S, \Upa)\) for \(m \in \N_+\) is given by \(r_m(x) = 0\) for \(x \in S_n\) with \(n \in \{0, \ldots, m - 2\}\) and \[r_m(x) = \alpha \frac{a_{n - m + 1}}{a_n}, \quad x \in S_n, \, n \in \{m - 1, m, m + 1, \ldots\}\]
Let \(m \in \N_+\). Then \(Y_m\) has reliability function \(F_m\) for \((S, \Upa)\) given by \[F_m(x) = \P(Y_m \in S_{n+1}) = \P(N_m = n + 1) = \frac{1}{\alpha^{n - m + 2} a_0 \cdots a_{n-m+1}}, \quad x \in S_n, \, n \in \{m - 1, m, m + 1, \ldots\}\] \(Y_m\) has rate function \(r_m = f_m / F_m\) for \((S, \Upa)\) and so the result follows from .
As before, let \((\N, \rta)\) denote the reflexive closure of the graph \((\N, \upa)\) so that \(n \rta n\) and \(n \rta n + 1\) for each \(n \in \N\). The graph \((S, \Rta)\) induced by \((\N, \rta)\) is given by \(x \Rta y\) if and only if for some \(n \in \N\), either \(x, \, y \in S_n\) or \(x \in S_n\) and \(y \in S_{n+1}\). Note that \((S, \Rta)\) is not the reflexive closure of the graph \((S, \Upa)\) studied in the last section.
A distribution with constant rate \(\alpha\) for \((S, \Rta)\) exists if and only if \(\alpha a_n \lt 1\) for all \(n \in \N\) and \[c(\alpha) := \sum_{n=0}^\infty \prod_{k=0}^{n-1} \left(\frac{1}{\alpha a_k} - 1\right) \lt \infty\] In this case, the probability density function \(f\) is given by \[f(x) = \frac{1}{c(\alpha)} \left[\prod_{k=0}^{n-1} \left(\frac{1}{\alpha a_k} - 1\right)\right] \frac{1}{a_n}, \quad x \in S_n, \, n \in \N\]
Clearly \(P_n = p_n + p_{n + 1}\) for \(n \in \N\). The condition for a constant rate distribution on \((S, \Rta)\) is \(p_n = \alpha a_n (p_n + p_{n + 1})\) for \(n \in \N\) or equivalently, \[p_{n + 1} = \left(\frac{1}{\alpha a_n} - 1\right) p_n, \quad n \in \N\] Solving gives \[p_n = p_0 \prod_{k=0}^{n-1} \left(\frac{1}{\alpha a_k} - 1\right), \quad n \in \N\] Hence a constant rate distribution exists if and only if \(\alpha a_n \lt 1\) for all \(n \in \N\) and \[c(\alpha) := \sum_{n=0}^\infty \prod_{k=0}^{n-1} \left(\frac{1}{\alpha a_k} - 1\right) \lt \infty\] in which case the discrete density function on \(\N\) is given by \[p_n = \frac{1}{c(\alpha)} \prod_{k=0}^{n-1} \left(\frac{1}{\alpha a_k} - 1\right), \; P_n = \frac{1}{c(\alpha)} \left[\prod_{k=0}^{n-1} \left(\frac{1}{\alpha a_k} - 1\right)\right] \frac{1}{\alpha a_n}; \quad n \in \N\]
In particular, if \(a_n\) is bounded away from 0 and \(\infty\) in \(n \in \N\), in a certain way, then a constant rate distribution exists.
Suppose that \(a \le a_n \le b\) for all \(n \in \N\) where \(0 \lt a \lt b \lt 2 a \lt \infty\). Then a distribution with constant rate \(\alpha\) for the graph \((S, \Rta)\) partitioned by \((\N, \rta)\) exists for all \(\alpha \in \left(\frac{1}{2 a}, \frac{1}{b}\right)\).
First, \(\alpha a_n \lt \frac{1}{b} b = 1\) for all \(n \in \N\). Next, \(\alpha \gt \frac{1}{2 a}\) so \(\alpha \ge \frac{1}{(1 + r)a}\) for some \(r \in (0, 1)\). Hence \(\alpha a_n \ge \frac{1}{(1 + r) a}{a} = \frac{1}{1 + r}\) and so \(\frac{1}{\alpha a_n} - 1 \le r\). Therefore \[\sum_{n=0}^\infty \prod_{k=0}^{n-1} \left(\frac{1}{\alpha a_k} - 1\right) \le \sum_{k=0}^\infty r^n \lt \infty\]
Next we consider the graph \((S, \prec)\) induced by \((\N, \lt)\). So \(x \prec y\) if and only if \(x \in S_m\) and \(y \in S_n\) for some \(m, \, n \in \N\) with \(m \lt n\). As the notation suggests, \(\prec\) is a strict partial order on \(S\), since clearly \(\prec\) is anti-reflexive and transitive. With \(S\) is discrete, the corresponding partial order graph will be studied in Section 4. As usual, we start with the left path functions.
The path function \(\gamma_k\) of order \(k \in \N_+\) for \((S, \prec)\) is given by \[\gamma_k(x) = \sum_{n_1 \lt n_2 \lt \cdots \lt n_k \lt n} a_{n_1} a_{n_2} \cdots a_{n_k}, \quad x \in S_n, \, n \in \N\]
This follows directly from the general theory in Section 1.7.
So the path function does not have a simple closed form, except in special cases.
Suppose that \(a_n = a \in (0, \infty)\) for each \(n \in \N\). Then for \(k \in \N_+\), \[\gamma_k(x) = \binom{n}{k} a^k, \quad x \in S_n, \quad n \in \N\]
A distribution with constant rate \(\alpha \in (0, \infty)\) for \((S, \prec)\) exists if and only if \[\lim_{n \to \infty} \frac{1}{(1 + \alpha a_0) \cdots (1 + \alpha a_n)} = 0\] In this case, the probability density function \(f\) is given by \[f(x) = \alpha \frac{1}{(1 + \alpha a_0) \cdots (1 + \alpha a_n)}; \quad x \in S_n, \, n \in \N\]
Note that \(P\) is related to \(p\) by \(P_n = \sum_{k = n + 1}^\infty p_k\). Equivalently \(p_0 = 1 - P_0\) and \(p_n = P{n - 1} - P_n\) for \(n \in \N_+\). Again, the basic condition for the existence of a constant rate distribution become \(p_n = \alpha a_n P_n\) for \(n \in \N\). Solving we have \[P_n = \frac{1}{(1 + \alpha a_0) \cdots (1 + \alpha a_n)}, \quad n \in \N\] If \(P_n \to 0\) as \(n \to \infty\) then \(P\) is a valid reliability function for \((\N, \lt)\) and the corresponding discrete probability density function \(p\) is given by \[p_n = \frac{\alpha a_n}{(1 + \alpha a_0) \cdots (a + \alpha a_n)}, \quad n \in \N\]
In particular, a constant rate distribution for \((S, \prec)\) exists if \(a_n\) is bounded away from 0 in \(n \in \N\).
If \(a_n \ge a\) for all \(n \in \N\) where \(a \in (0, \infty)\) then a constant rate distribution for for the graph \((S, \prec)\) partitioned by \((\N, \lt)\) exists for all \(\alpha \in (0, \infty)\).
If \(a_n \ge a \gt 0\) for all \(n \in \N\) then \[P_n \le \frac{1}{(1 + \alpha a)^n} \to 0 \text{ as } n \to \infty \]
Suppose next that \((S, \Rrightarrow)\) is the graph induced by \((\N, \le)\), so \(x \Rrightarrow y\) if and only if \(x \in S_m\) and \(y \in S_n\) with \(m \le n\). Note that \((S, \Rrightarrow)\) is not a partial order graph since \(\Rrightarrow\) is not antisymmetric.
A distribution with constant rate \(\alpha \in (0, \infty)\) for \((S, \Rrightarrow)\) exists if and only if \(0 \lt 1 - \alpha a_k \lt 1\) for each \(k \in \N\) and \(\prod_{k=0}^\infty (1 - \alpha a_k) = 0\). In this case the density function \(f\) is given by \[f(x) = \alpha \prod_{k=0}^{n-1} (1 - \alpha a_k), \quad x \in S_n, \, n \in \N\]
The condition for the existence of a distribution with constant rate \(\alpha \in (0, \infty)\) for \((S, \Rrightarrow)\) is \[p_n = \alpha a_n P_n, \quad n \in \N\] Solving gives \[P_n = \prod_{k=0}^{n-1} (1 - \alpha a_k), \; p_n = \alpha a_n \prod_{k=0}^{n-1} (1 - \alpha a_k); \quad n \in \N\] \(P\) is a valid reliability function for \((\N, \le)\) if \(\alpha\) satisfies \(0 \lt 1 - \alpha a_k \lt 1\) for each \(k \in \N\) and \(\prod_{k=0}^\infty (1 - \alpha a_k) = 0\).
In particular, if \(a_n\) is bounded away from 0 and \(\infty\) in \(n \in \N\), then there exist constant rate distributions.
Suppose that \(a \le a_n \le b\) for \(n \in \N\) where \(0 \lt a \lt b \lt \infty\). Then there a distribution with constant rate \(\alpha\) for the graph \((S, \Rrightarrow)\) exists for each \(\alpha \in (0, 1 / b)\).
Since \(a \le a_n \le b\) for \(n \in \N\) we have \(1 - \alpha b \le 1 - \alpha a_n \le 1 - \alpha a\) for \(n \in \N\). But \(0 \lt \alpha \lt 1 / b \lt 1 / a\) so \(1 - \alpha b \gt 0\) and \(1 - \alpha a \lt 1\).