3 Reversible Markov Chains (September 10, 2002)

3.3 Electrical networks

3.3.1 Flows

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

fij={-fjiif (i,j)(i,j) is an edge0if not.f_{ij}=\left\{\begin{array}[]{cl}-f_{ji}&\mbox{if $(i,j)$ is an edge}\\ 0&\mbox{if not.}\end{array}\right.

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

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

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

fij:=Ev0t=1TA(1(Xt-1=i,Xt=j)-1(Xt-1=j,Xt=i)).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 fijf_{ij} is the mean number of transitions iji\rightarrow j minus the mean number of transitions jij\rightarrow i, for the chain started at v0v_{0} and run until hitting AA. Clearly 𝐟v0A{\bf f}^{v_{0}\rightarrow A} is a unit flow from v0v_{0} to AA. Note that the mean net transitions definition of fijf_{ij} works equally well in continuous time to provide a unit flow 𝐟v0A{\bf f}^{v_{0}\rightarrow A} from v0v_{0} to AA.

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

3.3.2 The analogy

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

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

Physically, according to Ohm’s law,

Current=Potential differenceResistance\mbox{Current}=\frac{\mbox{Potential difference}}{\mbox{Resistance}}

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

Ivx=(g(v)-g(x))wvx.I_{vx}=(g(v)-g(x))w_{vx}. (3.20)

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

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

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

with pvxp_{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 gg is the unique function satisfying (3.22) and (3.19), then II 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 𝐟v0A{\bf f}^{v_{0}\rightarrow A} defined at (3.18).

Proposition 3.10

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

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

and the current IvxI_{vx} along each wire (v,x)(v,x) is fvx/rf_{vx}/r, where 𝐟=𝐟v0A{\bf f}={\bf f}^{v_{0}\rightarrow A} and

r=1wv0Pv0(TA<Tv0+)(0,).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  v0v_{0} to AA and g(v0)=1g(v_{0})=1, we find I(v0)=g(v0)/rI_{(v_{0})}=g(v_{0})/r. Since g=0g=0 on AA, it is thus natural in light of Ohm’s law to regard the entire network as effectively a single conductor from v0v_{0} to AA with resistance rr; for this reason rr is called the effective resistance between v0v_{0} and AA. 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.,

fvxr=(g(v)-g(x))wvx.\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 AA is a singleton aa, by the collapsing principle margin: 9/10/99 version(Chapter 2 Section 7.3). Now by the Markov property

fvx\displaystyle f_{vx} =\displaystyle= Ev0(number of visits to vv before time TaT_{a})pvx\displaystyle E_{v_{0}}(\mbox{number of visits to $v$ before time $T_{a}$})\ p% _{vx}
-Ev0(number of visits to xx before time TaT_{a})pxv.\displaystyle\quad-E_{v_{0}}(\mbox{number of visits to $x$ before time $T_{a}$})\ p_{xv}.
margin: 9/10/99 version

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

wwvxfvx=EaTv-Ev0Tv-EaTx+Ev0Tx.\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 gg:

g(v)=(EvTa+EaTv0-EvTv0)πv0Pv0(Ta<Tv0+)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

g(v)-g(x)πv0Pv0(Ta<Tv0+)=EvTa-ExTa-EvTv0+ExTv0.\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 v0,x,a,v,v0v_{0},x,a,v,v_{0}, and the result (3.25) follows after rearrangement, using πv0=wv0/w\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 AA of states of the chain to a singleton corresponds to the procedure of shorting together the vertices AA of the electrical network.

3.3.3 Mean commute times

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)

1πvPv(Ta<Tv+)=EvTa+EaTv, va,\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 vv and aa. [For continuous-time chains, πv\pi_{v} is replaced by qvπvq_{v}\pi_{v} in (3.28).] Comparing with (3.24) and using πv=wv/w\pi_{v}=w_{v}/w gives

Corollary 3.11 (commute interpretation of resistance)

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

EvTa+EaTv=wrva.E_{v}T_{a}+E_{a}T_{v}=wr_{va}.

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

EvTa+EaTv=2||rva.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 aa and vv 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 rvxr_{vx} across an edge (v,x)(v,x) is at most the resistance 1/wvx1/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.

3.3.4 Foster’s theorem

The commute interpretation of resistance allows us to rephrase Lemma 3.9 as the following result about electrical networks, due to Foster [153].

Corollary 3.12 (Foster’s Theorem)

In a weighted nn-vertex graph, let rer_{e} be the effective resistance between the ends (a,b)(a,b) of an edge ee. Then

erewe=n-1.\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.

*************************\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\ *\