Greedy walk on the real line

Abstract

We consider a self-interacting process described in terms of a single-server system with service stations at each point of the real line. The customer arrivals are given by a Poisson point processes on the space-time half plane. The server adopts a greedy routing mechanism, traveling toward the nearest customer, and ignoring new arrivals while in transit. We study the trajectories of the server and show that its asymptotic position diverges logarithmically in time.

Published at http://dx.doi.org/10.1214/13-AOP898 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (9)

• A survey of random processes with reinforcement
• Conformal invariance in random cluster models. I. Holomorphic fermions in the Ising model
• An asymptotic result for Brownian polymers
• Families of prudent self-avoiding walks
• Linearly edge-reinforced random walks
• Scaling Limit of the Prudent Walk
• The Evolution of a Spatial Stochastic Network
• Stability of the Greedy Algorithm on the Circle
• Stability of a spatial polling system with greedy myopic service

Cited by in corpus (5)

• Stability of the Greedy Algorithm on the Circle
• Random walks avoiding their convex hull with a finite memory
• The critical greedy server on the integers is recurrent
• Greedy walks on two lines
• Many greedy cleaners in a Poisson environment