14 Interacting Particles on Finite Graphs (March 10, 1994)

14.2 Meeting times

Given a Markov chain, the meeting time Mi,jM_{i,j} is the time at which independent copies of the chain started at ii and at jj first meet. Meeting times arose in the Doeblin coupling and arise in several other contexts later, so deserve a little study. It is natural to try to relate meeting times to properties such as hitting times for a single copy of the chain. One case is rather simple. Consider a distribution dist(ξ)(\xi) on a group GG such that

ξ=dξ-1;    gξ=dξg for all gG.\xi\ \stackrel{d}{=}\ \xi^{-1};\ \ \ \ \ g\xi\ \stackrel{d}{=}\ \xi g\mbox{ % for all }g\in G.

Now let XtX_{t} and YtY_{t} be independent copies of the continuization of random flight on GG with step-distribution ξ\xi. Then if we define Zt=Xt-1YtZ_{t}=X^{-1}_{t}Y_{t}, it is easy to check that ZZ is itself the continuization of the random flight, but run at twice the speed, i.e. with transition rates


It follows that EMi,j=12EiTjEM_{i,j}=\frac{1}{2}E_{i}T_{j}. The next result shows this equality holds under less symmetry, and (more importantly) that an inequality holds without any symmetry.

Proposition 14.5

For a continuous-time reversible Markov chain, let TjT_{j} be the usual first hitting time and let Mi,jM_{i,j} be the meeting time of independent copies of the chain started at ii and jj. Then maxi,jEMi,jmaxi,jEiTj\max_{i,j}EM_{i,j}\leq\max_{i,j}E_{i}T_{j}. If moreover the chain is symmetric (recall the definition from Chapter 7 yyy) then EMi,j=12EiTjEM_{i,j}=\frac{1}{2}E_{i}T_{j}.

Proof. This is really just a special case of the cat and mouse game of Chapter 3 section yyy, where the player is using a random strategy to decide which animal to move. Write XtX_{t} and YtY_{t} for the chains started at ii and jj. Write f(x,y)=ExTy-EπTyf(x,y)=E_{x}T_{y}-E_{\pi}T_{y}. Follow the argument in Chapter 3 yyy to verify

St(2t+f(Xt,Yt);0tMij) is a martingale. S_{t}\equiv(2t+f(X_{t},Y_{t});0\leq t\leq M_{ij})\mbox{ is a martingale. }


EiTj-EπTj\displaystyle E_{i}T_{j}-E_{\pi}T_{j} =\displaystyle= ES0\displaystyle ES_{0}
=\displaystyle= ESMi,j by the optional sampling theorem\displaystyle ES_{M_{i,j}}\mbox{ by the optional sampling theorem}
=\displaystyle= 2EMij+Ef(XMij,YMij)\displaystyle 2EM_{ij}+Ef(X_{M_{ij}},Y_{M_{ij}})
=\displaystyle= 2EMi,j-Et¯(XMi,j), where t¯(k)=EπTj.\displaystyle 2EM_{i,j}-E\bar{t}(X_{M_{i,j}})\mbox{, where }\bar{t}(k)=E_{\pi}% T_{j}.

In the symmetric case we have t¯(k)=τ0\bar{t}(k)=\tau_{0} for all kk, establishing the desired equality. In general we have t¯(k)maxi,jEiTj\bar{t}(k)\leq\max_{i,j}E_{i}T_{j} and the stated inequality follows.

Remarks. Intuitively the bound in Proposition 14.5 should be reasonable for “not too asymmetric” graphs. But on the nn-star (Chapter 5 yyy), for example, we have maxi,jEMi,j=Θ(1)\max_{i,j}EM_{i,j}=\Theta(1) while maxi,jEiTj=Θ(n)\max_{i,j}E_{i}T_{j}=\Theta(n). The “Θ(1)\Theta(1)” in that example comes from concentration of the stationary distribution, and on a regular graph we can use Chapter 3 yyy to obtain


But we can construct regular graphs which mimic the nn-star in the sense that maxi,jEMi,j=o(τ0)\max_{i,j}EM_{i,j}=o(\tau_{0}). A more elaborate result, which gives the correct order of magnitude on the nn-star, was given in Aldous [20].

Proposition 14.6

For a continuous-time reversible chain,

maxi,jEMi,jK(iπimax(EπTi,τ1))-1\max_{i,j}EM_{i,j}\leq K\left(\sum_{i}\frac{\pi_{i}}{\max(E_{\pi}T_{i},\tau_{1% })}\right)^{-1}

for an absolute constant KK.

The proof is too lengthy to reproduce, but let us observe as a corollary that we can replace the maxi,jEiTj\max_{i,j}E_{i}T_{j} bound in Proposition 14.5 by the a priori smaller quantity τ0\tau_{0}, at the expense of some multiplicative constant.

Corollary 14.7

For a continuous-time reversible chain,

maxi,jEMi,jKτ0\max_{i,j}EM_{i,j}\leq K\tau_{0}

for an absolute constant KK.

Proof of Corollary 14.7. First recall from Chapter 4 yyy the inequality

τ166τ0.\tau_{1}\leq 66\tau_{0}. (14.10)

“Harmonic mean \leq arithmetic mean” gives the first inequality in

(iπimax(EπTi,τ1))-1\displaystyle\left(\sum_{i}\frac{\pi_{i}}{\max(E_{\pi}T_{i},\tau_{1})}\right)^% {-1} \displaystyle\leq iπimax(EπTi,τ1)\displaystyle\sum_{i}\pi_{i}\max(E_{\pi}T_{i},\tau_{1})
\displaystyle\leq iπi(EπTi+τ1)\displaystyle\sum_{i}\pi_{i}(E_{\pi}T_{i}+\tau_{1})
\displaystyle\leq τ0+τ1\displaystyle\tau_{0}+\tau_{1}
\displaystyle\leq 67τ0 by (14.10)\displaystyle 67\tau_{0}\mbox{ by }(\ref{10-1})

and so the result is indeed a corollary of Proposition 14.6.

Two interesting open problems remain. First, does Proposition 14.6 always give the right order of magnitude, i.e.

Open Problem 14.8

In the setting of Proposition 14.6, does there exist an absolute constant KK such that

Kmaxi,jEMi,j(iπimax(EπTi,τ1))-1K\max_{i,j}EM_{i,j}\geq\left(\sum_{i}\frac{\pi_{i}}{\max(E_{\pi}T_{i},\tau_{1}% )}\right)^{-1}

The other open problem is whether some modification of the proof of Proposition 14.5 would give a small constant KK in Corollary 14.7. To motivate this question, note that the coupling inequality applied to the Doeblin coupling shows that for any chain d¯(t)maxi,jP(Mi,j>t).\bar{d}(t)\leq\max_{i,j}P(M_{i,j}>t). Then Markov’s inequality shows that the variation threshold satisfies τ1emaxi,jEMi,j.\tau_{1}\leq e\max_{i,j}EM_{i,j}. In the reversible setting, Proposition 14.5 now implies τ1eKτ0\tau_{1}\leq eK\tau_{0} where KK is the constant in Corollary 14.7. So a direct proof of Corollary 14.7 with small KK would improve the numerical constant in inequality (14.10).