# Probability that two walkers will meet on a graph

Consider two independent continuous random walks on a graph $$G$$ with adjacency matrix $$A$$. I am interested in the probability that the two walkers will ever meet.

When the graph is a $$k$$-regular graph with $$k=1,2$$ then the probability is one, see this question for example: What is the probability that two random walkers will meet?

I tried to derive a simple equation but I am doing something wrong and I cannot determine where it goes wrong, which is the reason of this post. Here is my reasoning:

Let $$p_i(t)$$ (res. $$q_i(t)$$) be probability that walker $$1$$ (res. $$2$$) is at node $$i$$ at time $$t$$. Let $$\gamma(t)$$ denote the probability that the two walkers have already met (at least one time) in the interval $$[0,t]$$. The probability that they have already met at $$t+\mathrm{d}t$$ is:

\begin{align} \gamma(t+\mathrm{d}t)&=1\times \text{"probability they have already met by time t"} \quad + \text{"probability they have NOT already met by time t"}\times \text{"probability they meet in next increment"}\\ &=\gamma(t)+ (1-\gamma(t))\mathrm{d}t \underbrace{\left( \sum_{ij}2\frac{A_{ij}}{k}p_i(t)q_j(t) \right)}_{\text{pr of meeting in next time increment}}. \end{align} In the last line I assumed regular graphs for this example, but this equation could be generalised to general graphs. (Conditioned on the event that walker $$1$$ is on vertex $$i$$ and walker $$2$$ is on vertex $$j$$ the probability that walker $$2$$ moves to vertex $$i$$ in the next time increment is $$\frac{A_{ij}}{k_j}\mathrm{d}t$$)

Taking the limit $$dt\to 0$$ gives me the master equation:

\begin{align} \dot\gamma(t)&=(1-\gamma(t))\left( \sum_{ij}2\frac{A_{ij}}{k}p_i(t)q_j(t) \right)\\ &=(1-\gamma(t))f(t). \end{align}

But if I solve this equation it gives me clearly wrong results, (first the integral of $$f(t)$$ diverges, and even if I take care of this divergence, the rate at which they meet is wrong). However I cannot see at which step I am taking a false assumption? Any remark or reference is always appreciated!

(I am NOT interested in the case where we reduce this problem to a single random walk, because I am interested in the generalization where the space is not homogeneous (e.g., not a regular graph, adding weights on the edges etc.).)

• The two events: "they have NOT already met by time $t$" and "probability they meet in next increment" are clearly not independent. You likely meant "probability they meet in next increment given that they did not meet by time $t$", but that is not given by such a simple expression. Dec 6, 2021 at 10:59
• Ah, yes indeed… Thank you. Would you happen to know a potential reference that would answer my question?
– Matt
Dec 6, 2021 at 11:39
• I am afraid I do not. If $u(t,x,y)$ is the probability that the two processes started at $x$ and $y$ did not meet up to time $t$, then $u$ solves $\partial_t u = L_x u + L_y u$ for $x \ne y$, and $u(0,x,y)=1$, $u(t,x,x)=0$. In particular, $h(x,y) = 1-u(\infty,x,y)$, the probability that they ever meet, is a positive and bounded harmonic function in the complement of the diagonal $x = y$, equal to $1$ on the diagonal. It can be proved that $h$ is the least positive harmonic function in the complement of the diagonal, equal to $1$ on the diagonal. That's all I can say in this generality. Dec 6, 2021 at 12:04