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.)
Best Answer
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.
[2]https://www.researchgate.net/publication/254211645_Exit_times_for_a_class_of_random_Walks_Exact_distribution_results