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

We start by repeating the definition

 $\tau^{*}\equiv\max_{ij}(E_{i}T_{j}+E_{j}T_{i})$ (4.1)

and recalling what we already know. Obviously

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

and by Chapter 3 Lemma yyy

 $\max_{j}E_{\pi}T_{j}\leq\tau^{*}\leq 4\max_{j}E_{\pi}T_{j}.$ (4.2)

Arguably we could have used $\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,

 $\tau^{*}=w\max_{ij}r_{ij}$

where $r_{ij}$ is the effective resistance between $i$ and $j$.

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

 $\tau^{*}\geq 2(n-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=i_{0},i_{1},\ldots,i_{m}=j$, and let’s call this path $\gamma_{ij}$ (because we’ve run out of symbols whose names begin with “p”!) This path, considered in isolation, has “resistance”

 $r(\gamma_{ij})\equiv\sum_{e\in\gamma_{ij}}1/w_{e}$

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

 $\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

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

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

 $i$ (4.5)

So

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

and we have proved

###### Proposition 4.2

For random walk on an $n$-vertex weighted graph,

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

for $c$ 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 $\tilde{w}_{e}\geq w_{e}$ be edge-weights and let $\tilde{\tau}^{*}$ and $\tau^{*}$ be the corresponding parameters for the random walks. Then

 $\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

 $\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 $\tilde{w}/w=1+O(1/n)$ but (by straightforward calculations) $\tilde{\tau}^{*}/\tau^{*}=O(1/n)$.