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

given thatthey did not meet by time $t$", but that is not given by such a simple expression. $\endgroup$leastpositive harmonic function in the complement of the diagonal, equal to $1$ on the diagonal. That's all I can say in this generality. $\endgroup$