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, and on finding out what happens when $n$ is large and $k = k(n) \rightarrow \infty$, but with no bounds on the rate at which it goes to infinity. 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 $k$ and $n$. Secondary goals include getting bounds that also have a good dependence on $d$ and showing that the actual hitting time is rarely vastly more than the expected hitting time (though the latter should be fairly easy by submultiplicativity).

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

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

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 four 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 interested in the case that $n$ is large and $k = k(n) \rightarrow \infty$, but with no bounds on the rate at which it goes to infinity. 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 $k$ and $n$. Secondary goals include getting bounds that also have a good dependence on $d$ and showing that the actual hitting time is rarely vastly more than the expected hitting time (though the latter should be fairly easy by submultiplicativity).

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!

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, and on finding out what happens when $n$ is large and $k = k(n) \rightarrow \infty$, but with no bounds on the rate at which it goes to infinity. 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 $k$ and $n$. Secondary goals include getting bounds that also have a good dependence on $d$ and showing that the actual hitting time is rarely vastly more than the expected hitting time (though the latter should be fairly easy by submultiplicativity).

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