Longest distance of a non-uniform dispersion process on the infinite line (Q2203601)

This paper considers a dispersion process on the graph which is the (two-way) infinite path labelled by the integers, so that neighbouring vertices are labelled by consecutive integers. At the beginning, \(n\) particles are placed at the origin (the vertex labelled 0). At step \(t\), for any vertex on which there are at least two particles, each of them moves to the largest neighbour with probability \(p_n\) or the smallest neighbour with probability \(1-p_n\), independently of every other particle. The process stops when all vertices are occupied by at most one particle. The main theorem states that when \(p_n\) is bounded from above and below by \(\sqrt{2}/2\) and \(1- \sqrt{2}/2\), respectively, then the furthest (from the origin) vertex that is occupied at the end is \(\Theta (n)\), with high probability. Also, the process finishes within \(O(n^8)\) with high probability. The former result works for larger range of \(p_n\) that previously known (that was known for \(p_n=1/2\)) and also it provides a matching asymptotic lower bound on the distance. Furthermore, the author also shows that if \(0< p_n <1\), then the process stops eventually with high probability as \(n\to \infty\).