# 14.2 Meeting times

Given a Markov chain, the meeting time $M_{i,j}$ is the time at which independent copies of the chain started at $i$ and at $j$ 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 $G$ such that

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

Now let $X_{t}$ and $Y_{t}$ be independent copies of the continuization of random flight on $G$ with step-distribution $\xi$. Then if we define $Z_{t}=X^{-1}_{t}Y_{t}$, it is easy to check that $Z$ is itself the continuization of the random flight, but run at twice the speed, i.e. with transition rates

 $q_{Z}(g,h)=2P(g\xi=h).$

It follows that $EM_{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 $T_{j}$ be the usual first hitting time and let $M_{i,j}$ be the meeting time of independent copies of the chain started at $i$ and $j$. Then $\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 $EM_{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 $X_{t}$ and $Y_{t}$ for the chains started at $i$ and $j$. Write $f(x,y)=E_{x}T_{y}-E_{\pi}T_{y}$. Follow the argument in Chapter 3 yyy to verify

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

Then

 $\displaystyle E_{i}T_{j}-E_{\pi}T_{j}$ $\displaystyle=$ $\displaystyle ES_{0}$ $\displaystyle=$ $\displaystyle ES_{M_{i,j}}\mbox{ by the optional sampling theorem}$ $\displaystyle=$ $\displaystyle 2EM_{ij}+Ef(X_{M_{ij}},Y_{M_{ij}})$ $\displaystyle=$ $\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 $\bar{t}(k)=\tau_{0}$ for all $k$, establishing the desired equality. In general we have $\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 $n$-star (Chapter 5 yyy), for example, we have $\max_{i,j}EM_{i,j}=\Theta(1)$ while $\max_{i,j}E_{i}T_{j}=\Theta(n)$. The “$\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

 $\sum_{i}\sum_{j}\pi_{i}\pi_{j}EM_{i,j}\geq\frac{(n-1)^{2}}{2n}.$

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

###### Proposition 14.6

For a continuous-time reversible chain,

 $\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 $K$.

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

###### Corollary 14.7

For a continuous-time reversible chain,

 $\max_{i,j}EM_{i,j}\leq K\tau_{0}$

for an absolute constant $K$.

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

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

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

 $\displaystyle\left(\sum_{i}\frac{\pi_{i}}{\max(E_{\pi}T_{i},\tau_{1})}\right)^% {-1}$ $\displaystyle\leq$ $\displaystyle\sum_{i}\pi_{i}\max(E_{\pi}T_{i},\tau_{1})$ $\displaystyle\leq$ $\displaystyle\sum_{i}\pi_{i}(E_{\pi}T_{i}+\tau_{1})$ $\displaystyle\leq$ $\displaystyle\tau_{0}+\tau_{1}$ $\displaystyle\leq$ $\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 $K$ such that

 $K\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 $K$ in Corollary 14.7. To motivate this question, note that the coupling inequality applied to the Doeblin coupling shows that for any chain $\bar{d}(t)\leq\max_{i,j}P(M_{i,j}>t).$ Then Markov’s inequality shows that the variation threshold satisfies $\tau_{1}\leq e\max_{i,j}EM_{i,j}.$ In the reversible setting, Proposition 14.5 now implies $\tau_{1}\leq eK\tau_{0}$ where $K$ is the constant in Corollary 14.7. So a direct proof of Corollary 14.7 with small $K$ would improve the numerical constant in inequality (14.10).