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.
 A: 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})$.
A: 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. $$
