This is a convenient place to record some definitions. A flow f $=(f_{ij})$ on a graph is required only to satisfy the conditions

$(i,j)$ |

So the net flow out of $i$ is $f_{(i)}:=\sum_{j\neq i}f_{ij}$, and by symmetry $\sum_{i}f_{(i)}=0$. We will be concerned with flows satisfying extra conditions. Given disjoint non-empty subsets $A,B$ of vertices, a unit flow from $B$ to $A$ is a flow satisfying

$\sum_{i\in B}f_{(i)}=1,\ \ \ \ \ f_{(j)}=0\mbox{\ \ for all\ }j\not\in A\cup B$ | (3.17) |

which implies $\sum_{i\in A}f_{(i)}=-1$. Given a Markov chain $X$ (in particular, given a weighted graph we can use the random walk) we can define a special flow as follows. Given $v_{0}\not\in A$, define ${\bf f}^{v_{0}\rightarrow A}$ by

$f_{ij}:=E_{v_{0}}\sum_{t=1}^{T_{A}}\left(1_{(X_{t-1}=i,X_{t}=j)}-1_{(X_{t-1}=j% ,X_{t}=i)}\right).$ | (3.18) |

So $f_{ij}$ is the mean number of transitions $i\rightarrow j$ minus the mean number of transitions $j\rightarrow i$, for the chain started at $v_{0}$ and run until hitting $A$. Clearly ${\bf f}^{v_{0}\rightarrow A}$ is a unit flow from $v_{0}$ to $A$. Note that the mean net transitions definition of $f_{ij}$ works equally well in continuous time to provide a unit flow ${\bf f}^{v_{0}\rightarrow A}$ from $v_{0}$ to $A$.

In Section 3.7.2 we will define the notion of “a unit flow from $v_{0}$ to a probability distribution $\rho$” and utilize a special unit flow from $v_{0}$ to the stationary distribution.

Given a weighted graph, consider the graph as an electrical network, where a wire linking $v$ and $x$ has conductance $w_{vx}$, i.e., resistance $1/w_{vx}$. Fix a vertex $v_{0}$ and a subset $A$ of vertices not containing $v_{0}$. Apply voltage $1$ at $v_{0}$ and ground (i.e., set at voltage $0$) the set $A$ of vertices. As we shall see, this determines the voltage $g(v)$ at each vertex $v$; in particular,

$g(v_{0})=1;\ \ g(\cdot)=0\mbox{\ on\ }A.$ | (3.19) |

Physically, according to Ohm’s law,

$\mbox{Current}=\frac{\mbox{Potential difference}}{\mbox{Resistance}}$ |

for each wire; that is, the current $I_{vx}$ along each wire $(v,x)$ satisfies

$I_{vx}=(g(v)-g(x))w_{vx}.$ | (3.20) |

Clearly, $I$ is a flow, and according to Kirchoff’s node law

$I_{(v)}=0,\ \ v\notin\{v_{0}\}\cup A.$ | (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 $g$ and a flow $I$, called voltage and current, respectively, satisfying (3.20)–(3.21) and the normalization (3.19). As it turns out, these three conditions specify $g$ [and hence also $I$, by (3.20)] uniquely since (3.20)–(3.21) imply

$g(v)=\sum_{x}p_{vx}g(x),\ \ v\not\in\{v_{0}\}\cup A$ | (3.22) |

with $p_{vx}$ 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 $g$ is the unique function
satisfying (3.22)
and (3.19), then $I$ 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 ${\bf f}^{v_{0}\rightarrow A}$ defined at (3.18).

Consider a weighted graph as an electrical network, where a wire linking $v$ and $x$ has conductance $w_{vx}$. Suppose that the voltage function $g$ satisfies (3.19). Then the voltage at any vertex $v$ is given in terms of the associated random walk by

$g(v)=P_{v}(T_{v_{0}}<T_{A})\in[0,1]$ | (3.23) |

and the current $I_{vx}$ along each wire $(v,x)$ is $f_{vx}/r$, where ${\bf f}={\bf f}^{v_{0}\rightarrow A}$ and

$r=\frac{1}{w_{v_{0}}P_{v_{0}}(T_{A}<T^{+}_{v_{0}})}\in(0,\infty).$ | (3.24) |

Since ${\bf f}$ is a unit flow from $v_{0}$ to $A$ and $g(v_{0})=1$, we find $I_{(v_{0})}=g(v_{0})/r$. Since $g=0$ on $A$, it is thus natural in light of Ohm’s law to regard the entire network as effectively a single conductor from $v_{0}$ to $A$ with resistance $r$; for this reason $r$ is called the effective resistance between $v_{0}$ and $A$. 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.,

$\frac{f_{vx}}{r}=(g(v)-g(x))w_{vx}.$ | (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 $A$ is a
singleton $a$,
by the collapsing principle ^{†}^{†}margin: 9/10/99 version(Chapter 2 Section 7.3).
Now by the Markov property

$\displaystyle f_{vx}$ | $\displaystyle=$ | $v$ | ||

$x$ |

Chapter 2 Lemma 9 gives a formula for the expectations above, and using $\pi_{v}p_{vx}=\pi_{x}p_{xv}=w_{vx}/w$ we get

$\frac{w}{w_{vx}}f_{vx}=E_{a}T_{v}-E_{v_{0}}T_{v}-E_{a}T_{x}+E_{v_{0}}T_{x}.$ | (3.26) |

And ^{†}^{†}margin: 9/10/99 versionChapter 2 Corollaries 8 and 10 give a formula
for $g$:

$g(v)=(E_{v}T_{a}+E_{a}T_{v_{0}}-E_{v}T_{v_{0}})\pi_{v_{0}}P_{v_{0}}(T_{a}<T^{+% }_{v_{0}})$ |

which leads to

$\frac{g(v)-g(x)}{\pi_{v_{0}}P_{v_{0}}(T_{a}<T^{+}_{v_{0}})}=E_{v}T_{a}-E_{x}T_% {a}-E_{v}T_{v_{0}}+E_{x}T_{v_{0}}.$ | (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 $v_{0},x,a,v,v_{0}$, and the result (3.25) follows after rearrangement, using $\pi_{v_{0}}=w_{v_{0}}/w$.

Remark. Note that, when identifying a reversible chain with an electrical network, the procedure of collapsing the set $A$ of states of the chain to a singleton corresponds to the procedure of shorting together the vertices $A$ 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)

$\frac{1}{\pi_{v}P_{v}(T_{a}<T^{+}_{v})}=E_{v}T_{a}+E_{a}T_{v},\ \ v\neq a,$ | (3.28) |

where we may call the right side the mean commute time between $v$ and $a$. [For continuous-time chains, $\pi_{v}$ is replaced by $q_{v}\pi_{v}$ in (3.28).] Comparing with (3.24) and using $\pi_{v}=w_{v}/w$ gives

Given two vertices $v,a$ in a weighted graph, the effective resistance $r_{va}$ between $v$ and $a$ is related to the mean commute time of the associated random walk by

$E_{v}T_{a}+E_{a}T_{v}=wr_{va}.$ |

Note that the Corollary takes a simple form in the case of unweighted graphs:

$E_{v}T_{a}+E_{a}T_{v}=2|\mbox{${\cal E}$}|r_{va}.$ | (3.29) |

Note also that the Corollary does not hold so simply if $a$ and $v$ 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
$r_{vx}$ across an edge $(v,x)$ is at most the resistance $1/w_{vx}$
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 $n$-vertex graph, let $r_{e}$ be the effective resistance between the ends $(a,b)$ of an edge $e$. Then

$\sum_{e}r_{e}w_{e}=n-1.$ |

$*\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\$ |

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.

$*\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\$ |

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