Introduction

Suppose that \( G = (S, L) \) is a connected graph with vertex set \( S \) and edge set \( L \subseteq S^2 \). We assume that the graph is undirected (perhaps a better term would be bi-directed) in the sense that \( (x, y) \in L \) if and only if \( (y, x) \in L \). We also assume that the graph has no loops, so that \( (x, x) \notin L \) for every \( x \in S \). The vertex set \( S \) may by infinite. Let \( N(x) = \{y \in S: (x, y) \in L\} \) denote the set of neighbors of a vertex \( x \in S \), and let \( d(x) = \#[N(x)] \) denote the degree of \( x \).

Suppose now that there is a conductance \( c(x, y) \gt 0 \) associated with each edge \( (x, y) \in L \). The conductance is symmetric in the sense that \( c(x, y) = c(y, x) \) for \( (x, y) \in L \). We extend \( c \) to a function on all of \( S \times S \) by defining \( c(x, y) = 0 \) for \( (x, y) \notin L \). As the terminology suggests, we imagine a fluid of some sort flowing through the edges of the graph, so that the conductance of an edge measures the capacity of the edge in some sense. The best interpretation is that the graph is an electrical network and the edges are resistors. In this interpretation, the conductance of a resistor is the reciprocal of the resistance.

Let \( C(x) = \sum_{y \in S} c(x, y) \) and suppose that \( C(x) \lt \infty \) for each \( x \in S \). The Markov chain \( \bs{X} = (X_0, X_1, X_2, \ldots) \) with state space \( S \) and transition probability matrix \( P \) given by

is called a random walk on the graph \( G \). This chain governs a particle moving along the vertices of \( G \). If the particle is at vertex \( x \in S \) at a given time, then the particle will be at a neighbor of \( x \) at the next time; the neighbor is chosen randomly, in proportion to the conductance. In the setting of an electrical network, it is natural to interpret the particle as an electron.

Note that multiplying the conductance function \( c \) by a positive constant has no effect on the associated random walk.

The chain in the previous exercise is the symmetric random walk on \( G \). Thus, if the chain is in state \( x \in S \) at a given time, then the chain is equally likely to move to any of the neighbors of \( x \) at the next time.

Consider the random walk on the graph below with the given conductance values. The underlying graph is sometimes called the Wheatstone bridge in honor of Charles Wheatstone.

1. Explicitly give the transition probability matrix \( P \).
2. Suppose that the chain starts at \( a \). Find the probability density function of \( X_2 \).

Answer:

For the matrix and vector below, we use the ordered state space \( S = (a, b, c, d) \).

1. \( P = \left[ \begin{matrix} 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{2} \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} \\ \frac{1}{5} & \frac{2}{5} & \frac{2}{5} & 0 \end{matrix} \right] \)
2. \( f_2 = \left( \frac{9}{40}, \frac{1}{5}, \frac{13}{40}, \frac{1}{4} \right) \)

Consider the random walk on the cube graph shown below, with the given conductance values. The vertices are bit strings of length 3, and two vertices are connected by an edge if and only if the bit strings differ by a single bit.

1. Explicitly give the transition probability matrix \( P \).
2. Suppose that the initial distribution is the uniform distribution on \( \{000, 001, 101, 100\} \). Find the probability density function of \( X_2 \).

Answer:

For the matrix and vector below, we use the ordered state space \( S = (000, 001, 101, 110, 010, 011, 111, 101 ) \).

1. \( P = \left[ \begin{matrix} 0 & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 & \frac{1}{2} & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 & 0 & 0 & \frac{1}{2} \\ \frac{1}{4} & 0 & 0 & 0 & 0 & \frac{3}{9} & 0 & \frac{3}{8} \\ 0 & \frac{1}{4} & 0 & 0 & \frac{3}{8} & 0 & \frac{3}{8} & 0 \\ 0 & 0 & \frac{1}{4} & 0 & 0 & \frac{3}{8} & 0 & \frac{3}{8} \\ 0 & 0 & 0 & \frac{1}{4} & \frac{3}{8} & 0 & \frac{3}{8} & 0 \end{matrix} \right] \)
2. \( f_2 = \left(\frac{3}{32}, \frac{3}{32}, \frac{3}{32}, \frac{3}{32}, \frac{5}{32}, \frac{5}{32}, \frac{5}{32}, \frac{5}{32}\right) \)

Random Walks on \( \Z^k \)

Random walks on the integer lattices \( \Z^k \), where \( k \in \N_+ \), are particularly interesting. Consider first the simple random walk \( \bs{X} = (X_0, X_1, X_2, \ldots) \) on \( \Z \), with transition probabilities

where \( p \in (0, 1) \) is a parameter. Note that the chain is irreducible.

More generally, consider \( \Z^k \), where \( k \in \N_+ \). For \( i \in \{1, 2, \ldots, k\} \), let \( \bs{u}_i \in \Z^k \) denote the unit vector with 1 in position \( i \) and 0 elsewhere. The simple random walk on \( \Z^k \) has transition probabilities

where \( p_i \gt 0 \), \( q_i \gt 0 \) for each \( i \) and \( \sum_{i=1}^k (p_i + q_i) = 1 \). Clearly, the larger the dimension \( k \), the less likely the chain is to be recurrent. In turns out that the behavior when \( k = 2 \) is similar to the behavior when \( k = 1 \): the chain is recurrent only in the symmetric case \( p_i = q_i = \frac{1}{4} \) for each \( i \). When the dimension \( k \) is 3 or more, the chain is transient for all values of the parameters, even in the symmetric case. Thus, for the simple, symmetric random walk on the integer lattice \( \Z^k \), we have the following interesting dimensional phase shift: the chain is recurrent in dimensions 1 and 2 and transient in dimensions 3 or more. The proofs are similar in to the proof sketched in the previous two exercises for dimension 1, but the details are considerably more complex. A return to \( 0 \) can occur only at even times and in the symmetric case,

where \( C_k \) is a positive constant that depends on the dimension \( k \). Thus \( G(\bs{0}, \bs{0}) = \infty \) and the chain is recurrent if \( k \in \{1, 2\} \) while \( G(\bs{0}, \bs{0}) \lt \infty \) and the chain is transient if \( k \in \{3, 4, \ldots\} \).

Positive Recurrence and Limiting Distributions

We return now to the general case of a random walk \( \bs{X} \) on a graph \( G \). Assume that \( G \) is connected so that \( \bs{X} \) is irreducible.

Recall, for example, the simple random walk on \( \Z^k \). We showed that the walk is recurrent if the dimension \( k \) is 1 or 2, and so we now know that the walk is null recurrent in these cases. The walk is transient if \( k \ge 3 \).

Reversibility

Essentially, all reversible Markov chains can be interpreted as random walks on graphs. This fact is one of the reasons for studying such walks.