Expected time of distinguishability of a series of Poisson processes bounded by each other

Question

Consider a system of $n$ "bounded" Poisson processes over the integers, $X_1, \ldots X_n$, all incrementing at rate $\lambda$. Initially all the processes begin at $0$. The process $X_i$ is inactive until $X_{i+1} - X_i > 1$, at which point it begins incrementing itself at rate $\lambda$. Whenever $X_{i+1} - X_i \leq 1$, the process $X_i$ stops, waiting for $X_{i+1}$ to increment itself, before becoming active again. ($X_n$ is always active.)

We can see that eventually every $X_i$ will have a unique value. My question is regarding the expected time $E[\mathcal{T}]$ of the first time this event occurs: what is the first time all processes have a unique value?

A simple bound seems to be $E[\mathcal{T}] = O(n^2)$. However, my simulations indicate that this takes linear time in $n$. I'd love to see an analysis that shows something along the lines of $E[\mathcal{T}] = O(n)$, or any other asymptotic analysis for this system.

Answer 1

The process you are looking at is called TASEP (totally asymmetric simple exclusion process); though your initial conditions are unusual. A more conventional version of your question would be to consider the TASEP with step initial conditions (one particle at every negative integer) and ask for a typical time that the first $n$ particles are at distances at least, say, 2 from each other.

TASEP is a determinantal process and it is exactly solvable in a very strong sense, and a huge literature on asymptotic results for TASEP or its generalizations is available. The results in

https://arxiv.org/pdf/0807.1713.pdf

in particular, suggest that the time of interest should indeed scale linearly with $n$; e. g. Theorem 1 say that the typical time before the $n$-th particle moves scales linearly, and the intuition (corroborated by Theorem 2) is that once they all have started moving, they will spread out quickly.

Note that Tracey and Widom are looking at ASEP which is a lot harder (non-determinantal), so their methods would be an overkill for TASEP. Maybe you should look into Johansson's papers they cite or look for a pre-2008 survey on TASEP.