6 Cover Times (October 31, 1994)

6.6 Lower bounds

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,

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

And for any subset AA of states,

minvEvCh|A|-1minij:i,jAEiTj.\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 AA was the entire state space, but the result for general AA follows by the same proof, taking the JJ’s to be a uniform random ordering of the states in AA. One obvious motivation for the more general formulation comes from the case of trees, where for a leaf ll we have minjElTj=1\min_{j}E_{l}T_{j}=1, so the lower bound with AA being the entire state space would be just hn-1h_{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 rr-tree of height HH (Chapter 5 Example yyy). Recall this tree has n=(rH+1-1)/(r-1)n=(r^{H+1}-1)/(r-1) vertices, and that (by the commute interpretation of resistance)

EiTj=2m(n-1) for leaves (i,j)(i,j) distance 2m2m apart.E_{i}T_{j}=2m(n-1)\mbox{ for leaves $(i,j)$ distance $2m$ apart}.

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

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

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

minvEvC\displaystyle\min_{v}E_{v}C \displaystyle\geq maxm2m(n-1)hrH+1-m\displaystyle\max_{m}2m(n-1)\ h_{r^{H+1-m}}
\displaystyle\sim 2nlogrmaxmm(H-m)\displaystyle 2n\log r\ \max_{m}m(H-m)
\displaystyle\sim 12H2nlogr.\displaystyle\frac{1}{2}H^{2}n\log r.

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

Theorem 6.27 ([21])

On the balanced rr-tree, as HH\rightarrow\infty for arbitrary starting vertex,

EC2Hnlogn2H2rH+1logrr-1EC\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)C^{(H+1)} in terms of C(H)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)r(v,x) between vertices vv and xx in a weighted graph satisfies

1r(v,x)wv,x+11wv-wv,x+1wx-wv,x.\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

r(v,x)\displaystyle r(v,x) \displaystyle\geq dv+dx-2dvdx-1 if (v,x)(v,x) is an edge\displaystyle\frac{d_{v}+d_{x}-2}{d_{v}d_{x}\ -1}\mbox{ if $(v,x)$ is an edge}
\displaystyle\geq 1dv+1dw if not\displaystyle\frac{1}{d_{v}}+\frac{1}{d_{w}}\mbox{ if not }

and on an unweighted dd-regular graph

r(v,x)\displaystyle r(v,x) \displaystyle\geq 2d+1 if (v,x)(v,x) is an edge\displaystyle\frac{2}{d+1}\mbox{ if $(v,x)$ is an edge}
\displaystyle\geq 2d if not .\displaystyle\frac{2}{d}\mbox{ if not }.

So on an unweighted dd-regular nn-vertex graph,

EvTx+ExTv\displaystyle E_{v}T_{x}+E_{x}T_{v} \displaystyle\geq 2dnd+1 if (v,x)(v,x) is an edge\displaystyle\frac{2dn}{d+1}\mbox{ if $(v,x)$ is an edge}
\displaystyle\geq 2n if not .\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 AA be the set of vertices which are neighbors of either vv or xx, but exclude vv and xx themselves from AA. Short the vertices of AA together, to form a single vertex aa. In the shorted graph, the only way current can flow from vv to xx is directly vxv\rightarrow x or indirectly as vaxv\rightarrow a\rightarrow x. So, using {}^{\prime} to denote the shorted graph, the effective resistance r(v,x)r^{\prime}(v,x) in the shorted graph satisfies

1r(v,x)=wv,x+11wv,a+1wx,a.\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 wx,v=wx,vw^{\prime}_{x,v}=w_{x,v}, wv,a=wv-wv,xw^{\prime}_{v,a}=w_{v}-w_{v,x} and wx,a=wx-wv,xw^{\prime}_{x,a}=w_{x}-w_{v,x}. Since shorting decreases resistance, r(v,x)r(v,x)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 nn-vertex graphs or the larger class of reversible chains on nn 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 nn vertices, and add an edge (v,l)(v,l) to a new leaf ll.

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


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

μ\displaystyle\mu =\displaystyle= 1n-1Ev( number of visits to vv before CC)\displaystyle{1\over{n-1}}E_{v}(\mbox{ number of visits to $v$ before $C$})
=\displaystyle= 1n-1Ev( number of visits to vv before C+C^{+})\displaystyle{1\over{n-1}}E_{v}(\mbox{ number of visits to $v$ before $C^{+}$})
=\displaystyle= 1n-11nEvC+ by Chapter 2 Proposition yyy\displaystyle{1\over{n-1}}\ {1\over n}E_{v}C^{+}\mbox{ by Chapter 2 % Proposition yyy}
=\displaystyle= 1+hn-1n by (6.12).\displaystyle\frac{1+h_{n-1}}{n}\mbox{ by (\ref{cgc+}).}

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


Now random walk on the complete (n+1)(n+1)-graph has mean cover time nhnnh_{n}, so ElCE_{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 nn states,


(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 nn-vertex graph,

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

where cnnlognc_{n}\sim n\log n as nn\rightarrow\infty.

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