# Meeting time lower bound for a random walks on a large finite graph of bounded degree

Let $$X_t$$ and $$Y_t$$ be independent continuous time random walks on the same connected undirected finite graph $$G=(V,E)$$. The meeting time $$T$$ is defined as $$T:=\inf\{t>0:X_t=Y_t,X_{t-}\neq Y_{t-}\}$$. I would like to have a lower bound on $$\min_{x\in V}E[T|X_0=Y_0=x]$$, as a function of the number of vertices $$n=|V|$$, and the maximal degree $$d$$. For fixed $$d$$, I’m hoping for the bound to be linear in $$n$$.

Specifically, the continuous time random walk is defined by associating i.i.d. Poisson clocks to the vertices. Each time the clock rings the random walk steps to a uniformly random neighbor of the current vertex.

If $$G$$ is a path of length $$n$$ and the initial node $$x$$ is an endpoint, then $$E(T)=O(\log n)$$. More precisely, $$P(T>k)=O(1/k) \; \; \text{for} \; \; k \le n^2 \quad (*)$$ $$\text{and } \; \; P(T>k) =O(n^{-2} \,\, 2^{-k/(4n^2)}) \; \; \text{for} \; \; k>n^2 \; \; (**)$$
Proof sketch: $$P(T>k)$$ is twice the probability that continuous time simple random walk in a quadrant (started at the origin) will stay in the cone $$0 for $$k$$ time units. This is within a constant factor of the probability that planar Brownian motion in the upper right quadrant (started at $$1$$, say) will exit the region $$\{z=x+iy: 0 via the arc of the circle. Applying reflection in the $$x$$ -axis and then the conformal map $$z \mapsto z^2$$ converts this to a standard question in the right half plane: the probability that planar Brownian motion (started at 1) in the semicircle $$\{x>0; |z| will exit the semicircle via the circular arc.