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

  • $\begingroup$ There are generally more than four adjacent vertices. Also, what is your initial condition? $\endgroup$ – Steve Huntsman Jun 7 '14 at 15:05
  • $\begingroup$ 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]$) $\endgroup$ – 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.


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.