3 Reversible Markov Chains (September 10, 2002)

3.2 Reversible chains and weighted graphs

Our convention is that a graph has finite vertex-set 𝒱={v,x,y,}\mbox{${\cal V}$}=\{v,x,y,\ldots\} and edge-set ={e1,e2,}\mbox{${\cal E}$}=\{e_{1},e_{2},\ldots\}, is connected and undirected, has no multiple edges, and has no self-loops. In a weighted graph, each edge (v,w)(v,w) also has a weight 0<wv,x=wx,v<0<w_{v,x}=w_{x,v}<\infty, and we allow a weighted graph to have self-loops.

Given a weighted graph, there is a natural definition of a Markov chain on the vertices. This requires an arbitrary choice of convention: do we want to regard an absent edge as having weight 00 or weight ++\infty? In terms of electrical networks (Section 3.3) the question is whether to regard weights as conductances or as resistances of wires. Conceptually one can make good arguments for either choice, but formulas look simpler with the conductance convention (absent edges have weight 00), so we’ll adopt that convention. Define discrete-time random walk on a weighted graph to be the Markov chain with transition matrix

pvx:=wvx/wv,  xvp_{vx}:=w_{vx}/w_{v},\ x\neq v (3.13)


wv:=xwvx, w:=vwv.w_{v}:=\sum_{x}w_{vx},\ \ w:=\sum_{v}w_{v}.

Note that ww is the total edge-weight, when each edge is counted twice, i.e., once in each direction. The fundamental fact is that this chain is automatically reversible with stationary distribution

πvwv/w\pi_{v}\equiv w_{v}/w (3.14)

because (3.1) is obviously satisfied by πvpvx=πxpxv=wvx/w\pi_{v}p_{vx}=\pi_{x}p_{xv}=w_{vx}/w. Our standing convention that graphs be connected implies that the chain is irreducible. Conversely, with our standing convention that chains be irreducible, any reversible chain can be regarded as as random walk on the weighted graph with edge-weights wvx:=πvpvxw_{vx}:=\pi_{v}p_{vx}. Note also that the “aperiodic” condition for a Markov chain (occurring in the convergence theorem margin: 9/10/99 versionChapter 2 Theorem 2) is just the condition that the graph be not bipartite.

An unweighted graph can be fitted into this setup by simply assigning weight 11 to each edge. Since we’ll be talking a lot about this case, let’s write out the specialization explicitly. The transition matrix becomes

pvx={1/dvif (v,x)(v,x) is an edge0if notp_{vx}=\left\{\begin{array}[]{cl}1/d_{v}&\mbox{if $(v,x)$ is an edge}\\ 0&\mbox{if not}\end{array}\right.

where dvd_{v} is the degree of vertex vv. The stationary distribution becomes

πv=dv2||\pi_{v}=\frac{d_{v}}{2|\mbox{${\cal E}$}|} (3.15)

where |||\mbox{${\cal E}$}| is the number of edges of the graph. In particular, on an unweighted regular graph the stationary distribution is uniform.

In continuous time there are two different ways to associate a walk with a weighted or unweighted graph. One way (and we use this way unless otherwise mentioned) is just to use (3.13) as the definition of the transition rates qvxq_{vx}. In the language of Chapter 2 margin: 9/10/99 versionthis is the continuization of the discrete-time walk, and has the same stationary distribution and mean hitting times as the discrete-time walk. The alternative definition, which we call the fluid model, uses the weights directly as transition rates:

qvx:=wvx, xv.q_{vx}:=w_{vx},\ \ x\neq v. (3.16)

In this model the stationary distribution is always uniform (cf. Section 3.2.1). In the case of an unweighted regular graph the two models are identical up to a deterministic time rescaling, but for non-regular graphs there are typically no exact relations between numerical quantities for the two continuous-time models. Note that, given an arbitrary continuous-time reversible chain, we can define edge-weights (wij)(w_{ij}) via

πiqij=πjqji=wij, say\pi_{i}q_{ij}=\pi_{j}q_{ji}=w_{ij},\mbox{\ say}

but the weights (wij)(w_{ij}) do not completely determine the chain: we can specify the πi\pi_{i} independently and then solve for the qq’s.

Though there’s no point in writing out all the specializations of the general theory of margin: 9/10/99 versionChapter 2, let us emphasize the simple expressions for mean return times of discrete-time walk obtained from margin: 9/10/99 versionChapter 2 Lemma 5 and the expressions (3.14)–(3.15) for the stationary distribution.

Lemma 3.5

For random walk on an nn-vertex graph,

EvTv+\displaystyle E_{v}T^{+}_{v} =\displaystyle= wwv  (𝑤𝑒𝑖𝑔ℎ𝑡𝑒𝑑)\displaystyle\frac{w}{w_{v}}\quad\mbox{\ \,{\rm(}weighted\/{\rm)}}
=\displaystyle= 2||dv(𝑢𝑛𝑤𝑒𝑖𝑔ℎ𝑡𝑒𝑑)\displaystyle\frac{2|\mbox{${\cal E}$}|}{d_{v}}\quad\mbox{{\rm(}unweighted\/{% \rm)}}
=\displaystyle= n    (unweighted regular).\displaystyle n\quad\mbox{\ \ \ \,{\rm(}unweighted regular\/{\rm)}}.
Example 3.6

Chess margin: The example has been copied here from the start of Example 18 of Chapter 5 (4/22/96 version); reminder: that example needs to be modified accordingly! moves.

Here is a classic homework problem for an undergraduate Markov chains course.

Start a knight at a corner square of an otherwise-empty chessboard. Move the knight at random, by choosing uniformly from the legal knight-moves at each step. What is the mean number of moves until the knight returns to the starting square?

It’s a good question, because if you don’t know Markov chain theory it looks too messy to do by hand, whereas using Markov chain theory it becomes very simple. The knight is performing random walk on a graph (the 64 squares are the vertices, and the possible knight-moves are the edges). It is not hard to check that the graph is connected, so by the elementary Lemma 3.5, for a corner square vv the mean return time is

EvTv+=1πv=2||dv=||,E_{v}T^{+}_{v}=\frac{1}{\pi_{v}}=\frac{2|\mbox{${\cal E}$}|}{d_{v}}=|\mbox{${% \cal E}$}|,

and by drawing a sketch in the margin the reader can count the number of edges |||\mbox{${\cal E}$}| to be 168168.

The following cute variation of Lemma 3.5 is sometimes useful. Given the discrete-time random walk (Xt)(X_{t}), consider the process


recording the present position at time tt and also the previous position. Clearly (Zt)(Z_{t}) is a Markov chain whose state-space is the set \stackrel{\rightarrow}{{\cal E}} of directed edges, and its stationary distribution (ρ\rho, say) is


in the general weighted case, and hence

ρ(v,x)=1||,(x,v)\rho(v,x)=\frac{1}{|\stackrel{\rightarrow}{{\cal E}}|},\ \ (x,v)\in\stackrel{% \rightarrow}{{\cal E}}

in the unweighted case. Now given an edge (x,v)(x,v), we can apply margin: 9/10/99 versionChapter 2 Lemma 5 to (Zt)(Z_{t}) and the state (x,v)(x,v) to deduce the following.

Lemma 3.7

Given an edge (v,x)(v,x) define

U:=min{t1:Xt=v,  Xt-1=x}.U:=\min\{t\geq 1:X_{t}=v,\ X_{t-1}=x\}.


EvU\displaystyle E_{v}U =\displaystyle= wwvx(𝑤𝑒𝑖𝑔ℎ𝑡𝑒𝑑)\displaystyle\frac{w}{w_{vx}}\quad\mbox{{\rm(}weighted\/{\rm)}}
=\displaystyle= 2||(𝑢𝑛𝑤𝑒𝑖𝑔ℎ𝑡𝑒𝑑).\displaystyle 2|\mbox{${\cal E}$}|\quad\mbox{{\rm(}unweighted\/{\rm)}}.
Corollary 3.8 (The edge-commute inequality)

For an edge (v,x)(v,x),

EvTx+ExTvwwvx(𝑤𝑒𝑖𝑔ℎ𝑡𝑒𝑑)2||(𝑢𝑛𝑤𝑒𝑖𝑔ℎ𝑡𝑒𝑑).E_{v}T_{x}+E_{x}T_{v}\leq\begin{array}[]{l}\frac{w}{w_{vx}}\quad\mbox{{\rm(}% weighted\/{\rm)}}\\ 2|\mbox{${\cal E}$}|\quad\mbox{{\rm(}unweighted\/{\rm)}}\end{array}.

We shall soon see (Section 3.3.3) this inequality has a natural interpretation in terms of electrical resistance, but it is worth remembering that the result is more elementary than that.

Here is another variant of Lemma 3.5.

Lemma 3.9

For random walk on a weighted nn-vertex graph,


where the sum is over undirected edges.

Proof. Writing vx\sum_{v}\sum_{x} for the sum over directed edges (v,x)(v,x), the left side equals

=\displaystyle= vxwvxExTv  by symmetry\displaystyle\sum_{v}\sum_{x}w_{vx}E_{x}T_{v}\mbox{\ \ by symmetry}
=\displaystyle= wvπvxpvxExTv\displaystyle w\sum_{v}\pi_{v}\sum_{x}p_{vx}E_{x}T_{v}
=\displaystyle= wvπv(EvTv+-1)\displaystyle w\sum_{v}\pi_{v}(E_{v}T^{+}_{v}-1)
=\displaystyle= wvπv(1πv-1)\displaystyle w\sum_{v}\pi_{v}({\textstyle\frac{1}{\pi_{v}}}-1)
=\displaystyle= w(n-1).             \displaystyle w(n-1).\qquad\qquad\qquad~{}\ \ \rule{4.3pt}{4.3pt}

3.2.1 The fluid model

Imagine a finite number of identical buckets which can hold unit quantity of fluid. Some pairs of buckets are connected by tubes through their bottoms. If a tube connects buckets ii and jj then, when the quantities of fluid in buckets ii and jj are pip_{i} and pjp_{j}, the flow rate through the tube should be proportional to the pressure difference and hence should be wij(pi-pj)w_{ij}(p_{i}-p_{j}) in the direction iji\rightarrow j, where wij=wjiw_{ij}=w_{ji} is a parameter. Neglecting the fluid in the tubes, the quantities of fluid (pi(t))(p_{i}(t)) at time tt will evolve according to the differential equations

dpj(t)dt=ijwij(pi(t)-pj(t)).\frac{dp_{j}(t)}{dt}=\sum_{i\neq j}w_{ij}(p_{i}(t)-p_{j}(t)).

These of course are the same equations as the forward equations [(4) of margin: 9/10/99 versionChapter 2] for pi(t)p_{i}(t) (the probability of being in state ii at time tt) for the continuous-time chain with transition rates qij=wij,  jiq_{ij}=w_{ij},\ j\neq i. Hence we call this particular way of defining a continuous-time chain in terms of a weighted graph the fluid model. Our main purpose in mentioning this notion is to distinguish it from the electrical network analogy in the next section. Our intuition about fluids says that as tt\rightarrow\infty the fluid will distribute itself uniformly amongst buckets, which corresponds to the elementary fact that the stationary distribution of the “fluid model” chain is always uniform. Our intuition also says that increasing a “specific flow rate” parameter wijw_{ij} will make the fluid settle faster, and this corresponds to a true fact about the “fluid model” Markov chain (in terms of the eigenvalue interpretation of asymptotic convergence rate—see Corollary 3.28). On the other hand the same assertion for the usual discrete-time chain or its continuization is simply false.