# 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 $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)$.

###### Lemma 5.1 (essential edge lemma)

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}$.