]>
Suppose that is a connected graph with vertex set and edge set . We assume that the graph is undirected (perhaps a better term would be bi-directed) in the sense that if and only if . We also assume that the graph has no loops, so that for any . The vertex set may by infinite. Let denote the set of neighbors of a vertex , and let denote the degree of .
Suppose now that there is a conductance associated with each edge . The conductance is symmetric in the sense that for . We extend to a function on all of by defining for . 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 and suppose that for each . The Markov chain with state space and transition probability matrix given by
is called a random walk on the graph . This chain governs a particle moving along the vertices of . If the particle is at vertex at a given time, then the particle will be at a neighbor of 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 by a positive constant has no effect on the associated random walk.
Suppose that each edge has the same conductance, so that is constant on the edges.
The chain in the previous exercise is the symmetric random walk on . Thus, if the chain is in state at a given time, then the chain is equally likely to move to any of the neighbors of 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.
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.
Note each of the following:
Suppose that is connected and finite. Show that is either aperiodic or has period 2. Moreover, has period 2 if and only if is bipartite. That is, the vertex set can be partitioned into sets and such that every edge in has one endpoint in and one endpoint in ; these sets are then the cyclic classes of the chain.
Random walks on the integer lattices , where , are particulalry interesting. Consider first the simple random walk on , with transition probabilities
where . Note that the chain is irreducible.
Note that starting in state 0, the chain can return to state 0 only at even times. Moreover, the chain returns to 0 whenever the number of steps right equals the number of steps left. Thus, show that
Use Stirling's approximation to show that . Conclude that
More generally, consider , where is a positive integer. For , let denote the unit vector with 1 in position and 0 elsewhere. The simple random walk on has transition probabilities
where and are positive for each and . Clearly, the larger the dimension , the less likely the chain is to be recurrent. In turns out that the behavior when is similar to the behavior when : the chain is recurrent only in the symmetric case for each . When the dimension 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 , 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 can occur only at even times and in the symmetric case,
where is a positive constant that depends on the dimension . Thus and the chain is recurrent if ; and the chain is transient if .
We return now to the general case of a random walk on a graph .
Show that the function is left-invariant for . Thus, conclude that the random walk is positive recurrent if and only if
in which case the invariant probability density function is given by for .
Consider the special case of the simple random walk on , so that the conductance function is constant on the set of edges . Show that the random walk is positive recurrent if and only if the set of vertices is finite, in which case the invariant probability density function is given by for where is the degree function and where is the number of undirected edges.
Recall, for example, the simple random walk on . We showed that the walk is recurrent if the dimension is 1 or 2, and so we now know that the walk is null recurrent in these cases. The walk is transient if .
Consider the random walk on the Wheatstone bridge given in Exercise 2.
Consider the random walk on the cube graph given in Exercise 3.
Essentially, all reversible Markov chains can be interpreted as random walks on graphs. This fact is one of the reasons for studying such walks.
Show that a positive recurrent random walk on a graph is reversible.
Conversely, suppose that is a reversible Markov chain on with transition probability matrix and invariant probability density function . Suppose also that for every . Show that can be interpreted as the random walk on the state graph of with conductance function given by
Recall that the Ehrenfest chain is reversible. Interpreting the chain as a random walk on a graph, sketch the graph and find a conductance function.