# First collision time of $n$ random walkers on a cycle

My question is somehow related to the one here First Collision Time for k Random Walkers on a Torus but, unfortunately, the answer does not cover my concern.

My problem is: consider $n$ walkers on the cycle $\mathbb{Z}/k$ ($n < k$). At each step, one walker is selected with probability $1/n$ and moves by one unit counter-clockwise; the other walkers remain at their locations. The steps are independent.

I would like to have some information on the first time $T$ until two walkers collide (go into to the same site); e.g., expectation, asymptotic behaviour (e.g. $k,n \rightarrow \infty$ in some proportion), etc.

When $n = 2$, this reduces to a single random walker on the cycle moving clockwise, or counter-clockwise with probability $1/2$, and the time $T$ is simply the hitting time of the site $0$.

But for arbitrary $n$, this approach does not seem to work ...

Do you have any ideas, or references to similar problems ?

Thank you.

• I am now aware of two arguments proving that for fixed $n$, the expected collision time is quadratic in $k$ as $k\to\infty$. – Liviu Nicolaescu Apr 30 '15 at 15:01

Suppose the initial distribution of walkers has each independently choosing a site with equal probabilities (note that multiply-occupied sites are allowed). This distribution is invariant under the process. The probability of a collision at any step is the probability that the site the moving walker enters is occupied, which is $1 - (1-1/k)^{n-1}$. By the elementary renewal theorem, the expected time between collisions is $1/(1 - (1-1/k)^{n-1})$.

• That definition of collision isn't a function of the resulting position, though. – Douglas Zare Apr 21 '15 at 23:19
• I ran computer simulations in the case of $k=100$ vertices and $n\in\{3,4\}$. For each choice of $n$ I have run random walks with $4000$ randomly chosen initial choices of $n$ vertices. The average collision times I got were $499$, when $n=3$, and $218$, when $n=4$. I have run these simulations twice and the results were within $10$ of the above numbers. – Liviu Nicolaescu Apr 29 '15 at 12:30

Let me consider the special case $n=2$, so there are two players. In this case, the problem reduces to a random walk on $\newcommand{\bZ}{\mathbb{Z}}$ $I_k:=\bZ\cap [0,k]$ with absorbition at both ends.

Indeed, in this case we have two players $p_1$, $p_2$. When $p_1$ moves counterclockwisely, it is as if $p_2$ moved clockwisely. So we may assume that $p_1$ fixed at $0\bmod k$ and the $p_2$ moves (counter)clockwisely with equal probability. The colusion occurs when $p_2$ reaches one of the endpoints of $[0,k]$.

The expected time to collision given that $p_2$ starts at $z\in I_k$ is (see Feller vol.1, Section XIV.3, eq. (3.5))

$$T_k(z)= z(k-z).$$

The player $p_2$ is equally likely to start at any of the positions $z=1,\dotsc, k\in I_k$. (Recall that $0=k\bmod k$.) Thus, the expected time to collision is (hat tip to Douglas Zare)

$$T_k=\frac{1}{k}\sum_{z\in I_k\setminus 0} z(k-z) =\sum_{j=1}^kj -\frac{1}{k}\sum_{j=1}^k j^2= \frac{k(k+1)}{2}-\frac{(k+1)(2k+1)}{6}$$

$$= \frac{(k^2-1)}{6}.$$

Thus

$$T_k\sim\frac{k^2}{6}\;\;\mbox{as}\;\;k\to\infty.$$

• You're right. I'll change the notation. – Liviu Nicolaescu Apr 24 '15 at 14:04