=+13. A random walk on a connected graph has equilibrium distribution v = d(v) 2m , where

=+13. A random walk on a connected graph has equilibrium distribution

πv = d(v)

2m , where d(v) is the degree of v and m is the number of edges. Let tuv be the expected time the chain takes in traveling from node u to node v. If the graph is not bipartite, then the chain is aperiodic, and Example 7.3.4 shows that tvv = 1/πv. Write a recurrence relation connecting tvv to the tuv for nodes u in the neighborhood of v, and use the relation to demonstrate that tuv ≤ 2m − d(v) for each such u.