2 General Markov Chains (September 10, 1999)

2.6 Matthews’ method for cover times

Theorem 2.26 below is the only non-classical result in this Chapter. We make extensive use of this Matthews’ method in Chapter 6 to analyze cover times for random walks on graphs.

Consider the cover time C:=maxjTjC:=\max_{j}T_{j} of the chain, i.e. the time required to visit every state. How can we bound EiCE_{i}C in terms of the mean hitting times EiTjE_{i}T_{j}? To appreciate the cleverness of Theorem 2.26 let us first consider a more routine argument. Write t*:=maxi.jEiTjt^{*}:=\max_{i.j}E_{i}T_{j}. Since EiCE_{i}C is unaffected by continuization, we may work in continuous time. By (2.20)

Pi(Tj>ket*)e-k,k=1,2,3,.P_{i}(T_{j}>ket^{*})\leq e^{-k},\ k=1,2,3,\ldots.

By Boole’s inequality, for an nn-state chain

Pi(C>ket*)ne-k,k=1,2,3,.P_{i}(C>ket^{*})\leq ne^{-k},\ k=1,2,3,\ldots.

One can rewrite this successively as

Pi(Cet*>x)\displaystyle P_{i}\left(\frac{C}{et^{*}}>x\right) \displaystyle\leq nee-x, 0x<\displaystyle ne\cdot e^{-x},\quad 0\leq x<\infty
Pi(Cet*-log(en)>x)\displaystyle P_{i}\left(\frac{C}{et^{*}}-\log(en)>x\right) \displaystyle\leq e-x, 0x<.\displaystyle e^{-x},\quad 0\leq x<\infty.

In words, this says that the distribution of Cet*-log(en)\frac{C}{et^{*}}-\log(en) is stochastically smaller that the exponential(1)(1) distribution, implying Ei(Cet*-log(en))1E_{i}\left(\frac{C}{et^{*}}-\log(en)\right)\leq 1 and hence

maxiEiC(2+logn)et*.\max_{i}E_{i}C\leq(2+\log n)et^{*}.

This argument does lead to a bound, but one suspects the factors 22 and ee are artifacts of the proof; also, it seems hard to obtain a lower bound this way. The following result both “cleans up” the upper bound and gives a lower bound.

Theorem 2.26 (Matthews [257])

For any nn-state Markov chain,

maxvEvChn-1maxi,jEiTj\max_{v}E_{v}C\leq h_{n-1}\max_{i,j}E_{i}T_{j}
minvEvChn-1minijEiTj\min_{v}E_{v}C\geq h_{n-1}\min_{i\neq j}E_{i}T_{j}

where hn-1:=m=1n-11mh_{n-1}:=\sum_{m=1}^{n-1}\frac{1}{m}.

Proof. We’ll prove the lower bound — the upper bound proof is identical. Let J1,J2,,JnJ_{1},J_{2},\ldots,J_{n} be a uniform random ordering of the states, independent of the chain. Define Cm:=maximTJiC_{m}:=\max_{i\leq m}T_{J_{i}} to be the time until all of {J1,J2,,Jm}\{J_{1},J_{2},\ldots,J_{m}\} have been visited, in some order. The key identity is

E(Cm-Cm-1|J1,,Jm;Xt,tCm-1)=t(Lm-1,Jm)1(Lm=Jm)E(C_{m}-C_{m-1}|J_{1},\ldots,J_{m};X_{t},t\leq C_{m-1})=t(L_{m-1},J_{m})1_{(L_% {m}=J_{m})} (2.26)

where t(i,j):=EiTjt(i,j):=E_{i}T_{j} and

Lm is the state amongst {J1,J2,,Jm}\{J_{1},J_{2},\ldots,J_{m}\} hit last. L_{m}\mbox{ is the state amongst $\{J_{1},J_{2},\ldots,J_{m}\}$ hit last. }

To understand what this says, suppose we are told which are the states {J1,J2,,Jm}\{J_{1},J_{2},\ldots,J_{m}\} and told the path of the chain up through time Cm-1C_{m-1}. Then we know whether or not Lm=JmL_{m}=J_{m}: if not, then Cm=Cm-1C_{m}=C_{m-1}, and if so, then the conditional distribution of Cm-Cm-1C_{m}-C_{m-1} is the distribution of the time to hit JmJ_{m} from the state at time Cm-1C_{m-1}, which we are told is state Lm-1L_{m-1}.

Writing t*:=minijt(i,j)t_{*}:=\min_{i\neq j}t(i,j), the right side of (2.26) is t*1(Lm=Jm)\geq t_{*}1_{(L_{m}=J_{m})}, and so taking expectations

E(Cm-Cm-1)t*P(Lm=Jm).E(C_{m}-C_{m-1})\geq t_{*}P(L_{m}=J_{m}).

But obviously P(Lm=Jm)=1/mP(L_{m}=J_{m})=1/m by symmetry. So

EvC=EvC1+m=2nEv(Cm-Cm-1)EvC1+t*m=2n1m.E_{v}C=E_{v}C_{1}+\sum_{m=2}^{n}E_{v}(C_{m}-C_{m-1})\geq E_{v}C_{1}+t_{*}\sum_% {m=2}^{n}\frac{1}{m}.

Allowing for the possibility J1=vJ_{1}=v we see EvC1(1-1n)t*E_{v}C_{1}\geq(1-\frac{1}{n})t_{*}, and the lower bound follows.