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.).)
Best Answer
This is equivalent to the question whether two walks will necessarily meet infinitely often (with probability one) or not. This question has been studied in some detail, see in particular [2] where some general criteria are given.
[1] Krishnapur, Manjunath, and Yuval Peres. "Recurrent graphs where two independent random walks collide finitely often." Electronic communications in probability 9 (2004): 72-81.
[2] Barlow, Martin T., Yuval Peres, and Perla Sousi. "Collisions of random walks." In Annales de l'IHP Probabilités et statistiques, vol. 48, no. 4, pp. 922-946. 2012.
[3] Chen, XinXing, and DaYue Chen. "Two random walks on the open cluster of ℤ 2 meet infinitely often." Science China Mathematics 53, no. 8 (2010): 1971-1978.
[4] Hutchcroft, Tom, and Yuval Peres. "Collisions of random walks in reversible random graphs." Electronic Communications in Probability 20 (2015): 1-6.