Reversible Markov Chains and Random Walks on Graphs

Chapter 5 Examples: Special Graphs and Trees (April 23 1996)

There are two main settings in which explicit calculations for random walks on large graphs can be done. One is where the graph is essentially just 11-dimensional, and the other is where the graph is highly symmetric. The main purpose of this chapter is to record some (mostly) bare-hands calculations for simple examples, in order to illuminate the general inequalities of Chapter 4. Our focus is on natural examples, but there are a few artificial examples devised to make a mathematical point. A second purpose is to set out some theory for birth-and-death chains and for trees.

Lemma 5.1 below is useful in various simple examples, so let’s record it here. An edge (v,x)(v,x) of a graph is essential (or a bridge) if its removal would disconnect the graph, into two components A(v,x)A(v,x) and A(x,v)A(x,v), say, containing vv and xx respectively. Recall that {\cal E} is the set of (undirected) edges, and write (v,x)\mbox{${\cal E}$}(v,x) for the set of edges of A(v,x)A(v,x).

Lemma 5.1 (essential edge lemma)

For random walk on a weighted graph with essential edge (v,x)(v,x),

EvTx\displaystyle E_{v}T_{x} =\displaystyle= 2(i,j)(v,x)wijwvx+1\displaystyle\frac{2\sum_{(i,j)\in\mbox{${\cal E}$}(v,x)}w_{ij}}{w_{vx}}+1 (5.1)
EvTx+ExTv\displaystyle E_{v}T_{x}+E_{x}T_{v} =\displaystyle= wwvx, where w=ijwij.\displaystyle\frac{w}{w_{vx}},\mbox{\ where\ }w=\sum_{i}\sum_{j}w_{ij}. (5.2)

Specializing to the unweighted case,

EvTx\displaystyle E_{v}T_{x} =\displaystyle= 2|(v,x)|+1\displaystyle 2|\mbox{${\cal E}$}(v,x)|+1 (5.3)
EvTx+ExTv\displaystyle E_{v}T_{x}+E_{x}T_{v} =\displaystyle= 2||.\displaystyle 2|\mbox{${\cal E}$}|. (5.4)

Proof. It is enough to prove (5.1), since (5.2) follows by adding the two expressions of the form (5.1). Because (v,x)(v,x) is essential, we may delete all vertices of A(x,v)A(x,v) except xx, and this does not affect the behavior of the chain up until time TxT_{x}, because xx must be the first visited vertex of A(x,v)A(x,v). After this deletion, πx-1=ExTx+=1+EvTx\pi_{x}^{-1}=E_{x}T^{+}_{x}=1+E_{v}T_{x} by considering the first step from xx, and πx=wvx/(2wvx+2(i,j)(v,x)wij)\pi_{x}=w_{vx}/(2w_{vx}+2\sum_{(i,j)\in\mbox{${\cal E}$}(v,x)}w_{ij}), giving (5.1).    

Remarks. Of course Lemma 5.1 is closely related to the edge-commute inequality of Chapter 3 Lemma yyy. We can also regard (5.2), and hence (5.4), as consequences of the commute interpretation of resistance (Chapter 3 yyy), because the effective resistance across an essential edge (v,x)(v,x) is obviously 1/wvx1/w_{vx}.