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

Question

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.

Answer 1

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<y<x$ 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<y<x,; \; |z|< \sqrt{k}\}$ 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|<k \}$ will exit the semicircle via the circular arc.

[1] Burdzy, Krzysztof, and Gregory F. Lawler. "Non-intersection exponents for Brownian paths." Probability theory and related fields 84, no. 3 (1990): 393-410.