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 -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 of a graph is essential (or a bridge) if its removal would disconnect the graph, into two components and , say, containing and respectively. Recall that is the set of (undirected) edges, and write for the set of edges of .
For random walk on a weighted graph with essential edge ,
(5.1) | |||||
(5.2) |
Specializing to the unweighted case,
(5.3) | |||||
(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 is essential, we may delete all vertices of except , and this does not affect the behavior of the chain up until time , because must be the first visited vertex of . After this deletion, by considering the first step from , and , giving (5.1).