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

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

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.

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

Then

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

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].

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.

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

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

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.

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).