4
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 6, 2021 at 10:59
  • $\begingroup$ Ah, yes indeed… Thank you. Would you happen to know a potential reference that would answer my question? $\endgroup$
    – Matt
    Dec 6, 2021 at 11:39
  • $\begingroup$ 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. $\endgroup$ Dec 6, 2021 at 12:04

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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