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.

  • $\begingroup$ I am now aware of two arguments proving that for fixed $n$, the expected collision time is quadratic in $k$ as $k\to\infty$. $\endgroup$ – 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})$.

| cite | improve this answer | |
  • $\begingroup$ That definition of collision isn't a function of the resulting position, though. $\endgroup$ – Douglas Zare Apr 21 '15 at 23:19
  • $\begingroup$ 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. $\endgroup$ – 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}.$$


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

| cite | improve this answer | |
  • $\begingroup$ You're right. I'll change the notation. $\endgroup$ – Liviu Nicolaescu Apr 24 '15 at 14:04

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.