Meeting times for independent Markov chains (Q1177207): Difference between revisions

Consider a time reversible continuous time Markov chain \((X_ t)\) on a finite state space. Let \((Y_ t)\) be an independent copy of the chain and let \(T_ M\) be the meeting time of the two chains. The paper studies the worst-case mean meeting time \[ \tau_ M\equiv\max_{i,j}E(T_ M\mid X_ 0=i, Y_ 0=j). \] Let \(H_ j\) be the first hitting time of state \(j\). The main results are the inequality \[ \tau_ M\leq K\max_{i,j}E(H_ j\mid X_ 0=i) \] together with a further sharpening involving specific averages of the \(E(H_ j\mid X_ 0=i)\) rather than a maximum. Here \(K\) is a universal constant independent of \(N\). The proof, which utilizes the harmonic mean formula, is of significant interest in itself.