# zbMATH — the first resource for mathematics

Greedy walk on the real line. (English) Zbl 1327.60176
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.

##### MSC:
 60K25 Queueing theory (aspects of probability theory) 60K35 Interacting random processes; statistical mechanics type models; percolation theory 60G55 Point processes (e.g., Poisson, Cox, Hawkes processes) 90B22 Queues and service in operations research
Full Text:
##### References:
  Altman, E. and Foss, S. (1997). Polling on a space with general arrival and service time distribution. Oper. Res. Lett. 20 187-194. · Zbl 0879.90094  Altman, E. and Levy, H. (1994). Queueing in space. Adv. in Appl. Probab. 26 1095-1116. · Zbl 0824.60097  Angel, O., Benjamini, I. and Virág, B. (2003). Random walks that avoid their past convex hull. Electron. Commun. Probab. 8 6-16 (electronic). · Zbl 1009.60085  Beffara, V., Friedli, S. and Velenik, Y. (2010). Scaling limit of the prudent walk. Electron. Commun. Probab. 15 44-58. · Zbl 1201.60029  Benjamini, I. and Berestycki, N. (2010). Random paths with bounded local time. J. Eur. Math. Soc. ( JEMS ) 12 819-854. · Zbl 1202.60131  Benjamini, I. and Wilson, D. B. (2003). Excited random walk. Electron. Commun. Probab. 8 86-92 (electronic). · Zbl 1060.60043  Bertsimas, D. J. and Ryzin, G. V. (1991). A stochastic and dynamic vehicle routing problem in the Euclidean plane. Oper. Res. 39 601-615. · Zbl 0736.90027  Bordenave, C., Foss, S. and Last, G. (2011). On the greedy walk problem. Queueing Syst. 68 333-338. · Zbl 1275.60048  Bousquet-Mélou, M. (2010). Families of prudent self-avoiding walks. J. Combin. Theory Ser. A 117 313-344. · Zbl 1228.05026  Carmona, P., Petit, F. and Yor, M. (1998). Beta variables as times spent in $$[0,\infty[$$ by certain perturbed Brownian motions. J. Lond. Math. Soc. (2) 58 239-256. · Zbl 0924.60067  Chaumont, L. and Doney, R. A. (1999). Pathwise uniqueness for perturbed versions of Brownian motion and reflected Brownian motion. Probab. Theory Related Fields 113 519-534. · Zbl 0945.60082  Coffman, E. G. Jr. and Gilbert, E. N. (1987). Polling and greedy servers on a line. Queueing Systems Theory Appl. 2 115-145. · Zbl 0653.90021  Davis, B. (1996). Weak limits of perturbed random walks and the equation $$Y_{t}=B_{t}+\alpha\sup\{Y_{s}: s\leq t\}+\beta\inf\{Y_{s}: s\leq t\}$$. Ann. Probab. 24 2007-2023. · Zbl 0870.60076  Davis, B. (1999). Brownian motion and random walk perturbed at extrema. Probab. Theory Related Fields 113 501-518. · Zbl 0930.60041  Foss, S. and Last, G. (1996). Stability of polling systems with exhaustive service policies and state-dependent routing. Ann. Appl. Probab. 6 116-137. · Zbl 0863.60091  Foss, S. and Last, G. (1998). On the stability of greedy polling systems with general service policies. Probab. Engrg. Inform. Sci. 12 49-68. · Zbl 0962.60099  Kroese, D. P. and Schmidt, V. (1992). A continuous polling system with general service times. Ann. Appl. Probab. 2 906-927. · Zbl 0772.60075  Kroese, D. P. and Schmidt, V. (1994). Single-server queues with spatially distributed arrivals. Queueing Systems Theory Appl. 17 317-345. · Zbl 0806.60084  Kroese, D. P. and Schmidt, V. (1996). Light-traffic analysis for queues with spatially distributed arrivals. Math. Oper. Res. 21 135-157. · Zbl 0848.60087  Kurkova, I. A. (1996). A sequential clearing process. Fundam. Prikl. Mat. 2 619-624. · Zbl 0902.60077  Kurkova, I. A. and Menshikov, M. V. (1997). Greedy algorithm, $$\mathbf{Z}^{1}$$ case. Markov Process. Related Fields 3 243-259. · Zbl 0935.60080  Lawler, G. F., Schramm, O. and Werner, W. (2004). Conformal invariance of planar loop-erased random walks and uniform spanning trees. Ann. Probab. 32 939-995. · Zbl 1126.82011  Lawler, G. F., Schramm, O. and Werner, W. (2004). On the scaling limit of planar self-avoiding walk. In Fractal Geometry and Applications : A Jubilee of Benoît Mandelbrot , Part 2. Proc. Sympos. Pure Math. 72 339-364. Amer. Math. Soc., Providence, RI. · Zbl 1069.60089  Leskelä, L. and Unger, F. (2012). Stability of a spatial polling system with greedy myopic service. Ann. Oper. Res. 198 165-183. · Zbl 1251.90095  Litvak, N. and Adan, I. (2001). The travel time in carousel systems under the nearest item heuristic. J. Appl. Probab. 38 45-54. · Zbl 0989.60024  Meester, R. and Quant, C. (1999). Stability and weakly convergent approximations of queueing systems on a circle. Available at .  Merkl, F. and Rolles, S. W. W. (2006). Linearly edge-reinforced random walks. In Dynamics & Stochastics. Institute of Mathematical Statistics Lecture Notes-Monograph Series 48 66-77. IMS, Beachwood, OH. · Zbl 1125.82014  Mountford, T. and Tarrès, P. (2008). An asymptotic result for Brownian polymers. Ann. Inst. Henri Poincaré Probab. Stat. 44 29-46. · Zbl 1175.60084  Pemantle, R. (2007). A survey of random processes with reinforcement. Probab. Surv. 4 1-79. · Zbl 1189.60138  Perman, M. and Werner, W. (1997). Perturbed Brownian motions. Probab. Theory Related Fields 108 357-383. · Zbl 0884.60082  Raimond, O. and Schapira, B. (2011). Excited Brownian motions. ALEA Lat. Am. J. Probab. Math. Stat. 8 19-41. · Zbl 1276.60033  Robert, P. (2010). The evolution of a spatial stochastic network. Stochastic Process. Appl. 120 1342-1363. · Zbl 1202.60149  Rojas-Nandayapa, L., Foss, S. and Kroese, D. P. (2011). Stability and performance of greedy server systems. A review and open problems. Queueing Syst. 68 221-227. · Zbl 1275.60085  Rolla, L. T. and Sidoravicius, V. Stability of the greedy algorithm on the circle. Available at . arXiv:1112.2389 · Zbl 1242.60104  Schaßberger, R. (1995). Stability of polling networks with state-dependent server routing. Probab. Engrg. Inform. Sci. 9 539-550. · Zbl 1336.68023  Schramm, O. (2000). Scaling limits of loop-erased random walks and uniform spanning trees. Israel J. Math. 118 221-288. · Zbl 0968.60093  Smirnov, S. (2001). Critical percolation in the plane: Conformal invariance, Cardy’s formula, scaling limits. C. R. Acad. Sci. Paris Sér. I Math. 333 239-244. · Zbl 0985.60090  Smirnov, S. (2010). Conformal invariance in random cluster models. I. Holomorphic fermions in the Ising model. Ann. of Math. (2) 172 1435-1467. · Zbl 1200.82011  Tóth, B. (1995). The “true” self-avoiding walk with bond repulsion on $$\mathbf{Z}$$: Limit theorems. Ann. Probab. 23 1523-1556. · Zbl 0852.60083  Tóth, B. (1999). Self-interacting random motions-A survey. In Random Walks ( Budapest , 1998). Bolyai Soc. Math. Stud. 9 349-384. János Bolyai Math. Soc., Budapest. · Zbl 0953.60027  Tóth, B. and Werner, W. (1998). The true self-repelling motion. Probab. Theory Related Fields 111 375-452. · Zbl 0912.60056  Zerner, M. P. W. (2005). On the speed of a planar random walk avoiding its past convex hull. Ann. Inst. Henri Poincaré Probab. Stat. 41 887-900. · Zbl 1073.60100
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.