As usual, our starting point is a measurable space \((S, \ms S)\). Recall that \(S^n\) is given the product \(\sigma\)-algebra \(\ms S^n\) for \(n \in \N_+\). As in Section 3, we also have a probability space \((\Omega, \ms F, \P)\) in the background.
A (right) random walk on the measurable graph \((S, \rta)\) is a discrete-time, homogeneous Markov process \(\bs{Y} = (Y_1, Y_2, \ldots)\) with the property that, with probability 1, \(Y_n \rta Y_{n+1}\) for all \(n \in \N_+\).
Of course, the term random walk has many different meanings in different settings, and in particular, the term random walk on a graph has a different meaning in combinatorial graph theory. However, in our terminology, walk has the same meaning as path and since \( Y_1 \rta Y_2 \rta \cdots \) the sequence \(\bs Y\) is literally a random path in the graph. Also, it's more common to have a discrete-time Markov process starting with index 0, but starting with index 1 is better for the purposes that we have in mind.
Suppose that \(X\) is a random variable supported by \((S, \rta)\). The random walk on \((S, \rta)\) associated with \(X\) is the random walk \(\bs Y = (Y_1, Y_2, \ldots)\) with the following properties:
That is, \(Y_1\) has the same distribution as \(X\), and for \(n \in \N_+\) and \(x \in S\), the conditional distribution of \(Y_{n+1}\) given \(Y_n = x\) is the same as the conditional distribution of \(X\) given \(x \rta X\). It's clear that \(\bs Y\) really is a random walk on the graph \((S, \rta)\) since \(Y_n \rta Y_{n+1}\) for \(n \in \N_+\). Also, it's only the distribution of \(X\) that is important, but as usual the language of random variables is more convenient and natural. Suppose now that \(\lambda\) is a fixed \(\sigma\)-finite reference measure on \((S, \ms S)\) and that \(X\) is supported by \((S, \rta)\) with density function \(f\), reliability function \(F\), and rate function \(r\). Let \(L\) denote the adjacency kernel of \((S, \rta)\).
The random walk \(\bs Y = (Y_1, Y_2, \ldots)\) on \((S, \rta)\) associated with \(X\) has the following properties:
Note that for \(x \in S\), the mapping \(y \mapsto f(y) / F(x)\) for \(x \rta y\) is density of the conditional distribution of \(X\) given \(x \rta X\).
So \(P(x, y) = f(y) / F(x)\) if \(x \rta y\) and is \(0\) otherwise. For the higher order transition densities, a new kernel is helpful, defined by integrating the product of the rate function over paths. This is additional evidence that the rate function as an object of general importance.
Let \(R^{(1)} = L\) and for \(n \in \N_+\) define \(R^{(n+1)}\) on \(S^2\) by \[R^{(n + 1)}(x, y) = \int_{x \rta x_1 \rta \cdots \rta x_n \rta y} r(x_1) r(x_2) \cdots r(x_n) \, d\lambda^n(x_1, x_2, \ldots, x_n), \quad (x, y) \in S^2\] so that the integral is over the middle parts of paths of length \(n + 1\) from \(x\) to \(y\).
The parentheses in the superscript are a reminder that this is not an ordinary operator product. Also, we need to be sure not to confuse the kernel \(R^{(n)}\) with the cumulative rate function \(R_n\) of order \(n\), which will make another appearance below.
Suppose again that \(\bs Y\) is the random walk on \((S, \rta)\) associated with \(X\). The transition density \(P^n\) of order \(n \in \N_+\) for \(\bs{Y}\) is given by \[P^n(x, y) = \frac{f(y)}{F(x)} R^{(n)}(x, y), \quad (x, y) \in S^2\]
The result is true by definition when \(n = 1\). For \(n \in \{2, 3, \ldots\}\), \begin{align*} P^n(x, y) &= \int_{S^{n-1}} P(x, x_1) P(x_1, x_2) \cdots P(x_{n-1}, y) \, d\lambda^{n-1}(x_1, x_2, \ldots, x_{n-1}) \\ &= \int_{x \rta x_1 \rta \cdots \rta x_{n-1} \rta y} \frac{f(x_1)}{F(x)} \frac{f(x_2)}{F(x_1)} \cdots \frac{f(x_{n-1})}{F(x_{n-1})} \frac{f(y)}{F(x_{n-1})} \, d\lambda^{n-1}(x_1, x_2, \dots, x_{n-1}) \\ &= \frac{f(y)}{F(x)} \int_{x \rta x_1 \rta \cdots \rta x_{n-1} \rta y} r(x_1) r(x_2) \cdots r(x_{n-1}) \, d\lambda^{n-1}(x_1, x_2, \ldots, x_{n-1}) \\ &= \frac{f(y)}{F(x)} R^{(n)}(x, y), \quad (x, y) \in S^2 \end{align*}
There is a simple connection between left operators of the kernels \(P^n\) and \(R^{(n)}\) for \(n \in \N_+\). We are only interested in nonnegative functions.
If \(g: S \to [0, \infty)\) is measurable then \((g F) P^n = f \left(g R^{(n)}\right)\) for \(n \in \N_+\).
For \(n \in \N_+\),
\begin{align*}
(g F)P^n(y) &= \int_S g(x) F(x) P^n(x, y) \, d\lambda(x) = \int_S g(x) F(x) \frac{f(y)}{F(x)} R^{(n)}(x, y)\, d\lambda(x) \\
&= f(y) \int_S g(x) R^{(n)}(x, y) \, d\lambda(x) = f(y) \left(g R^{(n)}\right)(y), \quad y \in S
\end{align*}Details:
Suppose that \((S, \lfrta)\) is a symmetric graph and that once again \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on \((S, \lfrta)\) associated with random variable \(X\), where \(X\) has density function \(f\) and reliability function \(F\).
In the discrete case, if the graph \((S, \lfrta)\) is strongly connected so that the Markov chain \(\bs Y\) is irreducible, then the random walk \(\bs Y\) is positive recurrent.
Suppose for a moment that we do not have an underlying graph and that \(\bs Y\) is a discrete-time Markov process on \(S\) with transition density \(P\). Then trivially \(\bs Y\) is a random walk with respect to its own leads-to relation \(\rta\) given by \(x \rta y\) if and only if \(P(x, y) \gt 0\). A natural question is when \(\bs Y\) is the random walk on the graph \((S, \rta)\) associated with a probability density function \(f\). The answer is simple.
A Markov transition density \(P\) on \(S\) corresponds to a random walk on \((S, \rta)\) associated with a probability density function if and only if \[P(x, y) = g(x) h(y) L(x, y), \quad (x, y) \in S^2\] for measurable functions \(g, \, h: S \to (0, \infty)\) with \(h \in \ms L_1\).
Trivially the transition density \(P\) associated with probability density function \(f\) has the factoring given above, with \(g = 1 / F\) and \(h = f\). Conversely, suppose that \(P\) has the factoring given above. Let \(c = \int_S h(y) \, d\lambda(y)\) so that \(c \in (0, \infty)\), and then define \(f\) and \(F\) by \[F(x) = \frac{1}{c g(x)}, \; f(x) = \frac{h(x)}{c}, \quad x \in S\] Then \(f\) is a density function on \(S\) and \(P(x, y) = f(y) / F(x)\) for \(x \rta y\). Moreover, since \(\int_{x \rta y} P(x, y) \, d\lambda(y) = 1\) for \(x \in S\), we have \[\int_{x \rta y} f(y) \, d\lambda(y) = F(x), \quad x \in S\] so \(F\) is the reliability function of \(f\) for \((S, \rta)\).
So clearly Markov processes on \(S\) that are associated with a probability density function on \(S\) are special. Nonetheless, many classical Markov chains with discrete state spaces have this form.
Consider again the original setting of a given measurable graph \((S, \rta)\) and a random variable \(X\) supported by \((S, \rta)\). It's easy to construct the random walk on \((S, \rta)\) associated with \(X\). The construction is based on the standard rejection method, but first we need to deal with minor technicalities. Let \(S^* = S \cup \{\delta\}\) where \(\delta\) is a new state. Extend the relation \(\rta\) to a relation \(\rta^*\) on \(S^*\) by the additional rule \(x \rta^* \delta\) for every \(x \in S^*\). Let \(\ms S^* = \sigma(\ms S \cup \{\delta\})\), which amounts to making the sets \(\{\delta\} \cup A\) measurable for \(A \in \ms S\).
Suppose that \(X\) is a random variable supported by \((S, \rta)\) and that \(\bs X = (X_1, X_2, \ldots)\) is a sequence of independent copies of \(X\).
The sequence \(\bs Y = (Y_1, Y_2, \ldots)\) is the sequence of record variables on \((S, \rta)\) associated with \(X\).
Suppose again that \(X\) is a random variable supported by \((S, \rta)\). The sequence of record variables \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on \((S, \rta)\) associated with \(X\).
By definition, \(Y_1 = X_1\) has the distribution of \(X\). Suppose that \(n \in \N_+\). Given \(Y_n = x \in S\) and an event \(A \in \sigma\{Y_0, \ldots, Y_{n-1}\}\), the conditional distribution of \(Y_{n+1}\) is the same as the distribution of \(X_N\) where \((X_1, X_2, \ldots)\) is a sequence of independent copies of \(X\), and where \(N = \min\{n \in \N_+: x \rta X_n\}\). In turn, the distribution of \(X_N\) is the same as the conditional distribution of \(X\) given \(x \rta X\). Since \(X\) is supported by \((S, \rta)\), with probability \(1\), \(Y_n \in S\) for all \(n \in \N\).
In the standard continuous space \(([0, \infty), \le)\) we can give a reliability interpretation of the record-value construction. Suppose that we have an infinite sequence of identical devices, labeled by the positive integers, and that all are initially working. We designate device 1 as the primary device. Recursively, when the primary device fails, we immediately (and with no loss of time), scan the sequence of devices; the first one that is still working then becomes the primary device.
Suppose again that \(X\) is a random variable supported by \((S, \rta)\) with density function \(f\), and with reliability function \(F\) and rate function \(r\) for \((S, \rta)\). Let \(\bs Y = (Y_1, Y_2 \ldots)\) be the random walk on \((S, \rta)\) associated with \(X\). For \(n \in \N_+\), recall the cumulative rate function \(R_n\) of order \(n\) of \(X\) is given by \[R_n(x) = \int_{x_1 \rta \cdots \rta x_n \rta x} r(x_1) r(x_2) \cdots r(x_n) \, d\lambda^n(x_1, x_2, \ldots, x_n), \quad x \in S\]
Let \(n \in \N_+\).
Since \(Y_1\) has density function \(f\) by definition, it follows that \((Y_1, Y_2, \ldots, Y_n)\) has density function \begin{align*} g_n(x_1, x_2, \ldots, x_n) &= f(x_1) P(x_1, x_2) \cdots P(x_{n-1}, x_n) = f(x_1) \frac{f(x_2)}{F(x_1)} \cdots \frac{f(x_n)}{F(x_{n-1})} \\ &= r(x_1) r(x_2) \cdots r(x_{n-1}) f(x_n), \quad x_1 \rta x_2 \rta \cdots \rta x_n \end{align*} for Parts (b) and (c) follow by the usual methods.
This corollary points out once again the importance of the rate function \(r\), and the importance of the cumulative rate function \(R_n\) for \(n \in \N\) (aside from their use in classical reliability theory). In part (a), consider the special case that the set of paths of length \(n - 1\) is a product set. Then \((Y_1, Y_2, \ldots, Y_n)\) are independent, with \((Y_1, Y_2, \ldots, Y_{n-1})\) identically distributed and having common density proportional to \(r\), while \(Y_n\) has density \(f\).
For \(n \in \N_+\), the density function \(f_n\) of \(Y_n\) given in part (b) of is the density function of order \(n\) associated with \((S, \rta)\) and \(f\).
The following definition applies to random walks generally, not just random walks associated with a given distribution on \(S\).
Let \(\bs Y = (Y_1, Y_2, \ldots)\) be a random walk on \((S, \rta)\). Define \[N_A = \#\{n \in \N _+: Y_n \in A\} = \sum_{n=1}^\infty \bs 1(Y_n \in A), \quad A \in \ms S\] The process \(\bs N = \{N_A: A \in \ms S\}\) is the point process associated with the random walk \(\bs Y\).
So \(A \mapsto N_A\) is a random, discrete measure on \((S, \ms S)\). Let's return now to our standard setting of a random walk \(\bs Y = (Y_1, Y_2, \ldots)\) on \((S, \rta)\) associated with a random variable \(X\). Our interest is in \(\E(N_A)\) for \(A \in \ms S\) and for that we need one more function.
Define \(V: S \to [0, \infty]\) by \[V(x) = \sum_{n=0}^\infty R_n(x), \quad x \in S\] where \(R_n\) is the cumulative rate function of order \(n \in \N\).
Let \(\bs Y\) be the random walk on \((S, \rta)\) associated with \(X\), and let \(\bs N\) be the corresponding point process. Then \[\E(N_A) = \E[V(X); X \in A], \quad A \in \ms S\]
So the (deterministic) measure \(A \mapsto \E(N_A)\) on \((S, \ms S)\) has density function \(V f\) with respect to \(\lambda\).