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.

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

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.

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)$.

4 Hitting and Convergence Time, and Flow Rate, Parameters for Reversible Markov Chains (October 11, 1994)Bibliography4.2 The average hitting time $\tau_{0}$

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