Greedy walk on the real line (Q2352757)

The authors study a single-server system with a space-time Poisson point process of customers with intensity \(\lambda > 0\). The server starts at the origin and chooses the nearest present customer (on the real line, ignoring new arrivals) to be served, that is, it uses a greedy strategy. After service (with service time \(T\)) the customer leaves the system. In particular, after the server starts to work at instant \(t=0\), the first customer is found to the left or to the right with equal probability. As the authors state, the real line (instead of a discrete structure) is more adapted to describe spatial large systems. However, this approach is highly sensitive to microscopic changes of the server position, and it makes analysis of this greedy walk a challenging problem. It is assumed that the server knows only the information needed to determine the next movement, positions of the further customers remaining unknown. A particular feature of this model is that the server's path is self-repelling, because the removal of a served customer in a region makes it less likely for the server to take the next step back into this region. This observation supports the main idea of the proof: to show that the local changes in the server's course can be ignored. Initially, the case \(T=1\) and the infinite travel speed of the server (to a new customer) is considered, then a general case is analyzed. Assuming that \(T\) has all exponential moments, the authors prove the following main result: the server position \(S(t)\) at time \(t\) is transient: \(\lambda S(t)/\log t\to \pm 1\) as \(t\to \infty\) with probability \(1/2\) each.