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 $1$-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)$ of a graph is essential (or a bridge) if its removal would disconnect the graph, into two components $A(v,x)$ and $A(x,v)$, say, containing $v$ and $x$ respectively. Recall that ${\cal E}$ is the set of (undirected) edges, and write $\mbox{${\cal E}$}(v,x)$ for the set of edges of $A(v,x)$.

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

$\displaystyle E_{v}T_{x}$ | $\displaystyle=$ | $\displaystyle\frac{2\sum_{(i,j)\in\mbox{${\cal E}$}(v,x)}w_{ij}}{w_{vx}}+1$ | (5.1) | ||

$\displaystyle E_{v}T_{x}+E_{x}T_{v}$ | $\displaystyle=$ | $\displaystyle\frac{w}{w_{vx}},\mbox{\ where\ }w=\sum_{i}\sum_{j}w_{ij}.$ | (5.2) |

Specializing to the unweighted case,

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

$\displaystyle E_{v}T_{x}+E_{x}T_{v}$ | $\displaystyle=$ | $\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)$ is essential, we may delete all vertices of $A(x,v)$ except $x$, and this does not affect the behavior of the chain up until time $T_{x}$, because $x$ must be the first visited vertex of $A(x,v)$. After this deletion, $\pi_{x}^{-1}=E_{x}T^{+}_{x}=1+E_{v}T_{x}$ by considering the first step from $x$, and $\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)$ is obviously $1/w_{vx}$.

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML