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.


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

  • $\begingroup$ Toda, Yuval. It is surprising! Is there any non-constant lower bound? $\endgroup$
    – Ron P
    Commented Mar 7, 2021 at 6:12
  • $\begingroup$ Indeed it is surprising, since if you start at the middle of the path the answer is linear in n. $\endgroup$ Commented Mar 8, 2021 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.