This section continues the setting of Section 4, but with additional assumption that the underlying space is discrete.
Suppose that \(S\) is countably infinite with counting measure \(\#\) as the reference measure on \(\ms P(S)\). Suppose also that \(\varphi: S \to \N\) induces a partition \(\ms P = \{S_n: n \in \N\}\) of \(S\) into finite, nonempty subsets \(S_n = \varphi^{-1}\{n\}\) for \(n \in \N\). Let \(k_n = \#(S_n) \in \N_+\) for \(n \in \N\). Define the strict partial order \(\prec\) on \(S\) by \(x \prec y\) if and only if \(\varphi(x) \lt \varphi(y)\), and let \(\preceq\) denote the corresponding partial order.
That is, for \((x, y) \in S^2\), \(x \prec y\) if and only if \(x \in S_m\), \(y \in S_n\) for some \(m, \, n \in \N\) with \(m \lt n\). The strict partial order graph \((S, \prec)\) is the graph induced by \((\N, \lt)\) as studied in Section 4, but now we are interested in the partial order graph \((S, \preceq)\). So \(x \preceq y\) if and only if \(x = y\) or \(x \in S_m, \, y \in S_n\) for some \(m, \, n \in \N\) with \(m \lt n\). This graph is not an induced graph, but can be constructed as the lexicographic sum of the graphs \((S_n, =)\) over \((\N, \lt)\) as described in Section 1.8. The elements in \(S_0\) are minimal, and in particular, if \(S_0 = \{e\}\) then \(e\) is the minimum element of \(S\). Note that the covering graph of \((S, \preceq)\) is the graph \((S, \Upa)\) induced by \((\N, \upa)\), the covering graph of \((\N, \le)\). In a special case, as we will see below, \((S, \preceq)\) is the graph associated with a positive semigroup.
The walk functions for the partial order graph \((S, \preceq)\) are considerably more complicated that for our previous graphs.
The left walk function \(u_j\) of order \(j \in \N\) for \((S, \preceq)\) is given by \(u_j(x) = v_j(n)\) for \(n \in \N\) and \(x \in S_n\) where \[v_j(n) = \sum_{l = 0}^n \binom{j}{l} \sum\left\{\prod_{i \in J} k_i: J \subseteq \{0, 1, \ldots, n - 1\}, \, \#(J) = l\right\}, \quad n \in \N\]
For a combinatorial proof, note that for \(x \in S_n\) where \(n \in \N\), a path of length \(j\) terminating in \(x\) must visit (in order) the partition sets \(S_j\) for \(j \in J\) where \(J \subseteq \{0, 1, \ldots, n - 1\}\) and with \(\#(J) = l\) for some \(l \in \{0, 1, \ldots n\}\) and with the requisite number of transitions from a state back to iteslf. More precisely, the path would have the following form, where the superscripts refer to transitions from a state to back to itself: \[x_{j_1}^{(i_1)} \prec x_{j_2}^{(i_2)} \prec \cdots \prec x_{j_l}^{(i_l)} \prec x^{(i_{l + 1})}\] where \(x_{j_1} \in S_{j_1}, \, x_{j_2} \in S_{j_2}, \ldots, x_{j_l} \in S_{j_l}\) with nonnegative integers \(j_1 \lt j_2 \lt \cdots \lt j_l \lt n\) and with positive integers \(i_1 + i_2 + \cdots + i_l + i_{l + 1} = j\). The number of ways to pick the distinct states \(\{x_{j_1}, x_{j_2}, \ldots, x_{j_l}\}\) is \(k_{j_1} k_{j_2} \cdots k_{j_l}\) and the number of ways to pick the sequence of repititions \((i_1, i_2, \ldots, i_l, i_{l + 1})\) that sum to \(j\) is \(\binom j l\).
For an induction proof, it helps to have some additional notation. If \(J \subset \N\) is finite, define \(k_J = \prod_{j \in J} k_j\). For \(n \in \N\) and \(l \in \{0, 1, \ldots, n\}\) define \[\ms B_{n, l} = \{J \subseteq \{0, 1, \ldots, n - 1\}: \#(J) = l\}\] Note that \(J_{n,0} = \{\emptyset\}\). Recall that \(u_0(x) = 1\) for \(x \in S\) and \(u_{j + 1}(x) = \sum_{y \preceq x} u_j(y)\) for \(x \in S\) and \(j \in \N\). So we can give a proof by induction on \(j\). The formula is vacuously true when \(j = 0\). Suppose now that the formula holds for a given \(j \in \N\) and \(x \in S\). Then for \(x \in S_n\), \begin{align*} u_{j + 1}(x) &= \sum_{y \preceq x} u_j(y) = u_j(x) + \sum_{m = 0}^{n - 1} \sum_{y \in S_m} u_j(y) = \sum_{l = 0}^n \binom{j}{l} \sum\left\{ k_J: J \in \ms B_{n, l}\right\} + \sum_{m = 0}^{n - 1} k_m \sum_{l = 0}^m \binom{j}{l} \sum \left\{k_J: J \in \ms B_{m, l}\right\} \\ &= \sum_{l = 0}^n \binom{j}{l} \sum \left\{k_J: J \in \ms B_{n, l}\right\} + \sum_{l = 0}^{n - 1} \binom{j}{l} \sum_{m = l}^{n - 1} \sum \left\{k_m k_J: J \in \ms B_{m, l}\right\}= \sum_{l = 0}^n \binom{j}{l} \sum \left\{k_J: J \in \ms B_{n, l}\right\} + \sum_{l = 0}^{n - 1} \binom{j}{l} \sum \left\{k_J: J \in \ms B_{n, l + 1}\right\} \\ &= \sum_{l = 0}^n \binom{j}{l} \sum\left\{k_J: J \in \ms B_{n, l}\right\} + \sum_{l = 1}^n \binom{j}{l - 1} \sum\left\{k_J: J \in \ms B_{n, l}\right\} = 1 + \sum_{l = 1}^n \left[\binom{j}{l} + \binom{j}{l - 1}\right] \sum\left\{k_J: J \in \ms B_{n, l}\right\}\\ & = \sum_{l = 0}^n \binom{j + 1}{l} \sum\left\{k_J: J \in \ms B_{n, l}\right\} \end{align*}
In the notation of , explicitly compute \(v_j(3)\) for \(j \in \{0, 1, 2, 3, 4\}\).
\begin{align*} v_0(3) &= 1 \\ v_1(3) & = 1 + k_0 + k_1 + k_2 \\ v_2(3) & = 1 + 2(k_0 + k_1 + k_2) + (k_0 k_1 + k_0 k_2 + k_1 k_2)\\ v_3(3) & = 1 + 3(k_0 + k_1 + k_2) + 3(k_0 k_1 + k_0 k_2 + k_1 k_2) + k_0 k_1 k_2\\ v_4(3) & = 1 + 4(k_0 + k_1 + k_2) + 6(k_0 k_1 + k_0 k_2 + k_1 k_2) + 4 k_0 k_1 k_2\\ \end{align*}
When the partition sets all have the same size, the walk function simplifies considerably.
Suppose that \(k_n = k \in \N_+\) for \(n \in \N\). In the notation of the function \(v_j\) for \(j \in \N\) is given by \[v_j(n) = \sum_{l = 0}^n \binom j l \binom n l k^l, \quad n \in \N\]
The \(\sigma\)-algebra associated with the graph \((S, \preceq)\) is the reference \(\sigma\)-algebra \(\ms P(S)\).
For \(n \in \N\), the set of right neigbors of \(x \in S_n\) is \(A_x = \{x\} \cup S_{n + 1} \cup S_{n + 2} \cup \cdots \). The \(\sigma\)-algebra associated with \((S, \preceq)\) is \(\ms A = \sigma(\{A_x: x \in S\})\). Suppose first that that \(k_n \ge 2\) for some \(n \in \N\) and that \(x, \, y \in S_n\) are distinct. Then \(A_x \setminus A_y = \{x\}\). Hence \(\{x\} \in \ms A\) for all \(n \in \N\) and \(x \in S_n\) with \(k_n \ge 2\). As a corollary, \(S_n \in \ms A\) for all \(n \in \N\) with \(k_n \ge 2\). Next suppose that \(k_m = 1\) for a single value of \(m \in \N\) so that in particular, \(S_m = \{x\}\) for some \(x \in S\). Then \(\{x\} = S \setminus \left(\bigcup_{n \ne m} S_n\right) \in \ms A\). Finally, suppose that there is a sequence of two or more partition sets that are singletons. Let \(m, \, n\) denote adjacent indices of the sequence of singleton sets, so that in particular, \(m \lt n\), \(S_m = \{x\}\), and \(S_n = \{y\}\) for some (distinct) \(x, \, y \in S\). Then \[\{x\} = A_x \setminus \left(A_y \cup S_{m + 1} \cup \cdots \cup S_{n - 1}\right) \in \ms A\] So now we have \(\{x\} \in \ms A\) for every \(x \in S\).
Next we compute the Möbius function \(M\) for the partial order graph \((S, \preceq)\). Since \(M(x, x) = 1\) for \(x \in S\) and \(M(x, y) = 0\) if \(x \npreceq y\), the only values of interest are \(M(x, y)\) with \(x \in S_m\) and \(y \in S_{m + n}\) with \(m \in \N\) and \(n \in \N_+\). As with the walk functions, it's not surprising that \(M\) is contant for such \((x, y)\).
The Möbius function \(M\) for \((S, \preceq)\) is given by \(M(x, y) = M_{m, m + n}\) for \(x \in S_m\) and \(y \in S_{m + n}\) where \[M_{m, m + n} = \sum_{l = 0}^{n - 1} (-1)^{l + 1} \sum\left\{\prod_{j \in J} k_{m + j}: J \subseteq \{1, \ldots, n - 1\}, \#(J) = l\right\}, \quad m \in \N, \, n \in \N_+\]
Suppose that \(m \in \N\) and that \(x \in S_m\). If \(y \in S_{m + 1}\) then \[M(x, y) = -\sum_{t \in [x, y)} M(x, t) = -M(x, x) = -1\] Similarly, if \(y \in S_{m + 2}\) then \[M(x, y) = -\sum_{t \in [x, y)} M(x, t) = -\left[M(x, x) + \sum_{t \in S_{m + 1}} M(x, t)\right] = -[1 - k_{m + 1}] = -1 + k_{m + 1}\] For \(y \in S_{m + 3}\), \begin{align*} M(x, y) &= - \sum_{t \in [x, y)} M(x, t) = -\left[M(x, x) + \sum_{t \in S_{m + 1}} M(x, t) + \sum_{t \in S_{m + 2}} M(x, t)\right] \\ &= -[1 - k_{m + 1} + k_{m + 2}(-1 + k_{m + 1})] = - 1 + k_{m + 1} + k_{m + 2} - k_{m + 1} k_{m + 2} \end{align*} Continuing in this way gives the result. A more formal induction proof over \(n\) is as follows. For \(n \in \N_+\) and \(j \in \{0, 1, \ldots, n - 1\}\), let \(\ms B_{n, l} = \{J \subseteq \{1, 2, \ldots, n - 1\}: \#(J) = l\}\). As shown above, the formula is true when \(m \in \N\) and \(n = 1\). Assume the formula holds for \(m \in \N\) and for positive integers \(r \le n\) for a given \(n \in \N_+\). Let \(x \in S_m\) and \(y \in S_{m + n + 1}\). Then \begin{align*} M(x, y) &= -\sum_{t \in [x, y)} M(x, t) = -\left[M(x, x) + \sum_{r = 1}^n \sum_{t \in S_{m + r}} M(x, t)\right] \\ &= -\left[1 + \sum_{r = 1}^n k_{m + r} \sum_{l = 0}^{r - 1} (-1)^{l + 1} \sum\left\{\prod_{j \in J} k_{m + j}: J \in \ms B_{r, l}\right\}\right] \\ &= -\left[1 + \sum_{l = 0}^{n - 1} (-1)^{l + 1} \sum_{r = l + 1}^n \sum\left\{k_{m + r} \prod_{j \in J} k_{m + j}: J \in \ms B_{r, l}\right\}\right] \\ &= -\left[1 + \sum_{l = 0}^{n - 1} (-1)^{l + 1} \sum\left\{\prod_{j \in J} k_{m + j}: J \in \ms B_{n + 1,l + 1}\right\}\right] \\ &= -\left[1 + \sum_{l = 1}^n (-1)^l \sum\left\{\prod_{j \in J} k_{m + j}: J \in \ms B_{n + 1, l}\right\}\right] \\ &= \sum_{l = 0}^n (-1)^{l + 1} \sum\left\{\prod_{j \in J} k_{m + j}: J \in \ms B_{n + 1, l}\right\} \end{align*}
Suppose that \(k_n = k \in \N_+\) for \(n \in \N\). In the notation of the function \(M\) is given by \(M_{m, m + n} = \mu_n\) for \(m \in \N\) and \(n \in \N_+\) where \[\mu_n = (-1)^n (k - 1)^n, \quad n \in \N_=\]
Suppose now that \(X\) is a random variable in \(S\) with probability density function \(f\). Let \(N = \varphi(X)\) denote the corresponding index random variable in \(\N\), so that \(N = n\) if and only if \(X \in S_n\) for \(n \in \N\). Thus \(N\) has density function \((p_n: n \in \N)\) given by \[p_n = \P(N = n) = \P(X \in S_n) = \sum_{x \in S_n} f(x), \quad n \in \N\] Let \(F\) denote the reliability function of \(X\) for the graph \((S, \preceq)\). Then \[F(x) = f(x) + \sum_{m = n + 1}^\infty p_m, \quad n \in \N, \, x \in S_n\]
As we will see in the subsection on positive semigorups below, the graph \((S, \preceq)\) is not in general stochastic. That is, a probabilitiy density function \(f\) on \(S\) (defining a probability measure on \((S, \ms P(S))\)) is not in general uniquely determined by the reliability function \(F\) for \((S, \preceq)\). On the other hand, \(f\) can be recovered from \(F\) via Möbius inversion under certain conditions. The following proposition uses the notation in .
Assuming absolute convergence of the series, \[f(x) = F(x) + \sum_{n = 1}^\infty M_{m, m + n} \sum_{y \in S_{m + n}} F(y), \quad m \in \N, \, x \in S_m\]
Let \(m \in \N\) and \(x \in S_m\). By the Möbius inversion formula, again assuming absolute convergence of the series, \begin{align*} f(x) &= \sum_{x \preceq y} M(x, y) F(y) = F(x) + \sum_{x \prec y} M(x, y) F(y) \\ &= F(x) + \sum_{n = 1}^\infty \sum_{y \in S_{m + n}} M(x, y) F(y) = F(x) + \sum_{n = 1}^\infty M_{m, m + n} \sum_{y \in S_{m + n}} F(y) \end{align*}
Of course, we are particularly interested in constant rate distribution for the partial order graph \((S, \preceq)\).
Suppose that \(X\) has constant rate \(\alpha \in (0, 1)\) for \((S, \preceq)\). Then \(X\) has density function \(f\) given by \[f(x) = \frac{\alpha (1 - \alpha)^n}{(1 - \alpha + \alpha k_0) (1 - \alpha + \alpha k_1) \cdots (1 - \alpha + \alpha k_n)}, \quad x \in S_n, \, n \in \N \]
As above, let \(p_n = \P(X \in S_n) = \P(N = n)\) for \(n \in \N\) so that \(n \mapsto p_n\) is the density function of \(N\). Let \(P_n = \sum_{m = n + 1}^\infty p_m\) for \(n \in \N\), so that \(n \mapsto P_n\) is the reliability function of \(N\) for the strict partial order graph \((N, \lt)\). As noted earlier, the reliability function \(F\) of \(X\) for \((S, \preceq)\) is given by \(F(x) = f(x) + P_n\) for \(x \in S_n\) and \(n \in \N\). Hence if \(X\) has constant rate \(\alpha \in (0, 1)\), then \(f = \alpha F\) and so \[F(x) = \frac{1}{1 - \alpha} P_n, \quad x \in S_n, \, n \in \N\] But \(P_n - P_{n + 1} = p_{n + 1}\) for \(n \in \N\) and moreover, \[p_m = \P(X \in S_m) = \sum_{x \in S_m} f(x) = \sum_{x \in S_m} \alpha F(x) = \sum_{x \in S_m} \frac{\alpha}{1 - \alpha} P_m = k_m \frac{\alpha}{1 - \alpha} P_m, \quad m \in \N\] Substituting we have \(P_n - P_{n + 1} = [\alpha k_{n + 1} / (1 - \alpha)] P_{n + 1}\) for \(n \in \N\) or equivalently, \[P_{n + 1} = \frac{1 - \alpha}{1 - \alpha + \alpha k_{n + 1}} P_n, \quad n \in \N\] Solving gives \[P_n = \frac{(1 - \alpha)^n}{(1 - \alpha + \alpha k_1) \cdots (1 - \alpha + \alpha k_n)} P_0, \quad n \in \N\] Finally, \(P_0 = 1 - p_0 = 1 - [\alpha / (1 - \alpha)] P_0\) and so \[P_0 = \frac{1 - \alpha}{1 - \alpha + \alpha k_0}\]
Suppose that \(X\) has constant rate \(\alpha \in (0, 1)\) for \((S, \preceq)\) as in . Let \(N\) denote the index variable of \(X\), so that \(N = n\) if and only if \(X \in S_n\) for \(n \in \N\).
So if \(k_n\) is increasing, or decreasing, or constant in \(n \in \N\), then \(N\) has increasing rate, decreasing rate, or constant rate, respectively, for \((\N, \lt)\). In the last case, of course, \(N\) has a geometric distribution. In the decreasing case, \(k_n\) must eventually be constant in \(n \in \N\).
Part (a) of defines an interesting class of distributions on \(\N\). Here are some special cases:
If \(k_n = k\) for all \(n \in \N\) and \(\alpha \in (0, 1)\) then \(N\) has the geometric distribution on \(\N\) with success parameter \(\alpha k / (1 - \alpha + \alpha k)\),
In this case, \(N\) has constant rate for the graph \((\N, \lt)\), as noted above, but also (with different constants) for the graphs \((\N, \le)\) and \((\N, \upa)\). In particular, if \(k = 1\), \(N\) has the geometric distribution with success parameter \(\alpha\), which of course must be the case since then \((S, \preceq)\) is isomorphic to \((\N, \le)\).
The app below is a simulation of the geometric distribution in . The parameters \(k\) and \(\alpha\) can be varied with the scrollbars.
Suppose that \(k_n = n + 1\) for \(n \in \N\) and \(\alpha \in (0, 1)\).
The app below is a simulation of the distribution in . The parameter \(\alpha\) can be varied with the scrollbar.
Suppose that \(\alpha = \frac 1 2\) and \(k_n \in \N_+\) for \(n \in \N\).
So \(N\) has a telescoping density function.
Suppose that \(k_n = n + 1\) for \(n \in \N\) and \(\alpha = \frac 1 2\).
Consider again the distribution in .
Return to the simulation in exercise and keep the default setting \(\alpha = 0.5\). Note the shape of the probability density function.
In the general lexicographic construction considered above, only one case corresponds to a positive semigroup, and that case corresponds to \(k_0 = 1\) and \(k_n = k \in \N_+\) for \(n \in \N_+\). Here is the construction:
Suppose that \(I\) is a set with \(k \in \N_+\) elements.
The strict partial order \(\prec\) associated with \((S_+, \cdot)\) is given by \((m, i) \prec (n, j)\) if and only if \(m \lt n\) for \((m, i), \, (n, j) \in S_+\). The corresponding partial order \(\preceq\) is the relation associated with \((S, \cdot)\). Moreover, \((S, \preceq)\) is a lexicographic partial order graph as constructed in with \(S_0 = \{e\}\) and \(S_n = \{n\} \times I\) for \(n \in \N_+\). In particular, \(k_0 = 1\) and \(k_n = k\) for \(n \in \N_+\).
So of course, the partial order \(\prec\) on \(S_+\) is the product of the strict order \(\lt\) on \(\N_+\) (the order associated with \((\N_+, +)\)) and the complete relation \(\equiv\) on \(I\) (the relation associated with \((I, \cdot)\)). The product semigroup \((S_+, \cdot)\) and the product graph \((S_+, \prec)\) were mentioned briefly in Section 2.7.
Although we use counting measure \(\#\) as the reference measure on \((S, \ms P(S))\), it is not the only left-invariant measure for \((S, \cdot)\). Recall that every positive measure \(\mu\) on \((I, \ms P(I))\) is trivially left invariant for \((I, \cdot)\) since \(i \cdot B = B\) for \(i \in I\) and \(B \subseteq I\). So with \(\#\) left invariant for \((\N_+, +)\) and \(\mu\) left invariant for \((I, \cdot)\) we have the product measure \(\# \times \mu\) left invariant for \((S_+, \cdot)\).
Recall the power notation for a general positive semigroup: \(x^n = x \cdot x \cdots x\) (\(n\) times) for \(n \in \N_+\) and \(x^0 = e\). For the semigroup here, note that \((1, i)^n = (n, i)\) for \(i \in I\) and \(n \in \N_+\), so we will use the abreviated notation \(i^n\) instead of \((1, i)^n\) (and of course \(i^0 = e\)). With this notation, the base sets are \(S = \{i^n: i \in I, \, n \in \N\}\) and \(S_+ = \{i^n: n \in \N_+\}\), and the elements in \(S_+\) are distinct. The semigroup operation becomes \(i^m \cdot j^n = j^{m + n}\) for \(i, \, j \in I\), \(m \in \N\) and \(n \in \N_+\). The exceptional case of course is \(i^m \cdot j^0 = i^m\) for \(i \in I\) and \(m \in \N\). This notation will greatly simplify the functions on \(S\) that we will study.
Suppose that \(X\) is a random variable in \(S\) and that \(X\) is memoryless for \((S, \cdot)\). Then \(X\) has reliability function \(F\) for \((S, \preceq)\) given by and \(F(i^n) = q^n\) for \(i^n \in S\), where \(q \in (0, 1)\) is a parameter. The probability density function \(f\) of \(X\) is given as follows:
The memoryless property of an reliability function \(F\) for \((S, \cdot)\) is \(F(i^m) F(j^n) = F(j^{m + n})\) for \(i^m, \, j^n \in S_+\). So \(F(i^m) = F(j^{m + n}) / F(j^n)\) and it follows that \(F(i^m)\) is constant in \(i \in I\) for each \(m \in \N_+\). Another application of the memoryless property then implies that \(F(i^n) = q^n\) for \(i^n \in S_+\) where \(q = F(i)\). Of course, \(F(e) = 1\). Now let \(f\) denote the probability density function of \(X\). For \(i^n, \, j^n \in S_+\), \begin{align*} F(i^n) &= f(i^n) + \sum_{m = n + 1}^\infty \sum_{u \in I} f(u^m)\\ F(j^n) &= f(j^n) + \sum_{m = n + 1}^\infty \sum_{u \in I} f(u^m) \end{align*} Since \(F(i^n)\) is constant in \(i \in I\) for each \(n \in \N_+\), it follows that \(f\) has this property as well. So, let \(g(n)\) denote the common value of \(f(i^n)\) for \(i^n \in S_+\) and let \(g(0) = f(e)\). It follows that \[q^n = g(n) + k \sum_{m = n + 1}^\infty g(m), \quad n \in \N\] Subtracting the equation with \(n + 1\) from the equation with \(n\) gives \[(1 - q) q^n = g(n) + (k - 1) g(n + 1)\] Using this result recursively gives the equation in part (b). Finally, the only requirement on \(g(0) = f(e)\) is that \(g(n) \ge 0\) for \(n \in \N\). Solving the various inequalities gives \(f(e) = (1 - q) / (1 - q + k q)\) if \(q \lt 1 / (k - 1)\), and \(0 \le f(e) \le 1 - q\) if \(q \ge 1 / (k - 1)\).
Suppose that \(X\) is a random variable in \(S\) with probability density function \(f\) given by \[f(i^n) = \frac{(1 - q) q^n }{1 - q + k q}, \quad i^n \in S \] where \(q \in (0, 1)\) is a parameter. Then \(X\) has an exponential distribution for \((S, \cdot)\). The reliability function \(F\) of \(X\) for \((S, \preceq)\) is given by \(F(i^n) = q^n\) for \(i^n \in S\), and \(X\) has constant rate \((1 - q) / (1 - q + k q)\) for \((S, \preceq)\).
In the case \(q \lt 1 / (k - 1)\), the only memoryless distribution is the exponential distribution. In the case \(q \ge 1 / (k - 1)\), the exponential probability density function corresponds to choosing \(f(e) = (1 - q) /(1 - q + k q)\) in part (b) of . But of course, this choice of \(f(e)\) is not the only possible one. Indeed, any choice of \(f(e)\) with \(0 \le f(e) \le 1 - q\) will lead to a probability density function whose corresponding reliability function \(F\) is \(F(i^n) = q^x\) for \(i^n \in S\), corresponding to a memoryless distribution. In particular, the reliability function does not uniquely specify the distribution, and there are probability distributions that are memoryless but not exponential. The following exercise explores a concrete example.
Suppose that \(k = 4\) and that \(q = \frac 1 2\), so that all of the distributions defined by in part (b) of are memoryless for \((S, \cdot)\), with reliability function \(F\) given by \(F(i^n) = \left(\frac 1 2 \right)^n\) for \(i^n \in S\). Find the probability density function \(f\) for each of the following choices of \(f(e)\):
On the other hand, for this positive semigroup, the constant rate property implies the full exponential property.
Suppose again that \(X\) is a random variable in \(S\). If \(X\) has constant rate for \((S, \preceq)\) then \(X\) is exponential for \((S, \cdot)\).
Suppose that \(F\) is the reliability function of a distribution which has constant rate \(\alpha \in (0,\,1)\) for \((S, \preceq)\). Then from \[F(i^n) = \frac{(1 - \alpha)^n}{(1)(1 - \alpha + \alpha k)^n} = \left(\frac{1 - \alpha}{1 - \alpha + \alpha k}\right)^n, \quad i^n \in S\] So the distribution is memoryless as well, and hence exponential for \((S, \cdot)\).
So to review, every distribution with constant rate for \((S, \preceq)\) is memoryless (and hence exponential) for \((S, \cdot)\), but conversely, there are memoryless distributions that do not have constant rate. Of course, if \(k = 1\) then \((S, \cdot)\) is isomorphic to \((\N, +)\) and so the constant rate distribution is the geometric distribution with rate \(\alpha\).
We continue with the semigroup \((S, \cdot)\) in the last subsection (with the compact notation) to illustrate some of the results in Section 2.8 on quotient spaces.
Fix \(j \in I\) and let \(T_j = \{j^n: n \in \N\}\) so that \((T_j, \cdot)\) is the complete sub-semigroup of \((S, \cdot)\) generated by the element \(j\). The corresponding quotient space is \(S / T_j = \{e\} \cup (I - \{j\})\). The basic assumptions are satisifed, so that \(i^n \in S\) has a unique factoring over \(T_j\) and \(S / T_j\). Specifically, the non-trivial factoring is \[i^n = j^{n - 1} \cdot i, \quad i^n \in S_+\]
If \(X\) is a random variable in \(S\) then \(X\) has a unique decomposition \(X = j^N Y\) where \(N \in \N\) and \(Y \in S / T_j\).
Suppose that \(X\) is a random variable in \(S\) with probability density function \(f\). Then the probability density function of \((N, Y)\) is given by \begin{align*} \P(N = n, Y = e) &= f(j^n), \quad n \in \N \\ \P(N = n, Y = i) &= f(i^{n + 1}), \quad n \in \N, \, i \in I - \{j\} \end{align*}
Suppose that \(X\) has the exponential distribution given in . Then
The fact that \(N\) has an exponential distribution on \((\N, +)\) and that \(N\) and \(U\) are independent follows from the general theory in Section 2.8. The particular details in this theorem follow from the density function of \((N, U)\) and standard techniques.
\begin{align*} \P(N = n, Y = e) &= f(j^n) = \frac{(1 - q) q^n}{1 - q + k q}, \quad n \in \N \\ \P(N = n, Y = i) &= f(i^{n + 1}) = \frac{(1 - q) q^{n + 1}}{1 - q + k q}, \quad n \in \N, \, i \in I - \{j\} \end{align*}Our next discussion gives a counterexample about conditional exponential distributions. We allow the set \(I\) to be countably infinite, and more generally, \(T_x = \{x^n: n \in \N\}\) for \(x \in S\) so that \((T_x, \cdot)\) is the complete sub-semigroup generated by \(x\).
Let \(p_i \in (0, 1)\) for each \(i \in I\) and assume that \(\sum_{i \in I} (1 - p_i) / p_i \lt \infty\). Suppose that random variable \(X \in S\) has probability density function \(f\) given by \(f(i^n) = d (1 - p_i)^n\) for \(i^n \in S\) where \[d = \frac{1}{1 + \sum_{i \in I} (1 - p_i) / p_i} \] Then the conditional distribution of \(X\) given \(X \in T_x\) is exponential for \((T_x, \cdot)\) for each \(x \in S\), but \(X\) does not have a memoryless distribution for \((S, \cdot)\) unless \(I\) is finite and \(p_i\) is constant in \(i \in I\).
First we verify that \(f\) is a valid density function on \(S\): \[\sum_{x \in S} f(x) = f(e) + \sum_{i \in I} \sum_{n = 1}^\infty f(i^n) = d + d \sum_{i \in I} \sum_{n = 1}^\infty (1 - p_i)^n = d\left[1 + \sum_{i \in I} (1 - p_i) / p_i \right] = 1\] by definition of \(d\). Next note that need only prove the theorem when \(x = i \in I\), since if \(x = i^n \in S_+\) then \((T_x, \cdot)\) is a sub-semigroup of \((T_i, \cdot)\). Towards that end, \[\P(X \in T_i) = \sum_{n = 0}^\infty f(i^n) = d + d \sum_{n = 1}^\infty (1 - p_i)^n = d \left[1 + (1 - p_i) / p_i\right] = d / p_i\] Hence \[\P(X = i^n \mid X \in T_i) = \frac{f(i^n)}{\P(X \in T_i)} = p_i (1 - p_i)^n, \quad n \in \N\] which is the geometric distribution with rate \(p_i\) under the isomorphism \(i^n \mapsto n\) for \(n \in \N\). But clearly \(X\) does not have a memoryless distribution for \((S, \cdot)\) unless \(S\) is finite and \(p_i = p \in (0, 1)\) for \(i \in I\). In this case, \(d = p / [p + \#(I) (1 - p)]\) and so \(f(i^n) = d (1 - p)^n\) for \(i^n \in S\), which agrees with the exponential distribution in .
Suppose that \(X\) has the distribution in . Fix \(j \in I\) and consider the decomposition \(X = j^N Y\) where \(N \in \N\) and \(Y \in S / T_j\). Then \((N, Y)\) has probability density function defined as follows: \begin{align*} \P(N = n, Y = e) &= \frac{(1 - p_j)^n}{{1 + \sum_{y \in I} (1 - p_y) / p_y}}, \quad n \in \N \\ \P(N = n, Y = i) &= \frac{(1 - p_i)^{n + 1}}{{1 + \sum_{y \in I} (1 - p_y) / p_y}}, \quad n \in \N, \, i \in I - \{j\} \end{align*}
First \[\P(N = n, Y = e) = \P(X = j^n) = d(1 - p_j)^n, \quad n \in \N\] Next, \[\P(N = n, Y = i) = \P(X = i^{n + 1}) = d(1 - p_i)^{n + 1}, \quad n \in \N, \, i \in I - \{j\}\]
Suppose again that \(X\) has the distribution in . Fix \(j \in I\) and consider the decomposition \(X = j^N Y\) where \(N \in \N\) and \(Y \in S / T_j\). Then
In particular, note from the last two results that \(N\) and \(Y\) are dependent.