If \(r(x) = \alpha\) for \(x \in S\) then from the definition, the cumulative rate function \(R_n\) of order \(n \in N_+\) is given by \(R_n(x) = \alpha^n \gamma_n(x)\) for \(x \in S\).

Note first that since \(F\) is positive, \(\mu\) is a \(\sigma\)-finite positive measure. By definition, \(\mu\) has density function \(1 / F\) with respect to the distribution of \(X\), and hence the distribution of \(X\) has density function \(F\) with respect to \(\mu\). That is, \(\P(X \in A) = \int_A F(x) d \mu(x)\) for \(A \in \ms S\).

Recall that if \(f\) is a probability density function then the corresponding reliability function for \((S, \rta)\) is \(F = L f\).

This is just the Peron-Frobenius theorem in disguise. The adjacency matrix \(L\) has unique positive eigenvalue with multiplicity 1 (the largest eigenvalue), and a corresponding eigenfunction that is strictly positive.

Suppose that \(x \rta x\) and that \(X\) has density function \(f\) and has reliability function \(F\) for \((S, \rta)\). If \(X\) has constant rate \(\alpha \in (0, \infty)\) then \[f(x) = \alpha F(x) = \alpha \left[f(x) + \sum_{x \rta y, \, y \ne x} f(y) \right]\] By the support assumption, \(F(x) \gt 0\) and hence \(f(x) \gt 0\). Rearranging the displayed equation we have \[(1 - \alpha) f(x) = \alpha \sum_{x \rta y, \, y \ne x} f(y)\] If \(\alpha \gt 1\), the left side is negative, but of course the right side is nonnegative.

Recall that if \(f\) and \(g\) are probability density functions with corresponding reliability functions \(F\) and \(G\) for \((S, \rta)\), respectivley, and if \(p \in (0, 1)\), then the density function \(h = p f + (1 - p) g\) has reliability function \(H = p F + (1 - p) G\). In this case, \(f = \alpha F\) and \(g = \alpha G\) so \[h = p f + (1 - p) g = p \alpha F + (1 - p) \alpha G = \alpha [p F + (1 - p) G] = \alpha H\]

Suppose that \(\lambda(S) \lt \infty\) and let \(f(x) = 1 / \lambda(S)\) for \(x \in S\) so that \(f\) is the density of the uniform distribution on \(S\). Then the reliability function is \[F(x) = \int_{x \rta y} \frac{1}{\lambda(S)} \, d\lambda(y) = \frac{\lambda\{y \in S: x \rta y\}}{\lambda(S)} = \frac{k}{\lambda(S)}\] and so \(f = \frac{1}{k} F\).

Note that there is a loop at \(x\) and this is the only edge from \(x\). There is a loop at \(y\) and at least one other edge from \(y\) (to \(w\)). Suppose \(f\) is a probability density function on \(S\) with constant rate, and let \(F\) denote the reliability function of \(f\) for \((S, \rta)\). Then \(F(x) = f(x)\) so the rate constant must be 1. But then \(f(y) = F(y)\) and also \(F(y) \ge f(y) + f(w)\). So we have \(f(w) = F(w) = 0\) and this contradicts the support assumption that \(F(t) \gt 0\) for all \(t \in S\).

Let \(f\) denote the density function of \(X\). Let \(F\) denote the reliability function of \(X\) for \((S, \preceq)\) and for \(n \in \N\), let \(G_n\) denote the reliability function of \(X\) for \((S, \upa^n)\).

1. We prove this by induction on \(n\). Note that \(a_1 = 1\), so the result is true by assumption when \(n = 1\). The result is trivial for \(n = 0\) since \(G_0(x) = f(x)\) for \(x \in S\). Assume that the result holds for a given \(n \in \N\). Then \begin{align*} G_{n+1}(x) &= \sum_{x \upa^{n+1}y} f(y) = \frac{1}{a_{n+1}} \sum_{x \upa u} \sum_{u \upa^n y} f(y) = \frac{1}{a_{n+1}} \sum_{x \upa u} G_n(u) \\ &= \frac{1}{a_{n+1}} \sum_{x \upa u} \frac{1}{\beta^n a_1 \cdots a_n} f(u) = \frac{1}{\beta^n a_1 \cdots a_{n+1}}G_1(x) = \frac{1}{\beta^{n+1} a_1 \cdots a_{n+1}} f(x), \quad x \in S \end{align*}
2. Recall that since \((S, \preceq)\) is uniform, \(F = \sum_{n=0}^\infty G_n\). Hence \[F(x) = \sum_{n=0}^\infty G_n(x) = \sum_{n=0}^\infty \frac{1}{\beta^n a_1 \cdots a_n} f(x) = f(x) \sum_{n=0}^\infty \frac{1}{\beta^n a_1 \cdots a_n}, \quad x \in S\]

This is an immediate consequence of the result in Section 3 since the rate function of the conditional distribution for \((A_x, \rta)\) is the restriction of the rate function of \(X\) to \(A_x\).

By assumption, \(f = \alpha F\) is a density of \(X\), so \[\int_S (g L^n)(x) F(x) \, d\lambda(x) = \frac{1}{\alpha} \int_S (g L^n)(x) f(x) = \frac{1}{\alpha} \E[(g L^n)(X)]\] Hence from the basic moment result \[\frac{1}{\alpha} \E[(g L^n)(X)] = \E[(g L^{n+1})(X)]\] The result then follows since \(L^0 = I\), the identity kernel.

This follows from with \(g = \bs 1\).

Recall that the graph \((S, \rta)\) supports the distribution of \(X\).

1. If \(\lambda\{x \in S: \gamma(x) = \infty\} > 0\) then \(\P[\gamma(X) = \infty] > 0\) and hence \(\E[\gamma(X)] = \infty\). This contradicts .
2. If \(\gamma(x) = c\) for almost all \(x \in S\) then \(\P[\gamma(X) = c] = 1\) so \(\E[\gamma(X)] = \E[\gamma(X); \gamma(X) = c] = c\). Hence \(c = 1 / \alpha\).

Recall that \(\Lambda(t) = \E[\Gamma(X, t)]\) where \(\Gamma(x, t) = \sum_{n=0}^\infty \gamma_n(x) t^n\) is the generating function of \((S, \rta)\). Hence using and Fubini's theorem we have \[\Lambda(t) = \E[\Gamma(X, t)] = \sum_{n=0}^\infty \E\left[\gamma_n(X)\right] t^n = \sum_{n=0}^\infty (t / \alpha)^n = \frac{1}{1 - t / \alpha}, \quad |t| \lt \alpha\]

Suppose that \(X\) has constant rate \(\alpha\), so that \(f = \alpha F\) is a density of \(X\). Suppose that \(Y\) is a random variable taking values in \(S\), with density function \(g\). From the general entropy inequality in Section 3 in we have \begin{align*} H(Y) &= -\int_S g(x) \ln[g(x)] d \lambda(x) \le -\int_S g(x) \ln[f(x)] d \lambda(x) \\ &= -\int_S g(x) \left(\ln \alpha + \ln[F(x)]\right) d \lambda(x) \\ & = -\ln \alpha - \int_S g(x) \ln[F(x)] d \lambda(x) = -\ln \alpha - \E\left(\ln[F(Y)]\right) \\ & = -\ln \alpha - \E\left(\ln[F(X)]\right) \end{align*} Of course, the entropy of \(X\) achieves the upper bound.

Recall from Section 4 that \[P^n(x, y) = \frac{f(y)}{F(x)} R^{(n)}(x, y), \quad (x, y) \in S^2\] where \[R^{(n)}(x, y) = \int_{x \rta x_1 \rta \cdots \rta x_{n-1} \rta y} r(x_1) \cdots r(x_{n-1}) d\lambda^n(x_1, \ldots, x_{n-1}), \quad (x, y) \in S^2\] Since \(X\) has constant rate \(\alpha\), \(f(x) = \alpha F(x)\) and \(r(x) = \alpha\) for \(x \in S\). Hence \[R^{(n)}(x, y) = \alpha^{n-1} \lambda^{n-1}\{(x_1, \ldots, x_{n-1}): x \rta x_1 \rta \cdots \rta x_{n-1} \rta y\} = \alpha^{n-1} L^n(x, y)\]

The results follow easily from the constant rate property.

1. This follows since \(r(x) = \alpha\) and \(f(x) = \alpha F(x)\) for \(x \in S\).
2. This follows since \(R_n(x) = \alpha^n \gamma_n(x)\) and again \(f(x) = \alpha F(x)\) for \(x \in S\). That is, \(X\) has constant average rate \(\alpha^n\) of order \(n\).
3. The conditional distribution reduces to \[h(x_1, x_2, \ldots x_n \mid x) = \frac{1}{\gamma_n(x)}, \quad x_1 \rta x_2 \rta \cdots \rta x_n \rta x\]

From the general theory in Section 4, \(f F\) is invariant for \(\bs Y\), where \(f\) is the density function of \(X\). Since \(X\) has constant rate \(\alpha\) it follows that \(f = \alpha F\) and hence \(\alpha F^2\) is invariant for \(\bs Y\). But then \(F^2\) is also invariant for \(\bs Y\). The normalizing constant is \[c := \int_S F^2(x) \, d\lambda(x) = \frac{1}{\alpha} \E[F(X)]\] Note that \(c \le 1\) since \(F \le 1\) so \(h = F^2 / c\) is an invariant probability density function for \(X\)

Recall that \(\E(N_A) = \E[V(X); X \in A]\) where \(V(x) = \sum_{n = 0}^\infty R_n(x)\) for \(x \in S\). Since \(X\) has constant rate \(\alpha\) we have \[V(x) = \sum_{n=0}^\infty R_n(x) = \sum_{n = 0}^\infty \alpha^n \gamma_n(x) = \Gamma(x, \alpha), \quad x \in S\]

As usual, let \(\gamma_n\) denote the path function of \((S, \rta)\) of order \(n \in \N\). Then \begin{align*} g(x) &= \E[f_N(x)] = \sum_{n = 1}^\infty p (1 - p)^{n - 1} f_n(x) = \sum_{n = 1}^\infty p (1 - p)^{n - 1} \alpha^n \gamma_{n - 1}(x) F(x) \\ &= \alpha p F(x) \sum_{n = 1}^\infty [\alpha (1 - p)]^{n - 1} \gamma_{n - 1}(x) = \alpha p F(x) \Gamma[x, \alpha (1 - p)] \\ &= p \Gamma[x, \alpha (1 - p)] f(x), \quad x \in S \end{align*}

For any probability distribution on \(S\), the reliability function \(F\) for \((S, \equiv)\) is the constant function 1. Note also that \((S, \equiv)\) is regular of degree \(\lambda(S)\), so applies.

Suppose that \(f\) is a probability density function on \(S\). The corresponding reliability function \(F\) is given by \[F(x) = \int_{S - \{x\}} f(y) \, d\lambda(y) = 1 - \int_{\{x\}} f(y) \, d\lambda(y) = \lambda\{x\} f(x) = c f(x) \] So the condition for the distribution defined by \(f\) to have constant rate \(\alpha \in (0, \infty)\) is \(f(x) = \alpha [1 - c f(x)]\) for \(x \in S\) or equivalently, \(f(x) = \alpha / (1 + \alpha c)\). If \(\lambda(S) \lt \infty\) then \(\alpha = 1 / [\lambda(S) - c]\) and \(f\) is the density of the uniform distribution on \(S\). If \(\lambda(S) = \infty\) then no choice of \(\alpha \in (0, \infty)\) makes \(f\) a valid density function. Note also that \((S, \ne)\) is regular of degree \(\lambda(S) - c\), so applies.

If \(f\) is a probability density function on \(S\), then trivially, the corresponding reliability function for \((S, =)\) is \(F = f\).

1. The rate constant is \(\alpha = 2 / (1 + \sqrt{17})\), the reciprocal of the largest eigenvalue.
2. The density function \(f\) and reliability function \(F\) of \(X\) are given by \begin{align*} f(1) &= f(4) = \frac{\sqrt{17} - 3}{4}, \quad f(2) = f(3) = \frac{5 - \sqrt{17}}{4} \\ F(1) &= F(4) = \frac{7 - \sqrt{17}}{4}, \quad F(2) = F(3) = \frac{\sqrt{17} - 3}{2} \end{align*}

1. The transition matrix \(P\) is given by \begin{align*} P(1, 2) &= P(1, 3) = P(4, 2) = P(4, 3) = \frac{9 = \sqrt{17}}{16} \\ P(1, 4) &= P(4, 1) = \frac{2}{1 + \sqrt{17}} \\ P(2, 1) &= P(2, 4) = P(3, 1) = P(3, 4) = \frac 1 2 \end{align*}
2. The density function \(f_n\) of \(Y_n\) is given by \begin{align*} f_n(1) &= f_n(4) = -\left(1 - \frac{4}{\sqrt{17}}\right) \left(\frac{1 - \sqrt{17}}{1 + \sqrt{17}}\right)^{n-1} + \frac{1}{4}\left(1 + \frac{1}{\sqrt{17}}\right) \\ f_n(2) &= f_n(3) = \left(1 - \frac{4}{\sqrt{17}}\right) \left(\frac{1 - \sqrt{17}}{1 + \sqrt{17}}\right)^{n-1} + \frac{1}{4}\left(1 - \frac{1}{\sqrt{17}}\right) \end{align*}
3. The limiting values are \begin{align*} \lim_{n \to \infty} f_n(1) &= \lim_{n \to \infty} f_n(4) = \frac{1}{4}\left(1 + \frac{1}{\sqrt{17}}\right) \\ \lim_{n \to \infty} f_n(2) &= \lim_{n \to \infty} f_n(3) = \frac{1}{4}\left(1 - \frac{1}{\sqrt{17}}\right) \end{align*} Moreover, \(\lim_{n \to \infty} f_n\) is \(f F\) normalized and hence is the invariant density function.

1. The rate constant is \(\alpha = 2^{-1/3}\), the reciprocal of the largest eigenvalue.
2. The density function \(f\) and the reliability function \(F\) of \(X\) are given by \begin{align*} f(1) &= \frac{2^{1/3}}{1 + 2^{1/3} + 2^{2/3}}, \; f(2) = f(3) = \frac{2^{-1/3}}{1 + 2^{1/3} + 2^{2/3}}, \; f(4) = \frac{1}{1 + 2^{1/3} + 2^{2/3}} \\ F(1) &= \frac{2^{2/3}}{1 + 2^{1/3} + 2^{2/3}}, \; F(2) = F(3) = \frac{1}{1 + 2^{1/3} + 2^{2/3}}, \; F(4) = \frac{2^{1/3}}{1 + 2^{1/3} + 2^{2/3}} \end{align*}

1. The transition probability matrix \(P\) is given by \[P(1, 2) = P(1, 3) = \frac{1}{2}, \, P(2, 4) = P(3, 4) = P(4, 1) = 1 \]
2. The density function \(f_n\) of \(Y_n\) is given as follows: If \(n = 0 \mod 3\) then \(f_n = f\). If \(n = 1 \mod 3\) then \(f_n(x) = 2^{-1 / 3} f(x)\) for \(x \in \{1, 2, 3\}\) and \(f_n(4) = 2^{2 / 3} f(4)\). If \(n = 2 \mod 3\) then \(f_n(x) = 2^{1 / 3} f(x)\) for \(x \in \{1, 4\}\) and \(f_n(x) = 2^{-2 / 3} f(x)\) for \(x \in \{2, 3\}\).
3. The invariant probability density function \(h\) is given by \(h(1) = h(4) = 1 / 3\) and \(h(2) = h(3) = 1 / 6\).
4. The random walk \(\bs Y\) is periodic with period 3.

1. The rate constant is \(\alpha = 2 / (1 + \sqrt{13})\), the reciprocal of the largest eigenvalue.
2. The density function \(f\) and reliability function \(F\) of \(X\) are given by \begin{align*} f(1) &= \frac{5 - \sqrt{13}}{6}, \quad f(2) = f(3) = \frac{\sqrt{13} - 2}{6}, \quad f(4) = f(5) = \frac{5 - \sqrt{13}}{12}\\ F(1) &= \frac{\sqrt{13} - 2}{3}, \quad F(2) = F(3) = \frac{11 - \sqrt{13}}{12}, \quad F(4) = F(5) = \frac{\sqrt{13} - 2}{6} \end{align*}

1. The transition probabiity matrix \(P\) is given by \begin{align*} P(1, 2) &= P(1, 3) = \frac{1}{2} \\ P(2, 1) &= P(3, 1) = \frac{10 - 2 \sqrt{13}}{11 - \sqrt{13}}, \, P(2, 3) = P(3, 2) = \frac{2}{1 + \sqrt{13}}, \, P(2, 4) = P(3, 5) = \frac{2 \sqrt{13} - 4}{5 \sqrt{13} - 2} \\ P(4, 2) &= P(5, 3) = 1 \end{align*}
2. The density function \(f_n\) of \(Y_n\) is given by \begin{align*} f_n(1) &= \left(\frac{14}{3 \sqrt{13}} - \frac{4}{3}\right)\left(\frac{1 - \sqrt{13}}{1 + \sqrt{13}}\right)^{n-2} + \frac{1}{3}\left(1 - \frac{1}{\sqrt{13}}\right) \\ f_n(2) = f_n(3) &= \left(1 - \frac{7}{2 \sqrt{13}}\right) \left(\frac{1 - \sqrt{13}}{1 + \sqrt{13}}\right)^{n-2} + \frac{1}{4}\left(1 + \frac{1}{\sqrt{13}}\right) \\ f_n(4) = f_n(5) &= \left(-\frac{1}{3} + \frac{7}{6 \sqrt{13}}\right) \left(\frac{1 - \sqrt{13}}{1 + \sqrt{13}}\right)^{n-2} + \frac{1}{12}\left(1 - \frac{1}{\sqrt{13}}\right) \end{align*}
3. The limiting values are \begin{align*} \lim_{n \to \infty} f_n(1) &= \frac{1}{3}\left(1 - \frac{1}{\sqrt{13}}\right) \\ \lim_{n \to \infty} f_n(2) = \lim_{n \to \infty} f_n(3) &= \frac{1}{4}\left(1 + \frac{1}{\sqrt{13}}\right) \\ \lim_{n \to \infty} f_n(4) = \lim_{n \to \infty} f_n(5) &= \frac{1}{12}\left(1 - \frac{1}{\sqrt{13}}\right) \end{align*} Moreover, \(\lim_{n \to \infty} f_n\) is \(f F\) normalized and hence is the invariant density function.

As noted in Section 3 the largest eigenvalue of the adjacency matrix \(L\) is \(1 + \sqrt{k + 1}\), and moreover a corresponding eigenfunction \(g\) is given by \(g(0) = \sqrt{k + 1} - 1\) and \(g(x) = 1\) for \(x \in \{1, 2, \ldots, k\}\). Hence rate constant is \[\alpha = \frac{1}{1 + \sqrt{k + 1}} = \frac{\sqrt{k + 1} - 1}{k}\] The corresponding density function \(f\) is obatined by normalizing \(g\). Since \(c = \sum_{x \in S} g(x) = k - 1 + \sqrt{k + 1}\), \begin{align*} f(0) & = \frac{\sqrt{k + 1} - 1}{k - 1 + \sqrt{k + 1}}\\ f(x) & = \frac{1}{k - 1 + \sqrt{k + 1}}, \quad x \in \{1, 2, \ldots, k\} \end{align*}

From Example , \(\alpha = 1 / 3\) and \(f(x) = 1 / 4\) for \(x \in \N_3\). But we already knew this since \((\N_3, \lfrta)\) is regular with degree \(3\).

From Example , \(\alpha = \left(\sqrt{5} - 1\right) / 4 \approx 0.309\). For the constant rate density function, \(f(0) = \sqrt 5 - 2\) and \(f(x) = \left(3 - \sqrt 5\right) / 4\) for \(x \in \{1, 2, 3, 4\}\).

Let \(p_k\) denote the common value of \(f_k(j)\) for \(j \in \{1, 2, \ldots, k\}\) as given above. So \(f(0) = 1 - k p_k\). Then for \(x \in [0, 1]\), \begin{align*} \P(X_k / k \le x) & = \sum_{j = 0}^k \bs{1}(j / k \le x) f_k(j) = f_k(0) + p_k \sum_{j = 1}^k \bs{1}(j / k \le x) \\ & = f_k(0) + k p_k \frac{1}{k} \sum_{j = 1}^k \bs{1}(j / k \le x) \end{align*} But as \(k \to \infty\), \(f_k(0) \to 0\), \(k p_k \to 1\), and \(\frac{1}{k} \sum_{j = 1}^k \bs{1}(j / k \le x) \to \int_0^x 1 dt = x\).

1. From Example and the definition of \(P\), \begin{align*} P(x, 0) & = \frac{\left(\sqrt{k + 1} - 1\right)^2}{k} \\ P(0, x) & = \frac{1}{k} \\ P(x, y) & = \frac{\sqrt{k + 1} - 1}{k}, \quad y = (x - 1) \mod k, \; y = (x + 1) \mod k \end{align*} Note that \((x - 1) \mod k\) and \((x + 1) \mod k\) are the neighbors of \(x\) on the cycle.
2. Since the wheel is finite and symmetric, \(\bs Y\) is positive recurrent and the invariant probability density function \(h\) is obtained by normalizing the invariant function \(f^2\). After some algebra, \begin{align*} h(0) &= \frac 1 2 - \frac{1}{2 \sqrt{k + 1}} \\ h(x) &= \frac{1}{2 k} + \frac{1}{2 k \sqrt{k + 1}}, \quad x \in \{1, 2, \ldots, k\} \end{align*}