6.6 Lower bounds‣ Chapter 6 Cover Times (October 31, 1994) ‣ Reversible Markov Chains and Random Walks on Graphs

6.6.1 Matthews’ method

We restate Matthews’ method (Chapter 2 yyy) as follows. The upper bound is widely useful: we have already used it several times in this chapter, and will use it several more times in the sequel.

Theorem 6.26

For a general Markov chain,

\max_{v}E_{v}C\leq h_{n-1}\max_{i,j}E_{i}T_{j}.

And for any subset $A$ of states,

\min_{v}E_{v}C\geq h_{|A|-1}\min_{i\neq j:\ i,j\in A}E_{i}T_{j}.

In Chapter 2 we proved the lower bound in the case where $A$ was the entire state space, but the result for general $A$ follows by the same proof, taking the $J$ ’s to be a uniform random ordering of the states in $A$ . One obvious motivation for the more general formulation comes from the case of trees, where for a leaf $l$ we have $\min_{j}E_{l}T_{j}=1$ , so the lower bound with $A$ being the entire state space would be just $h_{n-1}$ . We now illustrate use of the more general formulation.

6.6.2 Balanced trees

We are accustomed to finding that problems on trees are simpler than problems on general graphs, so it is a little surprising to discover that one of the graphs where studying the mean cover time is difficult is the balanced $r$ -tree of height $H$ (Chapter 5 Example yyy). Recall this tree has $n=(r^{H+1}-1)/(r-1)$ vertices, and that (by the commute interpretation of resistance)

(i,j)

Now clearly $E_{i}T_{j}$ is maximized by some pair of leaves, so $\max_{i,j}E_{i}T_{j}=2H(n-1)$ . Theorem 6.26 gives

\max_{v}E_{v}C\leq 2H(n-1)h_{n-1}\sim 2Hn\log n.

To get a lower bound, consider the set $S_{m}$ of $r^{H+1-m}$ vertices at depth $H+1-m$ , and let $A_{m}$ be a set of leaves consisting of one descendant of each element of $S_{m}$ . The elements of $A_{m}$ are at least $2m$ apart, so applying the lower bound in Theorem 6.26

$\displaystyle\min_{v}E_{v}C$	$\displaystyle\geq$	$\displaystyle\max_{m}2m(n-1)\ h_{r^{H+1-m}}$
	$\displaystyle\sim$	$\displaystyle 2n\log r\ \max_{m}m(H-m)$
	$\displaystyle\sim$	$\displaystyle\frac{1}{2}H^{2}n\log r.$

It turns out that this lower bound is asymptotically off by a factor of $4$ , while the upper bound is asymptotically correct.

Theorem 6.27 ([21])

On the balanced $r$ -tree, as $H\rightarrow\infty$ for arbitrary starting vertex,

EC\sim 2Hn\log n\sim\frac{2H^{2}r^{H+1}\log r}{r-1}

Improving the lower bound to obtain this result is not easy. The natural approach (used in [21]) is to seek a recursion for the cover time distribution $C^{(H+1)}$ in terms of $C^{(H)}$ . But the appropriate recursion is rather subtle (we invite the reader to try to find it!) so we won’t give the statement or analysis of the recursion here.

6.6.3 A resistance lower bound

Our use of the commute interpretation of resistance has so far been only to obtain upper bounds on commute times. One can also use “shorting” ideas to obtain lower bounds, and here is a very simple implementation of that idea.

Lemma 6.28

The effective resistance between $r(v,x)$ between vertices $v$ and $x$ in a weighted graph satisfies

\frac{1}{r(v,x)}\leq w_{v,x}+\frac{1}{\frac{1}{w_{v}-w_{v,x}}+\frac{1}{w_{x}-w% _{v,x}}}.

In particular, on an unweighted graph

	$\displaystyle r(v,x)$	$\displaystyle\geq$	$(v,x)$
		$\displaystyle\geq$	$\displaystyle\frac{1}{d_{v}}+\frac{1}{d_{w}}\mbox{ if not }$

and on an unweighted $d$ -regular graph

	$\displaystyle r(v,x)$	$\displaystyle\geq$	$(v,x)$
		$\displaystyle\geq$	$\displaystyle\frac{2}{d}\mbox{ if not }.$

So on an unweighted $d$ -regular $n$ -vertex graph,

	$\displaystyle E_{v}T_{x}+E_{x}T_{v}$	$\displaystyle\geq$	$(v,x)$
		$\displaystyle\geq$	$\displaystyle 2n\mbox{ if not }.$

Proof. We need only prove the first assertion, since the others follow by specialization and by the commute interpretation of resistance. Let $A$ be the set of vertices which are neighbors of either $v$ or $x$ , but exclude $v$ and $x$ themselves from $A$ . Short the vertices of $A$ together, to form a single vertex $a$ . In the shorted graph, the only way current can flow from $v$ to $x$ is directly $v\rightarrow x$ or indirectly as $v\rightarrow a\rightarrow x$ . So, using ${}^{\prime}$ to denote the shorted graph, the effective resistance $r^{\prime}(v,x)$ in the shorted graph satisfies

\frac{1}{r^{\prime}(v,x)}=w^{\prime}_{v,x}+\frac{1}{\frac{1}{w^{\prime}_{v,a}}% +\frac{1}{w^{\prime}_{x,a}}}.

Now $w^{\prime}_{x,v}=w_{x,v}$ , $w^{\prime}_{v,a}=w_{v}-w_{v,x}$ and $w^{\prime}_{x,a}=w_{x}-w_{v,x}$ . Since shorting decreases resistance, $r^{\prime}(v,x)\leq r(v,x)$ , establishing the first inequality.

6.6.4 General lower bounds

Chapter 3 yyy shows that, over the class of random walks on $n$ -vertex graphs or the larger class of reversible chains on $n$ states, various mean hitting time parameters are minimized on the complete graph. So it is natural to anticipate a similar result for cover time parameters. But the next example shows that some care is required in formulating conjectures.

Example 6.29

Take the complete graph on $n$ vertices, and add an edge $(v,l)$ to a new leaf $l$ .

Since random walk on the complete graph has mean cover time $(n-1)h_{n-1}$ , random walk on the enlarged graph has

E_{l}C=1+(n-1)h_{n-1}+2\mu

where $\mu$ is the mean number of returns to $l$ before covering. Now after each visit to $v$ , the walk has chance $1/n$ to visit $l$ on the next step, and so the mean number of visits to $l$ before visiting some other vertex of the complete graph equals $1/(n-1)$ . We may therefore write $\mu$ in terms of expectations for random walk on the complete graph as

$\displaystyle\mu$	$\displaystyle=$	$v$
	$\displaystyle=$	$v$
	$\displaystyle=$	$\displaystyle{1\over{n-1}}\ {1\over n}E_{v}C^{+}\mbox{ by Chapter 2 % Proposition yyy}$
	$\displaystyle=$	$\displaystyle\frac{1+h_{n-1}}{n}\mbox{ by (\ref{cgc+}).}$

This establishes an expression for $E_{l}C$ , which (after a brief calculation) can be rewritten as

E_{l}C=nh_{n}-\left(1-\frac{2}{n}\right)\left(h_{n}-\frac{1}{n}\right).

Now random walk on the complete $(n+1)$ -graph has mean cover time $nh_{n}$ , so $E_{l}C$ is smaller in our example than in the complete graph.

The example motivates the following as the natural “exact extremal conjecture”.

Open Problem 6.30

Prove that, for any reversible chain on $n$ states,

E_{\pi}C\geq(n-1)h_{n-1}

(the value for random walk on the complete graph).

The related asymptotic question was open for many years, and was finally proved by Feige [142].

Theorem 6.31

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

\min_{v}E_{v}C\geq c_{n},

where $c_{n}\sim n\log n$ as $n\rightarrow\infty$ .

The proof is an intricate mixture of many of the techniques we have already described.