6 Cover Times (October 31, 1994)

6.4 Short-time bounds

It turns out that the bound “τ*3n2\tau^{*}\leq 3n^{2} on a regular graph” given by Corollary 6.9 can be used to obtain bounds concerning the short-time behavior of random walks. Such bounds, and their applications, are the focus of this section. We haven’t attempted to optimize numerical constants (e.g. Theorem 6.15 implies that τ*13n2/6\tau^{*}\leq 13n^{2}/6 on regular graphs). More elaborate arguments (see Notes) can be used to improve constants and to deal with the irregular case, but we’ll restrict attention to the regular case for simplicity.

Write Ni(t)N_{i}(t) for the number of visits to ii before time tt, i.e. during [0,t-1][0,t-1].

Proposition 6.16

Consider random walk on an nn-vertex regular graph GG. Let AA be a proper subset of vertices and let iAi\in A.

(i) EiTAc4|A|2E_{i}T_{A^{c}}\leq 4|A|^{2}.

(ii) EiNi(TAc)5|A|E_{i}N_{i}(T_{A^{c}})\leq 5|A|.

(iii) EiNi(t)5t1/2, 0t<5n2E_{i}N_{i}(t)\leq 5t^{1/2},\ 0\leq t<5n^{2}.

(iv) Pπ(Ti<t)15nmin(t1/2,n)P_{\pi}(T_{i}<t)\geq\frac{1}{5n}\min(t^{1/2},n).

Remarks. For part (i) we give a slightly fussy argument repeating ingredients of the proof of Corollary 6.9, since these are needed for (ii). The point of (iv) is to get a bound for tEπTit\ll E_{\pi}T_{i}. On the nn-cycle, it can be shown that the probability in question really is Θ(min(t1/2/n,1))\Theta(\min(t^{1/2}/n,1)), uniformly in nn and tt.

Proof of Proposition 6.16. Choose a vertex bAcb\in A^{c} at minimum distance from ii, and let i=i0,i1,,ij,ij+1=bi=i_{0},i_{1},\ldots,i_{j},i_{j+1}=b be a minimum-length path. Let G*G^{*} be the subgraph on vertex-set AA, and let G**G^{**} be the subgraph on vertex-set AA together with all the neighbors of iji_{j}. Write superscripts *\ {}^{*} and **\ {}^{**} for the random walks on G*G^{*} and G**G^{**}. Then

EiTAcEiTAc**=EiTij*+EijTAc**E_{i}T_{A^{c}}\leq E_{i}T^{**}_{A^{c}}=E_{i}T^{*}_{i_{j}}+E_{i_{j}}T^{**}_{A^{% c}}

The inequality holds because we can specify the walk on GG in terms of the walk on G**G^{**} with possibly extra chances of jumping to AcA^{c} at each step (this is a routine stochastic comparison argument, written out as an example in Chapter 14 yyy). The equality holds because the only routes in G**G^{**} from ii to AcA^{c} are via iji_{j}, by the minimum-length assumption. Now write ,*,**\mbox{${\cal E}$},\mbox{${\cal E}$}^{*},\mbox{${\cal E}$}^{**} for the edge-sets. Using the commute interpretation of resistance,

EiTij*2|*|j.E_{i}T^{*}_{i_{j}}\leq 2|\mbox{${\cal E}$}^{*}|j. (6.20)

Writing q1q\geq 1 for the number of neighbors of iji_{j} in AcA^{c}, the effective resistance in G**G^{**} between iji_{j} and AcA^{c} is 1/q1/q, so the commute interpretation of resistance give the first equality in

EijTAc**=2|**|1q-1=2|*|q+12|*|+1|A|2.E_{i_{j}}T^{**}_{A^{c}}=2|\mbox{${\cal E}$}^{**}|\frac{1}{q}\ -1=2\frac{|\mbox% {${\cal E}$}^{*}|}{q}\ +1\leq 2|\mbox{${\cal E}$}^{*}|+1\leq|A|^{2}.

The neighbors of i0,i1,,ij-1i_{0},i_{1},\ldots,i_{j-1} are all in AA, so the proof of Lemma 6.10 implies

j3|A|/dj\leq 3|A|/d (6.21)

where dd is the degree of GG. Since 2|*|d|A|2|\mbox{${\cal E}$}^{*}|\leq d|A|, the bound in (6.20) is at most 3|A|23|A|^{2}, and part (i) follows.

For part (ii), by the electrical network analogy (Chapter 3 yyy) the quantity in question equals

1Pi(TAc<Ti+)=wir(i,Ac)=dr(i,Ac)\frac{1}{P_{i}(T_{A^{c}}<T^{+}_{i})}=w_{i}r(i,A^{c})=dr(i,A^{c}) (6.22)

where r(i,Ac)r(i,A^{c}) is the effective resistance in GG between ii and AcA^{c}. Clearly this effective resistance is at most the distance (j+1j+1, in the argument above) from ii to AcA^{c}, which by (6.21) is at most 3|A|/d+13|A|/d\ +1. Thus the quantity (6.22) is at most 3|A|+d3|A|+d, establishing the desired result in the case d2|A|d\leq 2|A|. If d>2|A|d>2|A| then there are at least d-|A|d-|A| edges from ii to AcA^{c}, so r(i,Ac)1d-|A|r(i,A^{c})\leq\frac{1}{d-|A|} and the quantity (6.22) is at most dd-|A|25|A|\frac{d}{d-|A|}\leq 2\leq 5|A|.

For part (iii), fix a state ii and an integer time tt. Write Ni(t)N_{i}(t) for the number of visits to ii before time tt, i.e. during times {0,1,,t-1}\{0,1,\ldots,t-1\}. Then

tn=EπNi(t)Pπ(Ti<t)EiNi(t)\frac{t}{n}=E_{\pi}N_{i}(t)\leq P_{\pi}(T_{i}<t)E_{i}N_{i}(t) (6.23)

the inequality by conditioning on TiT_{i}. Now choose real ss such that nstns\geq t. Since jEiNj(t)=t\sum_{j}E_{i}N_{j}(t)=t, the set


has |A|<t/sn|A|<t/s\leq n, so part (ii) implies

EiNi(TAc)5t/s.E_{i}N_{i}(T_{A^{c}})\leq 5t/s. (6.24)

Now by regularity we can rewrite AA as {j:EjNi(t)>s}\{j:E_{j}N_{i}(t)>s\}, and so by conditioning on TAcT_{A^{c}}

EiNi(t)EiNi(TAc)+s.E_{i}N_{i}(t)\leq E_{i}N_{i}(T_{A^{c}})+s.

Setting s=5ts=\sqrt{5t} and combining with (6.24) gives (iii). The bound in (iv) now follows from (iii) and (6.23).

6.4.1 Covering by multiple walks

The first application is a variant of work of Broder et al [64] discussed further in section 6.8.2.

Proposition 6.17

On a regular nn-vertex graph, consider KK independent random walks, each started at a uniform random vertex. Let C[K]C^{[K]} be the time until every vertex has been hit by some walk. Then

EC[K](25+o(1))n2log2nK2 as n with K6logn.EC^{[K]}\leq\frac{(25+o(1))n^{2}\log^{2}n}{K^{2}}\mbox{ as }n\rightarrow\infty% \mbox{ with }K\geq 6\log n.

Remarks. The point is the 1K2\frac{1}{K^{2}} dependence on KK. On the nn-cycle, for KεnK\sim\varepsilon n it can be shown that initially the largest gap between adjacent walkers is Θ(logn)\Theta(\log n) and that EC[K]=Θ(log2n)EC^{[K]}=\Theta(\log^{2}n), so in this respect the bound is sharp. Of course, for KlognK\leq\log n the bound would be no improvement over Theorem 6.4.

Proof. As usual write TiT_{i} for the hitting time on ii for a single walk, and write Ti[K]T^{[K]}_{i} for the first time ii is visited by some walk. Then

Pπ(Ti[K]t)\displaystyle P_{\pi}(T^{[K]}_{i}\geq t) =\displaystyle= (Pπ(Tit))K\displaystyle(P_{\pi}(T_{i}\geq t))^{K}
=\displaystyle= (1-Pπ(Ti<t))K\displaystyle(1-P_{\pi}(T_{i}<t))^{K}
\displaystyle\leq exp(-KPπ(Ti<t))\displaystyle\exp(-KP_{\pi}(T_{i}<t))
\displaystyle\leq exp(-Kt1/25n)\displaystyle\exp\left(-\frac{Kt^{1/2}}{5n}\right)

by Proposition 6.16 (iii), provided tn2t\leq n^{2}. So

P(C[K]t)iP(Ti[K]t)nexp(-Kt1/25n),tn2.P(C^{[K]}\geq t)\leq\sum_{i}P(T^{[K]}_{i}\geq t)\leq n\exp\left(-\frac{Kt^{1/2% }}{5n}\right),\ t\leq n^{2}. (6.25)

The bound becomes 11 for t0=25n2K2log2nt_{0}=\frac{25n^{2}}{K^{2}}\log^{2}n. So

EC[K]\displaystyle EC^{[K]} =\displaystyle= t=1P(C[K]t)\displaystyle\sum_{t=1}^{\infty}P(C^{[K]}\geq t)
\displaystyle\leq t0+t=t0+1n2-1nexp(-Kt1/25n)+t=n2P(C[K]t)\displaystyle\lceil t_{0}\rceil+\sum_{t=\lceil t_{0}\rceil+1}^{n^{2}-1}n\exp% \left(-\frac{Kt^{1/2}}{5n}\right)+\sum_{t=n^{2}}^{\infty}P(C^{[K]}\geq t)
=\displaystyle= t0+S1+S2, say,\displaystyle\lceil t_{0}\rceil+S_{1}+S_{2},\mbox{ say,}

and the issue is to show that S1S_{1} and S2S_{2} are o(t0)o(t_{0}). To handle S2S_{2}, split the set of KK walks into subsets of sizes K-1K-1 and 11. By independence, for tn2t\geq n^{2} we have P(C[K]t)P(C[K-1]n2)P(C[1]t)P(C^{[K]}\geq t)\leq P(C^{[K-1]}\geq n^{2})P(C^{[1]}\geq t). Then

S2\displaystyle S_{2} \displaystyle\leq P(C[K-1]n2)EC[1] by summing over t\displaystyle P(C^{[K-1]}\geq n^{2})EC^{[1]}\mbox{ by summing over }t
\displaystyle\leq nexp(-(K-1)/5)6n2 by (6.25) and Theorem 6.4\displaystyle n\exp(-(K-1)/5)\cdot 6n^{2}\mbox{ by (\ref{CKn}) and Theorem % \ref{K0}}
=\displaystyle= o(t0) using the hypothesis K6logn.\displaystyle o(t_{0})\mbox{ using the hypothesis }K\geq 6\log n.

To bound S1S_{1} we start with a calculus exercise: for u>1u>1

u2exp(-x1/2)dx\displaystyle\int_{u^{2}}^{\infty}\exp(-x^{1/2})\ dx =\displaystyle= u2yexp(-y)dy by putting x=y2\displaystyle\int_{u}^{\infty}2y\ \exp(-y)\ dy\mbox{ by putting }x=y^{2}
\displaystyle\leq 2e-1uuexp(-(u-1u)y)dy , using yuexp(yu-1)\displaystyle 2e^{-1}u\int_{u}^{\infty}\exp(-\left(\frac{u-1}{u}\right)y)\ dy% \mbox{ , using }\frac{y}{u}\leq\exp(\frac{y}{u}-1)
=\displaystyle= 2u2exp(-u)u-1.\displaystyle\frac{2u^{2}\exp(-u)}{u-1}.

The sum S1S_{1} is bounded by the corresponding integral over [t0,)[t_{0},\infty) and the obvious calculation, whose details we omit, bounds this integral by 2t0/(logn-1)2t_{0}/(\log n-1).

6.4.2 Bounding point probabilities

Our second application is to universal bounds on point probabilities. A quite different universal bound will be given in Chapter yyy.

Proposition 6.18

For continuous-time random walk on a regular nn-vertex graph,

Pi(Xt=j)\displaystyle P_{i}(X_{t}=j) \displaystyle\leq 5t-1/2,  tn2\displaystyle 5t^{-1/2},\ t\leq n^{2}
\displaystyle\leq 1n+K1nexp(-tK2n2),  tn2\displaystyle\frac{1}{n}+\frac{K_{1}}{n}\exp\left(\frac{-t}{K_{2}n^{2}}\right)% ,\ t\geq n^{2}

where K1K_{1} and K2K_{2} are absolute constants.

In discrete time one can get essentially the same result, but with the bounds multiplied by 22, though we shall not give details (see Notes).

Proof. Pi(Xt=i)P_{i}(X_{t}=i) is decreasing in tt, so

Pi(Xt=i)t-10tPi(Xs=i)ds=t-1EiNi(t)5t-1/2P_{i}(X_{t}=i)\leq t^{-1}\int_{0}^{t}P_{i}(X_{s}=i)ds=t^{-1}E_{i}N_{i}(t)\leq 5% t^{-1/2}

where the last inequality is Proposition 6.16 (iii), whose proof is unchanged in continuous time, and which holds for tn2t\leq n^{2}. This gives the first inequality when i=ji=j, and the general case follows from Chapter 3 yyy.

For the second inequality, recall the definition of separation s(t)s(t) from Chapter 4 yyy. Given a vertex ii and a time tt, there exists a probability distribution θ\theta such that


Then for u0u\geq 0,


Thus, defining q(t)=maxi,j(Pi(Xt=j)-1n)q(t)=\max_{i,j}\left(P_{i}(X_{t}=j)-\frac{1}{n}\right), we have proved

q(t+u)s(t)q(u);  t,u0.q(t+u)\leq s(t)q(u);\ t,u\geq 0. (6.26)

Now q(n2)4/nq(n^{2})\leq 4/n by the first inequality of the Proposition, and s(τ1(1))=e-1s(\tau_{1}^{(1)})=e^{-1} by definition of τ1(1)\tau_{1}^{(1)} in Chapter 4 yyy, so by iterating (6.26) we have

q(n2+mτ1(1))4ne-m,  m1.q(n^{2}+m\tau_{1}^{(1)})\leq\frac{4}{n}\ e^{-m},\ m\geq 1. (6.27)

But by Chapter 4 yyy we have τ1(1)Kτ*\tau_{1}^{(1)}\leq K\tau^{*} for an absolute constant KK, and then by Corollary 6.9 we have τ1(1)3Kn2\tau_{1}^{(1)}\leq 3Kn^{2}. The desired inequality now follows from (6.27).

6.4.3 A cat and mouse game

Here we reconsider the cat and mouse game discussed in Chapter 4 section yyy. Recall that the cat performs continuous-time random walk on a nn-vertex graph, and the mouse moves according to some arbitrary deterministic strategy. Let MM be the first meeting time, and let m*m^{*} be the maximum of EMEM over all pairs of initial vertices and all strategies for the mouse.

Proposition 6.19

On a regular graph, m*KN2m^{*}\leq KN^{2} for some absolute constant KK.

Proof. The proof relies on Proposition 6.18, whose conclusion implies there exists a constant KK such that

p*(t)maxx,vpvx(t)1n+Kt-1/2; 0t<.p^{*}(t)\equiv\max_{x,v}p_{vx}(t)\leq\frac{1}{n}+Kt^{-1/2};\ 0\leq t<\infty.

Consider running the process forever. The point is that, regardless of the initial positions, the chance that the cat and mouse are “together” (i.e. at the same vertex) at time uu is at most p*(u)p^{*}(u). So in the case where the cat starts with the (uniform) stationary distribution,

P( together at time ss )\displaystyle P(\mbox{ together at time $s$ }) =\displaystyle= 0sf(u)P( together at time ss|M=u)du\displaystyle\int_{0}^{s}f(u)P(\mbox{ together at time $s$}|M=u)\ du
where ff is the density function of MM
\displaystyle\leq 0sf(u)p*(s-u)du\displaystyle\int_{0}^{s}f(u)p^{*}(s-u)du
\displaystyle\leq 1nP(Ms)+K0sf(u)(s-u)-1/2du.\displaystyle\frac{1}{n}P(M\leq s)\ +K\int_{0}^{s}f(u)(s-u)^{-1/2}du.


tn\displaystyle\frac{t}{n} =\displaystyle= 0tP( together at time ss )ds by stationarity\displaystyle\int_{0}^{t}P(\mbox{ together at time $s$ })\ ds\mbox{ by stationarity}
\displaystyle\leq 1n0tP(Ms)ds+K0tf(u)duut(s-u)-1/2ds\displaystyle\frac{1}{n}\int_{0}^{t}P(M\leq s)ds\ +K\int_{0}^{t}f(u)du\int_{u}% ^{t}(s-u)^{-1/2}ds
=\displaystyle= tn-1n0tP(M>s)ds+2K0tf(u)(t-u)1/2du\displaystyle\frac{t}{n}-\frac{1}{n}\int_{0}^{t}P(M>s)ds+2K\int_{0}^{t}f(u)(t-% u)^{1/2}du
\displaystyle\leq tn-1nEmin(M,t)+2Kt1/2.\displaystyle\frac{t}{n}-\frac{1}{n}E\min(M,t)+2Kt^{1/2}.

Rearranging, Emin(M,t)2Knt1/2E\min(M,t)\leq 2Knt^{1/2}. Writing t0=(4Kn)2t_{0}=(4Kn)^{2}, Markov’s inequality gives P(Mt0)1/2P(M\leq t_{0})\geq 1/2. This inequality assumes the cat starts with the stationary distribution. When it starts at some arbitrary vertex, we may use the definition of separation s(u)s(u) (recall Chapter 4 yyy) to see P(Mu+t0)(1-s(u))/2P(M\leq u+t_{0})\geq(1-s(u))/2. Then by iteration, EM2(u+t0)1-s(u)EM\leq\frac{2(u+t_{0})}{1-s(u)}. So appealing to the definition of τ1(1)\tau_{1}^{(1)},


But results from Chapter 4 and this chapter show τ1(1)=O(τ*)=O(n2)\tau_{1}^{(1)}=O(\tau^{*})=O(n^{2}), establishing the Proposition.