I am looking for a reference or derivation for the following question:

Consider a cycle graph $G$ with $N$ vertices (see example here). Let two independent continuous-time random walkers$^\star$ start on node $i$ and node $j$. Let $T$ be the time when the two walkers meet for the first time.

What will be the probability density function of $T$?

I am looking for the exact expression of that pdf for finite $N$. I am sure this is a well known question with a precise formula but I have not been able to find a clear reference solving it. This is a new field for me so perhaps I am using the wrong vocabulary? With the hope that this post will help. Thanks!

($^\star$: each walker jumps to a neighboring vertex (chosen at random) with rate one.)


1 Answer 1


Assume that $i<j.$ You can reduce this to the following simpler-looking question: Consider a continuous-time RW on the integers, moving at rate two, started at $k:=j-i$. Let $T$ be the hitting time of $\{0,N\}$ by this walk, also known as as the exit time from $[1,N-1]$. Let $\tau$ denote the hitting time of $\{0,N\}$ by discrete-time random walk. The distribution of $\tau$ can be determined from the arguments in Chapter 21 of [1]. (Spitzer gives the general method, and then provides all the details only for the case $k=N/2$.) Then you can deduce the distribution of $T$ via $$P_k[T>q] = \sum_n P[{\rm Poisson}(2q)=m] \cdot P_k[\tau>m] \,.$$

See also [2].

[1] Spitzer, Frank. Principles of random walk. GTM Vol. 34. Second edition, Springer.



Your Answer

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

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