# 3.7 Extremal characterizations and mean hitting times

###### Theorem 3.36 (Extremal characterization of mean commute times)

For distinct states $i$ and $a$, the mean commute time satisfies

 $E_{i}T_{a}+E_{a}T_{i}=\sup\{1/\mbox{{\cal E}}(g,g):0\leq g\leq 1,\ g(i)=1,\ % g(a)=0\}$ (3.90)

and the sup is attained by $g(j)=P_{j}(T_{i}. In discrete time, for a subset $A$ and a state $i\not\in A$,

 $A$ (3.91)

and the inf is attained by $g(j)=P_{j}(T_{i}. Equation (3.91) remains true in continuous time, with $\pi_{i}$ replaced by $q_{i}\pi_{i}$ on the left.

Proof. As noted at (3.28), form (3.90) follows (in either discrete or continuous time) from form (3.91) with $A=\{a\}$. To prove (3.91), consider $g$ satisfying the specified boundary conditions. Inspecting (3.74), the contribution to $\mbox{{\cal E}}(g,g)$ involving a fixed state $j$ is

 $\sum_{k\neq j}\pi_{j}p_{jk}(g(k)-g(j))^{2}.$ (3.92)

As a function of $g(j)$ this is minimized by

 $g(j)=\sum_{k}p_{jk}g(k).$ (3.93)

Thus the $g$ which minimizes ${\cal E}$ subject to the prescribed boundary conditions on $A\cup\{i\}$ must satisfy (3.93) for all $j\not\in A\cup\{i\}$, and by Chapter 2 margin: 9/10/99 versionLemma 27 the unique solution of these equations is $g(j)=P_{j}(T_{i}. Now apply to this $g$ the general expression (3.75):

 $\mbox{{\cal E}}(g,g)=\sum_{j}\pi_{j}g(j)\left(g(j)-\sum_{k}p_{jk}g(k)\right).$

For $j\not\in A\cup\{i\}$ the factor $(g(j)-\sum_{k}p_{jk}g(k))$ equals zero, and for $j\in A$ we have $g(j)=0$, so only the $j=i$ term contributes. Thus

 $\displaystyle\mbox{{\cal E}}(g,g)$ $\displaystyle=$ $\displaystyle\pi_{i}\left(1-\sum_{k}p_{ik}g(k)\right)$ (3.94) $\displaystyle=$ $\displaystyle\pi_{i}(1-P_{i}(T^{+}_{i} $\displaystyle=$ $\displaystyle\pi_{i}P_{i}(T_{A}

giving (3.91).

The analogous result for two disjoint subsets $A$ and $B$ is a little complicated to state. The argument above shows that

 $A$

is attained by $g_{0}(j)=P_{j}(T_{B} and that this $g_{0}$ satisfies

 $\mbox{{\cal E}}(g_{0},g_{0})=\sum_{i\in B}\pi_{i}P_{i}(T_{A} (3.95)

We want to interpret the reciprocal of this quantity as a mean time for the chain to commute from $A$ to $B$ and back. Consider the stationary chain $(X_{t};-\infty. We can define what is technically called a “marked point process” which records the times at which $A$ is first visited after a visit to $B$ and vice versa. Precisely, define $Z_{t}$ taking values in $\{\alpha,\beta,\delta\}$ by

 $\exists s

So the times $t$ when $Z_{t}=\beta$ are the times of first return to $B$ after visiting $A$, and the times $t$ when $Z_{t}=\alpha$ are the times of first return to $A$ after visiting $B$. Now $(Z_{t})$ is a stationary process. By considering the time-reversal of $X$, we see that for $i\in B$

 $P(X_{0}=i,\,Z_{0}=\beta)=P(X_{0}=i,\,T_{A}

So  (3.95) shows $P(Z_{0}=\beta)=\mbox{{\cal E}}(g_{0},g_{0})$. If we define $T_{BAB}$, “the typical time to go from $B$ to $A$ and back to $B$”, to have the conditional distribution of margin: (discrete time chain) $\min\{t\geq 1:Z_{t}=\beta\}$ given $Z_{0}=\beta$, then Kac’s formula for the (non-Markov) stationary process $Z$ (see e.g. [133] Theorem 6.3.3) says that $ET_{BAB}=1/P(Z_{0}=\beta)$. So we have proved

###### Corollary 3.37
 $A$

and the sup is attained by $g(i)=P_{i}(T_{B}.

As another interpretation of this quantity, define

 $\rho_{B}(\cdot)=P(X_{0}\in\cdot\,|\,Z_{0}=\beta),\ \ \rho_{A}(\cdot)=P(X_{0}% \in\cdot\,|\,Z_{0}=\alpha).$

Interpret $\rho_{B}$ and $\rho_{A}$ as the distribution of hitting places on $B$ and on $A$ in the commute process. It is intuitively clear, and not hard to verify, that

 $P_{\rho_{A}}(X(T_{B})\in\cdot)=\rho_{B}(\cdot),\ \ P_{\rho_{B}}(X(T_{A})\in% \cdot)=\rho_{A}(\cdot)$
 $ET_{BAB}=E_{\rho_{B}}T_{A}+E_{\rho_{A}}T_{B}.$

In particular

 $\min_{i\in B}E_{i}T_{A}+\min_{i\in A}E_{i}T_{B}\leq ET_{BAB}\leq\max_{i\in B}E% _{i}T_{A}+\max_{i\in A}E_{i}T_{B}.$

## 3.7.1 Thompson’s principle and leveling networks

Theorem 3.36 was stated in terms of (reversible) Markov chains. Rephrasing in terms of discrete-time random walk on a weighted graph gives the usual “electrical network” formulation of the Dirichlet principle stated below, using (3.77),(3.91) and (3.94). Recall from Proposition 3.10 that the effective resistance $r$ between $v_{0}$ and $A$ is, in terms of the random walk,

 $r=\frac{1}{w_{v_{0}}P_{v_{0}}(T_{A} (3.96)
###### Proposition 3.38 (The Dirichlet principle)

Take a weighted graph and fix a vertex $v_{0}$ and a subset $A$ of vertices not containing $v_{0}$. Then the quantity $\frac{1}{2}\sum_{i}\sum_{j}w_{ij}(g(j)-g(i))^{2}$ is minimized, over all functions $g:I\rightarrow[0,1]$ with $g(v_{0})=1$ and $g(\cdot)=0$ on $A$, by the function $g(i):\equiv P_{i}(T_{v_{0}} (where probabilities refer to random walk on the weighted graph), and the minimum value equals $1/r$, where $r$ is the effective resistance (3.96).

There is a dual form of the Dirichlet principle, which following Doyle and Snell [131] we call

###### Proposition 3.39 (Thompson’s principle)

Take a weighted graph and fix a vertex $v_{0}$ and a subset $A$ of vertices not containing $v_{0}$. Let ${\bf f}=f_{ij}$ denote a unit flow from $v_{0}$ to $A$. Then $\frac{1}{2}\sum_{i}\sum_{j}(f^{2}_{ij}/w_{ij})$ is minimized, over all such flows, by the flow ${\bf f}^{v_{0}\rightarrow A}$ [defined at (3.18)] associated with the random walk from $v_{0}$ to $A$, and the minimum value equals the effective resistance $r$ appearing in (3.96).

Recall that a flow is required to have $f_{ij}=0$ whenever $w_{ij}=0$, and interpret sums $\sum_{i}\sum_{j}$ as sums over ordered pairs $(i,j)$ with $w_{ij}>0$.

Proof. Write $\psi({\bf f}):=\frac{1}{2}\sum_{i}\sum_{j}(f^{2}_{ij}/w_{ij})$. By formula (3.25) relating the random walk notions of “flow” and “potential”, the fact that $\psi({\bf f}^{v_{0}\rightarrow A})=r$ is immediate from the corresponding equality in the Dirichlet principle. So the issue is to prove that for a unit flow ${\bf f}^{*}$, say, attaining the minimum of $\psi({\bf f})$, we have $\psi({\bf f}^{*})=\psi({\bf f}^{v_{0}\rightarrow A})$. To prove this, consider two arbitrary paths $(y_{i})$ and $(z_{j})$ from $v_{0}$ to $A$, and let ${\bf f}^{\varepsilon}$ denote the flow ${\bf f}^{*}$ modified by adding flow rates $+\varepsilon$ along the edges $(y_{i},y_{i+1})$ and by adding flow rates $-\varepsilon$ along the edges $(z_{i},z_{i+1})$. Then ${\bf f}^{\varepsilon}$ is still a unit flow from $v_{0}$ to $A$. So the function $\varepsilon\rightarrow\psi({\bf f}^{\varepsilon})$ must have derivative zero at $\varepsilon=0$, and this becomes the condition that

 $\sum_{i}(f^{*}_{y_{i},y_{i+1}}/w_{y_{i},y_{i+1}})=\sum_{i}(f^{*}_{z_{i},z_{i+1% }}/w_{z_{i},z_{i+1}}).$

So the sum is the same for all paths from $v_{0}$ to $A$. Fixing $x$, the sum must be the same for all paths from $x$ to $A$, because two paths from $x$ to $A$ could be extended to paths from $v_{0}$ to $A$ by appending a common path from $v_{0}$ to $x$. It follows that we can define $g^{*}(x)$ as the sum $\sum_{i}(f^{*}_{x_{i},x_{i+1}}/w_{x_{i},x_{i+1}})$ over some path $(x_{i})$ from $x$ to $A$, and the sum does not depend on the path chosen. So margin: (This is essentially the same argument used in Section 3.3.2.)

 $(x,z)$ (3.97)

The fact that ${\bf f}^{*}$ is a flow means that, for $x\not\in A\cup\{v_{0}\}$,

 $0=\sum_{z:w_{xz}>0}f^{*}_{xz}=\sum_{z}w_{xz}(g^{*}(x)-g^{*}(z)).$

So $g^{*}$ is a harmonic function outside $A\cup\{v_{0}\}$, and $g^{*}=0$ on $A$. So by the uniqueness result (Chapter 2 margin: 9/10/99 versionLemma 27) we have that $g^{*}$ must be proportional to $g$, the minimizing function in Proposition 3.38. So ${\bf f}^{*}$ is proportional to ${\bf f}^{v_{0}\rightarrow A}$, because the relationship (3.97) holds for both, and then ${\bf f}^{*}={\bf f}^{v_{0}\rightarrow A}$ because both are unit flows.

A remarkable statistical interpretation was discussed in a monograph of Borre and Meissl [57]. Imagine a finite set of locations such as hilltops. For each pair of locations $(i,j)$ with a clear line-of-sight, measure the elevation difference $D_{ij}=$ (height of $j$ minus height of $i$). Consider the associated graph [whose edges are such pairs $(i,j)$], and suppose it is connected. Take one location $v_{0}$ as a benchmark “height $0$”. If our measurements were exact we could determine the height of location $x$ by adding the $D$’s along a path from $v_{0}$ to $x$, and the sum would not depend on the path chosen. But suppose our measurements contain random errors. Precisely, suppose $D_{i,j}$ equals the true height difference $h(j)-h(i)$ plus an error $Y_{ij}$ which has mean $0$ and variance $1/w_{ij}$ and is independent for different measurements. Then it seems natural to estimate the height of $x$ by taking some average $\hat{h}(x)$ over paths from $v_{0}$ to $x$, and it turns out that the “best” way to average is to use the random walk from $v_{0}$ to $x$ and average (over realizations of the walk) the net height climbed by the walk.

In mathematical terms, the problem is to choose weights $f_{ij}$, not depending on the function $h$, such that

 $\hat{h}(x):=\frac{1}{2}\sum_{i}\sum_{j}f_{ij}D_{ij}$

has $E\hat{h}(x)=h(x)$ and minimal variance. It is not hard to see that the former “unbiased” property holds iff $f$ is a unit flow from $v_{0}$ to $x$. Then

 ${\rm var}\ \hat{h}(x)=\frac{1}{4}\sum_{i}\sum_{j}f^{2}_{ij}\mbox{var}(D_{ij})=% \frac{1}{4}\sum_{i}\sum_{j}\frac{f^{2}_{ij}}{w_{ij}}$

and Proposition 3.39 says this is minimized when we use the flow from $v_{0}$ to $x$ obtained from the random walk on the weighted graph. But then

 $\hat{h}(x)=E_{v_{0}}\sum_{t=1}^{T_{x}}D_{X_{t-1}X_{t}},$

the expectation referring to the random walk.

## 3.7.2 Hitting times and Thompson’s principle

Using the commute interpretation of resistance (Corollary 3.11) to translate Thompson’s principle into an assertion about mean commute times gives the following.

###### Corollary 3.40

For random walk on a weighted graph and distinct vertices $v$ and $a$,

 $a$

and the $\min$ is attained by the flow ${\bf f}^{a\rightarrow v}$ associated with the random walk.

Comparing with Theorem 3.36 we have two different extremal characterizations of mean commute times, as a sup over potential functions and as an inf over flows. In practice this “flow” form is less easy to use than the “potential” form, because writing down a flow ${\bf f}$ is harder than writing down a function $g$. But, when we can write down and calculate with some plausible flow, it gives upper bounds on mean commute times.

One-sided mean hitting times $E_{i}T_{j}$ don’t have simple extremal characterizations of the same kind, with the exception of hitting times from stationarity. To state the result, we need two definitions. First, given a probability distribution $\rho$ on vertices, a unit flow from $a$ to $\rho$ is a flow $f$ satisfying

 $f_{(i)}=1_{(i=a)}-\rho_{i}\mbox{\ \ for all\ }i;$ (3.98)

more generally, a unit flow from a set $A$ to $\rho$ is defined to satisfy

 $i\in A^{c}$

Now fix a state $a$ and define the special flow ${\bf f}^{a\rightarrow\pi}$ by

 $f_{ij}:=\lim_{t_{0}\rightarrow\infty}E_{a}\sum_{t=1}^{t_{0}}\left(1_{(X_{t-1}=% i,\,X_{t}=j)}-1_{(X_{t-1}=j,\,X_{t}=i)}\right)$ (3.99)

with the usual convention in the periodic case. So $f_{ij}$ is the mean excess of transitions $i\rightarrow j$ compared to transitions $j\rightarrow i$, for the chain started at $a$ and run forever. This is a unit flow from $a$ to $\pi$, in the above sense. Equation (6) (the definition of ${\bf Z}$) in Chapter 2 margin: 9/10/99 versionand reversibility give the first equality, and Chapter 2 margin: 9/10/99 versionLemma 12 gives the last equality, in

 $\displaystyle f_{ij}$ $\displaystyle=$ $\displaystyle Z_{ai}p_{ij}-Z_{aj}p_{ji}$ (3.100) $\displaystyle=$ $\displaystyle\frac{Z_{ia}\pi_{i}p_{ij}}{\pi_{a}}-\frac{Z_{ja}\pi_{j}p_{ji}}{% \pi_{a}}$ $\displaystyle=$ $\displaystyle\frac{(Z_{ia}-Z_{ja})\pi_{i}p_{ij}}{\pi_{a}}$ $\displaystyle=$ $\displaystyle\frac{(E_{j}T_{a}-E_{i}T_{a})w_{ij}}{w},$ (3.101)

switching to “weighted graphs” notation. Note also that the first-step recurrence for the function $i\mapsto Z_{ia}$ is

 $Z_{ia}=\left(1_{(i=a)}-\pi_{a}\right)+\sum_{j}p_{ij}Z_{ja}.$ (3.102)
###### Proposition 3.41

For random walk on a weighted graph and a subset $A$ of vertices,

 $\displaystyle E_{\pi}T_{A}$ $\displaystyle=$ $A$ $\displaystyle=$ $A$

When $A$ is a singleton $\{a\}$, the minimizing flow is the flow ${\bf f}^{a\rightarrow\pi}$ defined above, and the maximizing function $g$ is $g(i)=Z_{ia}/Z_{aa}$. For general $A$ the maximizing function $g$ is $g(i)=1-\frac{E_{i}T_{A}}{E_{\pi}T_{A}}$.

margin: Added the final observation about general $A$

Proof. Suppose first that $A=\{a\}$. We start by showing that the extremizing flow, ${\bf f}^{*}$ say, is the asserted ${\bf f}^{a\rightarrow\pi}$. By considering adding to ${\bf f}^{*}$ a flow of size $\varepsilon$ along a directed cycle, and copying the argument for (3.97) in the proof of Proposition 3.39, there must exist a function $g^{*}$ such that

 $g^{*}(x)-g^{*}(z)=\frac{f^{*}_{xz}}{w_{xz}}\mbox{\ for each edge\ }(x,z).$ (3.103)

The fact that ${\bf f}^{*}$ is a unit flow from $a$ to $\pi$ says that

 $1_{(x=a)}-\pi_{x}=\sum_{z}f^{*}_{xz}=\sum_{z}w_{xz}(g^{*}(x)-g^{*}(z))$

which implies

 $\frac{1_{(x=a)}-\pi_{x}}{w_{x}}=\sum_{z}p_{xz}(g^{*}(x)-g^{*}(z))=g^{*}(x)-% \sum_{z}p_{xz}g^{*}(z).$

Since $w_{x}=w\pi_{x}$ and $1/\pi_{a}=E_{a}T^{+}_{a}$, this becomes

 $g^{*}(x)=\sum_{z}p_{xz}g^{*}(z)-w^{-1}\left(1-(E_{a}T^{+}_{a})1_{(x=a)}\right).$

Now these equations have a unique solution $g^{*}$, up to an additive constant, because the difference between two solutions is a harmonic function. (Recall Chapter 2 margin: 9/10/99 versionCorollary 28.) On the other hand, a solution is $g^{*}(x)=-\frac{E_{x}T_{a}}{w}$, by considering the first-step recurrence for $E_{x}T^{+}_{a}$. So by (3.103) $f^{*}_{xz}=(E_{z}T_{a}-E_{x}T_{a})w_{xz}/w$, and so ${\bf f}^{*}={\bf f}^{a\rightarrow\pi}$ by (3.101).

Now consider the function $g$ which minimizes $\mbox{{\cal E}}(g,g)$ under the constraints $\sum_{i}\pi_{i}g(i)=0$ and $g(a)=1$. By introducing a Lagrange multiplier $\gamma$ we may consider $g$ as minimizing $\mbox{{\cal E}}(g,g)+\gamma\sum_{i}\pi_{i}g(i)$ subject to $g(a)=1$. Repeating the argument at (3.92), the minimizing $g$ satisfies

 $-2\sum_{k\neq j}\pi_{j}p_{jk}(g(k)-g(j))\ +\gamma\pi_{j}=0,\ \ j\neq a.$

Rearranging, and introducing a term $\beta 1_{(j=a)}$ to cover the case $j=a$, we have

 $g(j)=\sum_{k}p_{jk}g(k)\ -(\gamma/2)+\beta 1_{(j=a)}\mbox{\ for all\ }j,$

for some $\gamma,\beta$. Because $\sum_{j}\pi_{j}g(j)=0$ we have

 $0=0-(\gamma/2)+\beta\pi_{a},$

allowing us to rewrite the equation as

 $g(j)=\sum_{k}p_{jk}g(k)\ +\beta(1_{(j=a)}-\pi_{a}).$

By the familiar “harmonic function” argument this has a unique solution, and (3.102) shows the solution is $g(j)=\beta Z_{ja}$. Then the constraint $g(a)=1$ gives $g(j)=Z_{ja}/Z_{aa}$.

Next consider the relationship between the flow ${\bf f}={\bf f}^{a\rightarrow\pi}$ and the function $g(i)\equiv Z_{ia}/Z_{aa}$. We have margin: Chapter 2 reference in following display is to 9/10/99 version.

 $\displaystyle w\ \frac{f^{2}_{ij}}{w_{ij}}$ $\displaystyle=$ $\displaystyle(E_{j}T_{a}-E_{i}T_{a})^{2}\frac{w_{ij}}{w}\mbox{\ \ by~{}(\ref{% flT})}$ $\displaystyle=$ $\displaystyle(E_{\pi}T_{a})^{2}\frac{w_{ij}}{w}\left(\frac{E_{j}T_{a}-E_{i}T_{% a}}{E_{\pi}T_{a}}\right)^{2}$ $\displaystyle=$ $\displaystyle(E_{\pi}T_{a})^{2}\frac{w_{ij}}{w}\left(\frac{Z_{ia}-Z_{ja}}{Z_{% aa}}\right)^{2}\mbox{\ \ by Chapter~{}2{} Lemmas~{}11, 12}$ $\displaystyle=$ $\displaystyle(E_{\pi}T_{a})^{2}\frac{w_{ij}}{w}\ (g(i)-g(j))^{2}.$

Thus it is enough to prove

 $w\frac{1}{2}\sum_{i}\sum_{j}\frac{f^{2}_{ij}}{w_{ij}}=E_{\pi}T_{a}$ (3.104)

and it will then follow that

 $1/\mbox{{\cal E}}(g,g)=E_{\pi}T_{a}.$

To prove (3.104), introduce a parameter $\varepsilon$ (which will later go to $0$) and a new vertex $z$ and edge-weights $w_{iz}=\varepsilon w_{i}$. Writing superscripts $\ {}^{\varepsilon}$ to refer to this new graph and its random walk, the equation becomes $w^{\varepsilon}_{iz}:=\varepsilon w_{i}$ and Corollary 3.40 says

 $E^{\varepsilon}_{a}T_{z}+E^{\varepsilon}_{z}T_{a}=w^{\varepsilon}\frac{1}{2}% \sum_{i\in I^{\varepsilon}}\sum_{j\in I^{\varepsilon}}\frac{(f^{\varepsilon}_{% ij})^{2}}{w^{\varepsilon}_{ij}}$ (3.105)

where ${\bf f}^{\varepsilon}$ is the special unit flow from $a$ to $z$ associated with the new graph (which has vertex set $I^{\varepsilon}:=I\cup\{z\}$). We want to interpret the ingredients to (3.105) in terms of the original graph. Clearly $w^{\varepsilon}=w(1+2\varepsilon)$. The new walk has chance $\varepsilon/(1+\varepsilon)$ to jump to $z$ from each other vertex, so $E^{\varepsilon}_{a}T_{z}=(1+\varepsilon)/\varepsilon$. Starting from $z$, after one step the new walk has the stationary distribution $\pi$ on the original graph, and it follows easily that $E^{\varepsilon}_{z}T_{a}=1+E_{\pi}T_{a}(1+O(\varepsilon))$. We can regard the new walk up to time $T_{z}$ as the old walk sent to $z$ at a random time $U^{\varepsilon}$ with Geometric($\varepsilon/(1+\varepsilon)$) distribution, so for $i\neq z$ and $j\neq z$ the flow $f^{\varepsilon}_{ij}$ is the expected net number of transitions $i\rightarrow j$ by the old walk up to time $U^{\varepsilon}$. From the spectral representation it follows easily that $f^{\varepsilon}_{ij}=f_{ij}+O(\varepsilon)$. Similarly, for $i\neq z$ we have $-f^{\varepsilon}_{zi}=f^{\varepsilon}_{iz}=P_{a}(X(U^{\varepsilon}-1)=i)=\pi_{% i}+O(\varepsilon)$; noting that $\sum_{i\in I}f^{\varepsilon}_{iz}=1$, the total contribution of such terms to the double sum in (3.105) is

 $\displaystyle 2\sum_{i\in I}\frac{(\pi_{i}+f^{\varepsilon}_{iz}-\pi_{i})^{2}}{% \varepsilon w_{i}}$ $\displaystyle=$ $\displaystyle\frac{2}{w\varepsilon}\sum_{i\in I}\frac{(\pi_{i}+f^{\varepsilon}% _{iz}-\pi_{i})^{2}}{\pi_{i}}$ $\displaystyle=$ $\displaystyle\frac{2}{w\varepsilon}\left(1+\sum_{i\in I}\frac{(f^{\varepsilon}% _{iz}-\pi_{i})^{2}}{\pi_{i}}\right)=\frac{2}{w\varepsilon}+O(\varepsilon).$

So (3.105) becomes

 $\frac{1+\varepsilon}{\varepsilon}+1+E_{\pi}T_{a}+O(\varepsilon)=w(1+2% \varepsilon)\left(\frac{1}{2}\sum_{i\in I}\sum_{j\in I}\frac{f^{2}_{ij}}{w_{ij% }}\ +\frac{1}{w\varepsilon}\right)+O(\varepsilon)$

Subtracting $(1+2\varepsilon)/\varepsilon$ from both sides and letting $\varepsilon\rightarrow 0$ gives the desired (3.104). This concludes the proof for the case $A=\{a\}$, once we use the mean hitting time formula to verify

 $g(i):\equiv{\textstyle\frac{Z_{ia}}{Z_{aa}}}=1-{\textstyle\frac{E_{i}T_{a}}{E_% {\pi}T_{a}}}.$

Finally, the extension to general $A$ is an exercise in use of the chain, say $X^{*}$, in which the set $A$ is collapsed to a single state $a$. Recall Chapter 2 margin: 9/10/99 versionSection 7.3. In particular,

 $w^{*}_{ij}=w_{ij},\ i,j\in A^{c};\quad w^{*}_{ia}=\sum_{k\in A}w_{ik},\ i\in A% ^{c};\quad w^{*}_{aa}=\sum_{k\in A}\sum_{l\in A}w_{kl};\quad w^{*}=w.$

We now sketch the extension. First, $E_{\pi}T_{A}=E^{*}_{\pi^{*}}T_{a}$. Then the natural one-to-one correspondence between functions $g$ on $I$ with $g(\cdot)=1$ on $A$ and $\sum_{i\in I}\pi_{i}g(i)=0$ and functions $g^{*}$ on $I^{*}$ with $g^{*}(a)=0$ and $\sum_{i\in I^{*}}\pi^{*}_{i}g^{*}(i)=0$ gives a trivial proof of

 $A$

It remains to show that

 $A$ (3.106) $\displaystyle=$ $a$

where

 $\Psi({\bf f}):=\frac{1}{2}\sum_{i\in I}\sum_{j\in I}(f^{2}_{ij}/w_{ij}),\quad% \Psi^{*}({\bf f^{*}}):=\frac{1}{2}\sum_{i\in I^{*}}\sum_{j\in I^{*}}((f^{*}_{% ij})^{2}/w^{*}_{ij}).$

Indeed, given a unit flow ${\bf f}$ from $A$ to $\pi$, define $f^{*}_{ij}$ as $f_{ij}$ if $i,j\in A^{c}$ and as $\sum_{k\in A}f_{ik}$ if $i\in A^{c}$ and $j=a$. One can check that ${\bf f^{*}}$ is a unit flow from $a$ to $\pi^{*}$ (the key observation being that $\sum_{i\in A}\sum_{j\in A}f_{ij}=0$) and, using the Cauchy–Schwarz inequality, that $\Psi^{*}({\bf f^{*}})\leq\Psi({\bf f})$. Conversely, given a unit flow ${\bf f^{*}}$ from $a$ to $\pi^{*}$, define $f_{ij}$ as $f^{*}_{ij}$ if $i,j\in A^{c}$, as $f^{*}_{ia}w_{ij}/\sum_{k\in A}w_{ik}$ if $i\in A^{c}$ and $j\in A$, and as $0$ if $i,j\in A$. One can check that ${\bf f}$ is a unit flow from $A$ to $\pi$ and that $\Psi({\bf f})=\Psi({\bf f^{*}})$. We have thus established (3.106), completing the proof.

###### Corollary 3.42

For chains with transition matrices ${\bf P},\tilde{{\bf P}}$ and the same stationary distribution $\pi$,

 $\min_{i\neq j}\frac{p_{ij}}{\tilde{p}_{ij}}\leq\frac{\tilde{E_{\pi}}T_{a}}{E_{% \pi}T_{a}}\leq\max_{i\neq j}\frac{p_{ij}}{\tilde{p}_{ij}}.$

Proof. Plug the minimizing flow ${\bf f}^{a\rightarrow\pi}$ for the ${\bf P}$-chain into Proposition 3.41 for the $\tilde{{\bf P}}$-chain to get the second inequality. The first follows by reversing the roles of ${\bf P}$ and $\tilde{{\bf P}}$.