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. In our setting the term is approriate: Since \( Y_1 \rta Y_2 \rta \cdots \) the sequence \(\bs Y\) is literally a random walk in the graph. 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. Note that in the discrete case, the periodicity of states, in the sense of Markov chains, agrees with periodicity of the underlying graph, as defined in Section 1. 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 walks. 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 walks 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 walks 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\).
Suppose that \((S, \rta)\) is a finite graph so that \(\lambda(S) \in (0, \infty)\). Recall from Section 1 that the right walk distribution of order \(m \in \N\) for \((S, \rta)\) has density function \(x \mapsto v_m(x) / w_m\) on \(S\) where \(v_m\) is the right walk function of order \(m\) and \(w_m\) is the corresponding normalizing constant. That is, \(v_m(x)\) is the measure of the set of walks of length \(m\) starting in \(x \in S\) while \(w_m\) is the measure of all walks of length \(m\).
Suppose again that \((S, \rta)\) is a finite graph and that \(\bs Y_m = (Y_1, Y_2, \ldots)\) is the random walk on \((S, \rta)\) associated with the right walk distribution of order \(m \in \N\).
The corresponding reliability function is \(x \mapsto v_{m + 1}(x) / w_m\) on \(S\). We assume of course that the graph is right positive with respect to \(\lambda\), so that the walk functions are positive.
The walk distribution of order 0 is the uniform distribution on \(S\). In this case, given \(Y_n = x \in S\), random variable \(Y_{n + 1}\) is uniformly distributed on the neighbors of \(x\). For a finite discrete graph, this is the setting for classical random walks on such graphs. In part (b), an invariant density function \(g_m\) is given by \(g_m(x) = v_m(x) v_{m + 1}(x) / c_m\) for \(x \in S\) where \(c_m\) is the normalizing constant: \(c_m = \int_S v_m(y) v_{m + 1}(y) \, d\lambda(y)\)
Suppose that \((S, \rta)\) is a finite graph and is right regular of degree \(k \in (0, \infty)\). Let \(\bs Y = (Y_1, Y_2, \ldots)\) denote the random walk on \((S, \rta)\) associated with the right walk distribution of order \(m \in \N\).
The results follow trivially since the right walk function of order \(m \in \N\) is \(v_m(x) = k^m\) for \(x \in S\).
Recall again that we have an underlying \(\sigma\)-finte measure space \((S, \ms S, \lambda)\), and that graphs with base set \(S\) are assumed to be measurable. In particular, in the discrete case, the reference \(\sigma\)-algebra \(\ms P(S)\) is the collection of all subsets of \(S\), and the reference measure \(\#\) is counting measure.
Recall that \(([0, \infty), \le)\) (with the usual Euclidean measure structure) is the standard continuous graph. Suppose that \(X\) has density function \(f\) given by \[f(x) = \frac{\alpha}{(x + 1)^{\alpha + 1}}, \quad x \in [0, \infty)\] where \(\alpha \in (0, \infty)\) is a parameter, and let \(\bs Y = (Y_1, Y_2, \ldots)\) be the random walk on \(([0, \infty), \le)\) associated with \(X\). Find the following for \(n \in \N_+\):
Recall that \((\N, \le)\) is the standard discrete graph. Suppose that \(X\) has density function \(f\) given by \[f(x) = \frac{1}{(x + 1)^\alpha} - \frac{1}{(x + 2)^\alpha}, \quad x \in \N\] where \(\alpha \in (0, \infty)\) is a parameter, and let \(\bs Y = (Y_1, Y_2, \ldots)\) be the random walk on \((\N, \le)\) associated with \(X\). Find the following:
The variables below are in \(\N\).
Consider the diamond graph \((S, \lfrta)\) studied in Section 1 and shown below. Let \(\bs Y_m = (Y_1, Y_2, \ldots)\) denote the random walk on \((S, \lfrta)\) associated with the right walk distribution of order \(m \in \N\). Find each of the following:
Consider the bull graph \((S, \lfrta)\) studied in Section 1 and shown below. Let \(\bs Y_m = (Y_1, Y_2, \ldots)\) denote the random walk on \((S, \lfrta)\) associated with the walk distribution of order \(m \in \N\). Find each of the following:
For \(k \in \{3, 4, \ldots\}\), let \((S, \lfrta)\) denote the star graph of order \(k\) as defined in Section 1.and shown below. Recall that \(S = \{0, 1, \ldots, k\}\) where \(0\) is the center and \(\{1, 2, \ldots, k\}\) are the endpoints. Let \(\bs Y = (Y_1, Y_2, \ldots)\) denote the random walk on \((S, \lfrta)\) associated with the walk distribution of order \(m \in \N\). Find each of the following:
From the walk functions in Section 1, or simply from symmetry considerations,
In example , note that \(P\) and \(g\) do not depend on the order \(m\) of the walk distribution. Note also that the star (and hence a random walk on the star) is periodic with period 2.
For \(k \in \{3, 4, \ldots\}\), let \((S, \lfrta)\) denote the wheel graph of order \(k\) as defined in Section 1 and shown below. Let \(\bs Y_m = (Y_1, Y_2, \ldots)\) denote the random walk on \((S, \lfrta)\) associated with the walk distribution of order \(m \in \N\). Find each of the following:
Let \(m \in \N\) and \(x \in \{1, 2, \ldots, k\}\). The expressions \(x - 1\) and \(x + 1\) refer to the neighbors of \(x\) on the cycle.