# First Collision Time for k Random Walkers on a Torus

I consider $k$ random walkers on $\mathbb{Z}^{d}/n \mathbb{Z}^{d}$, the $d$-dimensional torus of side length $n$. More precisely, I will define a Markov chain $Z_{t} = (X_{t}[1], \ldots, X_{t}[k])$ with $X_{t}[i] \in \mathbb{Z}^{d}/n \mathbb{Z}^{d}$. To evolve this Markov chain, at each time step $t$ choose an index $i \in \{1,2,\ldots,k\}$ uniformly at random, then set $X_{t+1}[i]$ to be one of the $2d$ vertices in the torus adjacent to $X_{t}[i]$, again chosen uniformly at random.

Finally, for points $u,v \in \mathbb{Z}^{d}/n \mathbb{Z}^{d}$, say $u \sim v$ if they are adjacent in the torus and define

$\tau_{adjacent}^{k} = \inf \{ t \, : \, \exists i \neq j \, s.t. \, X_{t}[i] \sim X_{t}[j] \}$.

My question: what is known about the distribution of $\tau_{adjacent}$?

More specifically: I am most interested in the `worst-case' initial conditions (i.e. the initial conditions that minimize or maximize this expectation), and on finding out what happens when $n$ is large and for any condition on $k$ The most important thing for me is to get an upper bound on $E[\tau_{adjacent}^{k}]$ that is close to tight in its dependence on $n$ and not awful in its dependence on $k$. Secondary goals include getting bounds that also have a good dependence on $d$ and showing that the actual hitting time is rarely vastly different from the expected hitting time.

What little I know already: It is easy to compute the expected value of the adjacency time in the case $k = 2$, and this provides upper and lower bounds on the adjacency time for $k$ particles. Those bounds are fine if $k$ is uniformly bounded, but I don't know how to generalize them to big $k$ in a useful way.

PS: Any references to the same problem on general graphs would be greatly appreciated!

EDIT: Clarified in response to comments

• There are generally more than four adjacent vertices. Also, what is your initial condition? – Steve Huntsman Jun 7 '14 at 15:05
• Thanks for the comment, Steve. The question has (I hope) been clarified. In particular: 1. Agreed; there should be $2d$ adjacent vertices and 2. Any initial conditions are interesting, but I am most interested in the worst case (e.g. $\sup_{z} E[\tau_{adjacent}^{k} \vert Z_{0} = z]$) – AMQS Jun 7 '14 at 15:19

The answer would depend on whether $d\leq2$ or $d>2$. In the higher dimensional case, we expect the answer to be of order $n^d/k$ (since only one walker moves at each step). If $k \ll n^{(d-2)/2}$ then it is unlikely that any pair meets before time $k n^2$ (even for random starting points) and after $k n^2$ steps the walkers are mixed, so the initial conditions do not matter too much.
If you are interested in larger $k$ or in $d\leq 2$ different arguments are needed.