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.

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

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.

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.

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

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML