This is a convenient place to record some definitions. A flow f on a graph is required only to satisfy the conditions
So the net flow out of is , and by symmetry . We will be concerned with flows satisfying extra conditions. Given disjoint non-empty subsets of vertices, a unit flow from to is a flow satisfying
(3.17) |
which implies . Given a Markov chain (in particular, given a weighted graph we can use the random walk) we can define a special flow as follows. Given , define by
(3.18) |
So is the mean number of transitions minus the mean number of transitions , for the chain started at and run until hitting . Clearly is a unit flow from to . Note that the mean net transitions definition of works equally well in continuous time to provide a unit flow from to .
In Section 3.7.2 we will define the notion of “a unit flow from to a probability distribution ” and utilize a special unit flow from to the stationary distribution.
Given a weighted graph, consider the graph as an electrical network, where a wire linking and has conductance , i.e., resistance . Fix a vertex and a subset of vertices not containing . Apply voltage at and ground (i.e., set at voltage ) the set of vertices. As we shall see, this determines the voltage at each vertex ; in particular,
(3.19) |
Physically, according to Ohm’s law,
for each wire; that is, the current along each wire satisfies
(3.20) |
Clearly, is a flow, and according to Kirchoff’s node law
(3.21) |
Regarding the above as intuition arising from the study of physical electrical networks, we can define an electrical network mathematically as a weighted graph together with a function and a flow , called voltage and current, respectively, satisfying (3.20)–(3.21) and the normalization (3.19). As it turns out, these three conditions specify [and hence also , by (3.20)] uniquely since (3.20)–(3.21) imply
(3.22) |
with defined at (3.13), and ††margin: 9/10/99 versionChapter 2 Lemma 27 shows that this equation, together with the boundary conditions (3.19), has a unique solution. Conversely, if is the unique function satisfying (3.22) and (3.19), then defined by (3.20) satisfies (3.21), as required. Thus a weighted graph uniquely determines both a random walk and an electrical network.
The point of this subsection is that the voltage and current functions can be identified in terms of the random walk. Recall the flow defined at (3.18).
Consider a weighted graph as an electrical network, where a wire linking and has conductance . Suppose that the voltage function satisfies (3.19). Then the voltage at any vertex is given in terms of the associated random walk by
(3.23) |
and the current along each wire is , where and
(3.24) |
Since is a unit flow from to and , we find . Since on , it is thus natural in light of Ohm’s law to regard the entire network as effectively a single conductor from to with resistance ; for this reason is called the effective resistance between and . Since (3.19) and (3.21) are clearly satisfied, to establish Proposition 3.10 it suffices by our previous comments to prove (3.20), i.e.,
(3.25) |
Proof of (3.25). Here is a “brute force” proof by writing everything in terms of mean hitting times. First, there is no less of generality in assuming that is a singleton , by the collapsing principle ††margin: 9/10/99 version(Chapter 2 Section 7.3). Now by the Markov property
Chapter 2 Lemma 9 gives a formula for the expectations above, and using we get
(3.26) |
And ††margin: 9/10/99 versionChapter 2 Corollaries 8 and 10 give a formula for :
which leads to
(3.27) |
But the right sides of (3.27) and (3.26) are equal, by the cyclic tour property (Lemma 3.2) applied to the tour , and the result (3.25) follows after rearrangement, using .
Remark. Note that, when identifying a reversible chain with an electrical network, the procedure of collapsing the set of states of the chain to a singleton corresponds to the procedure of shorting together the vertices of the electrical network.
The classical use of the electrical network analogy in the mathematical literature is in the study of the recurrence or transience of infinite-state reversible chains by comparison arguments ††margin: 6/23/01 version(Chapter 13). As discussed in Doyle and Snell [131], the comparisons involve “cutting or shorting”. Cutting an edge, or more generally decreasing an edge’s conductance, can only increase an effective resistance. Shorting two vertices together (i.e., linking them with an edge of infinite conductance), or more generally increasing an edge’s conductance, can only decrease an effective resistance. These ideas can be formalized via the extremal characterizations of Section 3.7 without explicitly relying on the electrical analogy.
In our context of finite-state chains the key observation is the following. For not-necessarily-reversible discrete-time chains we have ††margin: 9/10/99 version(Chapter 2 Corollary 8)
(3.28) |
where we may call the right side the mean commute time between and . [For continuous-time chains, is replaced by in (3.28).] Comparing with (3.24) and using gives
Given two vertices in a weighted graph, the effective resistance between and is related to the mean commute time of the associated random walk by
Note that the Corollary takes a simple form in the case of unweighted graphs:
(3.29) |
Note also that the Corollary does not hold so simply if and are both replaced by subsets—see Corollary 3.37.
Corollary 3.11 apparently was not stated explicitly or exploited until a 1989 paper of Chandra et al [85], but then rapidly became popular in the “randomized algorithms” community. The point is that “cutting or shorting” arguments can be used to bound mean commute times. As the simplest example, it is obvious that the effective resistance across an edge is at most the resistance of the edge itself, and so Corollary 3.11 implies the edge-commute inequality (Corollary 3.8). ††margin: add pointers to uses of cutting and shorting later in book Finally, we can use Corollary 3.11 to get simple exact expressions for mean commute times in some special cases, in particular for birth-and-death processes (i.e., weighted linear graphs) discussed in ††margin: 4/22/96 versionChapter 5.
As with the infinite-space results, the electrical analogy provides a vivid language for comparison arguments, but the arguments themselves can be justified via the extremal characterizations of Section 3.7 without explicit use of the analogy.
The commute interpretation of resistance allows us to rephrase Lemma 3.9 as the following result about electrical networks, due to Foster [153].
In a weighted -vertex graph, let be the effective resistance between the ends of an edge . Then
CONVENTION.
For the rest of the chapter we make the convention that we are dealing with a finite-state, irreducible, reversible chain, and we will not repeat the “reversible” hypothesis in each result. Instead we will say “general chain” to mean not-necessarily-reversible chain.