4 Hitting and Convergence Time, and Flow Rate, Parameters for Reversible Markov Chains (October 11, 1994)

4.1 The maximal mean commute time τ*\tau^{*}

We start by repeating the definition

τ*maxij(EiTj+EjTi)\tau^{*}\equiv\max_{ij}(E_{i}T_{j}+E_{j}T_{i}) (4.1)

and recalling what we already know. Obviously

maxijEiTjτ*2maxijEiTj\max_{ij}E_{i}T_{j}\leq\tau^{*}\leq 2\max_{ij}E_{i}T_{j}

and by Chapter 3 Lemma yyy

maxjEπTjτ*4maxjEπTj.\max_{j}E_{\pi}T_{j}\leq\tau^{*}\leq 4\max_{j}E_{\pi}T_{j}. (4.2)

Arguably we could have used maxijEiTj\max_{ij}E_{i}T_{j} as the “named” parameter, but the virtue of τ*\tau^{*} is the resistance interpretation of Chapter 3 Corollary yyy.

Lemma 4.1

For random walk on a weighted graph,

τ*=wmaxijrij\tau^{*}=w\max_{ij}r_{ij}

where rijr_{ij} is the effective resistance between ii and jj.

In Chapter 3 Proposition yyy we proved lower bounds for any nn-state discrete-time reversible chain:

τ*2(n-1)\tau^{*}\geq 2(n-1)
maxijEiTjn-1\max_{ij}E_{i}T_{j}\geq n-1

which are attained by random walk on the complete graph. Upper bounds will be discussed extensively in Chapter 6, but let’s mention two simple ideas here. Consider a path i=i0,i1,,im=ji=i_{0},i_{1},\ldots,i_{m}=j, and let’s call this path γij\gamma_{ij} (because we’ve run out of symbols whose names begin with “p”!) This path, considered in isolation, has “resistance”

r(γij)eγij1/wer(\gamma_{ij})\equiv\sum_{e\in\gamma_{ij}}1/w_{e}

which by the Monotonicity Law is at least the effective resistance rijr_{ij}. Thus trivially

τ*wmaxi,jminpaths γijr(γij).\tau^{*}\leq w\max_{i,j}\min_{\mbox{paths }\gamma_{ij}}r(\gamma_{ij}). (4.3)

A more interesting idea is to combine the max-flow min-cut theorem (see e.g. [86] sec. 5.4) with Thompson’s principle (Chapter 3 Corollary yyy). Given a weighted graph, define

cminAiAjAcwijc\equiv\min_{A}\sum_{i\in A}\sum_{j\in A^{c}}w_{ij} (4.4)

the minmin over proper subsets AA. The max-flow min-cut theorem implies that for any pair a,ba,b there exists a flow 𝐟{\bf f} from aa to bb of size cc such that |fij|wij|f_{ij}|\leq w_{ij} for all edges (i,j)(i,j). So there is a unit flow from aa to bb such that |fe|c-1we|f_{e}|\leq c^{-1}w_{e} for all edges ee. It is clear that by deleting any flows around cycles we may assume that the flow through any vertex ii is at most unity, and so

j|fij|2 for all ii, and =1=1 for i=a,bi=a,b.\sum_{j}|f_{ij}|\leq 2\mbox{ for all $i$, and $=1$ for $i=a,b$}. (4.5)

So

EaTb+EbTa\displaystyle E_{a}T_{b}+E_{b}T_{a} \displaystyle\leq wefe2we by Thompson’s principle\displaystyle w\sum_{e}\frac{f^{2}_{e}}{w_{e}}\mbox{ by Thompson's principle }
\displaystyle\leq wce|fe|\displaystyle\frac{w}{c}\sum_{e}|f_{e}|
\displaystyle\leq wc(n-1) by (4.5).\displaystyle\frac{w}{c}\ (n-1)\mbox{ by }(\ref{fsum}).

and we have proved

Proposition 4.2

For random walk on an nn-vertex weighted graph,

τ*w(n-1)c\tau^{*}\leq\frac{w(n-1)}{c}

for cc defined at (4.4).

Lemma 4.1 and the Monotonicity Law also make clear a one-sided bound on the effect of changing edge-weights monotonically.

Corollary 4.3

Let w~ewe\tilde{w}_{e}\geq w_{e} be edge-weights and let τ~*\tilde{\tau}^{*} and τ*\tau^{*} be the corresponding parameters for the random walks. Then

EiT~j+EjT~iEiTj+EjTiw~w for all i,j\frac{E_{i}\tilde{T}_{j}+E_{j}\tilde{T}_{i}}{E_{i}T_{j}+E_{j}T_{i}}\leq\frac{% \tilde{w}}{w}\mbox{ for all }i,j

and so

τ~*/τ*w~/w.\tilde{\tau}^{*}/\tau^{*}\leq\tilde{w}/w.

In the case of unweighted graphs the bound in Corollary 4.3 is |~|/|||\tilde{\mbox{${\cal E}$}}|/|\mbox{${\cal E}$}|. Example yyy of Chapter 3 shows there can be no lower bound of this type, since in that example w~/w=1+O(1/n)\tilde{w}/w=1+O(1/n) but (by straightforward calculations) τ~*/τ*=O(1/n)\tilde{\tau}^{*}/\tau^{*}=O(1/n).