×

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
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] 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
[2] Altman, E. and Levy, H. (1994). Queueing in space. Adv. in Appl. Probab. 26 1095-1116. · Zbl 0824.60097
[3] 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
[4] Beffara, V., Friedli, S. and Velenik, Y. (2010). Scaling limit of the prudent walk. Electron. Commun. Probab. 15 44-58. · Zbl 1201.60029
[5] Benjamini, I. and Berestycki, N. (2010). Random paths with bounded local time. J. Eur. Math. Soc. ( JEMS ) 12 819-854. · Zbl 1202.60131
[6] Benjamini, I. and Wilson, D. B. (2003). Excited random walk. Electron. Commun. Probab. 8 86-92 (electronic). · Zbl 1060.60043
[7] 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
[8] Bordenave, C., Foss, S. and Last, G. (2011). On the greedy walk problem. Queueing Syst. 68 333-338. · Zbl 1275.60048
[9] Bousquet-Mélou, M. (2010). Families of prudent self-avoiding walks. J. Combin. Theory Ser. A 117 313-344. · Zbl 1228.05026
[10] 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
[11] 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
[12] 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
[13] 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
[14] Davis, B. (1999). Brownian motion and random walk perturbed at extrema. Probab. Theory Related Fields 113 501-518. · Zbl 0930.60041
[15] 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
[16] 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
[17] Kroese, D. P. and Schmidt, V. (1992). A continuous polling system with general service times. Ann. Appl. Probab. 2 906-927. · Zbl 0772.60075
[18] Kroese, D. P. and Schmidt, V. (1994). Single-server queues with spatially distributed arrivals. Queueing Systems Theory Appl. 17 317-345. · Zbl 0806.60084
[19] 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
[20] Kurkova, I. A. (1996). A sequential clearing process. Fundam. Prikl. Mat. 2 619-624. · Zbl 0902.60077
[21] Kurkova, I. A. and Menshikov, M. V. (1997). Greedy algorithm, \(\mathbf{Z}^{1}\) case. Markov Process. Related Fields 3 243-259. · Zbl 0935.60080
[22] 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
[23] 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
[24] 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
[25] 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
[26] Meester, R. and Quant, C. (1999). Stability and weakly convergent approximations of queueing systems on a circle. Available at .
[27] 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
[28] 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
[29] Pemantle, R. (2007). A survey of random processes with reinforcement. Probab. Surv. 4 1-79. · Zbl 1189.60138
[30] Perman, M. and Werner, W. (1997). Perturbed Brownian motions. Probab. Theory Related Fields 108 357-383. · Zbl 0884.60082
[31] Raimond, O. and Schapira, B. (2011). Excited Brownian motions. ALEA Lat. Am. J. Probab. Math. Stat. 8 19-41. · Zbl 1276.60033
[32] Robert, P. (2010). The evolution of a spatial stochastic network. Stochastic Process. Appl. 120 1342-1363. · Zbl 1202.60149
[33] 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
[34] Rolla, L. T. and Sidoravicius, V. Stability of the greedy algorithm on the circle. Available at . arXiv:1112.2389 · Zbl 1242.60104
[35] Schaßberger, R. (1995). Stability of polling networks with state-dependent server routing. Probab. Engrg. Inform. Sci. 9 539-550. · Zbl 1336.68023
[36] Schramm, O. (2000). Scaling limits of loop-erased random walks and uniform spanning trees. Israel J. Math. 118 221-288. · Zbl 0968.60093
[37] 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
[38] 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
[39] 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
[40] 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
[41] Tóth, B. and Werner, W. (1998). The true self-repelling motion. Probab. Theory Related Fields 111 375-452. · Zbl 0912.60056
[42] 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.