Random walks avoiding their convex hull with a finite memory.(English)Zbl 1471.60065
Summary: Fix integers \(d \geq 2\) and \(k \geq d - 1\). Consider a random walk \(X_0, X_1, \ldots\) in \(\mathbb{R}^d\) in which, given \(X_0, X_1, \ldots, X_n (n \geq k)\), the next step \(X_{n + 1}\) is uniformly distributed on the unit ball centred at \(X_n\), but conditioned that the line segment from \(X_n\) to \(X_{n + 1}\) intersects the convex hull of \(\{0, X_{n - k}, \ldots, X_n \}\) only at \(X_n\). For \(k = \infty\) this is a version of the model introduced by Angel et al., which is conjectured to be ballistic, i.e., to have a limiting speed and a limiting direction. We establish ballisticity for the finite-\(k\) model, and comment on some open problems. In the case where \(d = 2\) and \(k = 1\), we obtain the limiting speed explicitly: it is \(8/(9 \pi^2)\).
MSC:
| 60G50 | Sums of independent random variables; random walks |
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
| 52A22 | Random convex sets and integral geometry (aspects of convex geometry) |
Cite
References:
| [1] | Angel, O.; Benjamini, I.; Viràg, B., Random walks that avoid their past convex hull, Electron. Commun. Probab., 8, 6-16 (2003) ·Zbl 1009.60085 |
| [2] | Barber, M. N.; Ninham, B. W., Random and Restricted Walks: Theory and Applications (1970), Gordon and Breach: Gordon and Breach New York ·Zbl 0232.60048 |
| [3] | Baur, E.; Bertoin, J., Elephant random walks and their connection to Pólya-type urns, Phys. Rev. E, 94, Article 052134 pp. (2016) |
| [4] | Beffara, V.; Friedli, S.; Velenik, Y., Scaling limit of the prudent walk, Electron. Commun. Probab., 15, 44-58 (2010) ·Zbl 1201.60029 |
| [5] | Benjamini, I.; Wilson, D. B., Excited random walk, Electron. Commun. Probab., 8, 86-92 (2003) ·Zbl 1060.60043 |
| [6] | Bercu, B., A martingale approach for the elephant random walk, J. Phys. A, 81, Article 015201 pp. (2018) ·Zbl 1392.60038 |
| [7] | Bousquet-Mélou, M., Families of prudent self-avoiding walks, J. Combin. Theory Ser. A, 117, 313-344 (2010) ·Zbl 1228.05026 |
| [8] | Chen, A.; Renshaw, E., The Gillis-Domb-Fisher correlated random walk, J. Appl. Probab., 29, 792-813 (1992) ·Zbl 0768.60058 |
| [9] | Comets, F.; Menshikov, M. V.; Volkov, S.; Wade, A. R., Random walk with barycentric self-interaction, J. Stat. Phys., 143, 855-888 (2011) ·Zbl 1232.82007 |
| [10] | Cruise, J. R.; Wade, A. R., The critical greedy server on the integers is recurrent, Ann. Appl. Probab., 29, 1233-1261 (2019) ·Zbl 1425.60076 |
| [11] | Durrett, R., Probability: Theory and Examples (2010), Cambridge University Press: Cambridge University Press Cambridge ·Zbl 1202.60001 |
| [12] | Foss, S.; Rolla, L.; Sidoravicius, V., Greedy walk on the real line, Ann. Probab., 43, 1399-1418 (2015) ·Zbl 1327.60176 |
| [13] | Gut, A.; Stadtmüller, U., Variations of the elephant random walk (2018), Preprint arXiv:1812.01915 |
| [14] | Kurkova, I. A.; Menshikov, M. V., Greedy algorithm \(\mathbf{Z}^1\) case, Markov Process. Related Fields, 3, 243-259 (1997) ·Zbl 0935.60080 |
| [15] | Lindvall, T., Lectures on the Coupling Method (1992), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York ·Zbl 0760.60078 |
| [16] | Madras, N.; Slade, G., (The Self-Avoiding Walk. The Self-Avoiding Walk, Modern Birkhäuser Classics (2013)), reprint of the 1993 original ·Zbl 1254.01051 |
| [17] | Menshikov, M.; Popov, S.; Wade, A., Non-Homogeneous Random Walks (2016), Cambridge University Press: Cambridge University Press Cambridge |
| [18] | Meyn, S. P.; Tweedie, R. L., Markov Chains and Stochastic Stability (2009), Cambridge University Press: Cambridge University Press Cambridge ·Zbl 0925.60001 |
| [19] | Mountford, T.; Tarrès, P., An asymptotic result for Brownian polymers, Ann. Inst. Henri Poincaré Probab. Stat., 44, 29-46 (2008) ·Zbl 1175.60084 |
| [20] | Norris, J. R.; Rogers, L. C.G.; Williams, D., Self-avoiding random walk: A Brownian motion model with local time drift, Probab. Theory Related Fields, 74, 271-287 (1987) ·Zbl 0611.60052 |
| [21] | Pemantle, R., A survey of random processes with reinforcement, Probab. Surv., 4, 1-79 (2007) ·Zbl 1189.60138 |
| [22] | Pétrélis, N.; Sun, R.; Torri, N., Scaling limit of the uniform prudent walk, Electron. J. Probab., 22, 19 (2017), paper no. 66 ·Zbl 1377.82028 |
| [23] | Rolla, L.; Sidoravicius, V., Stability of the greedy algorithm on the circle, Comm. Pure Appl. Math., 70, 1961-1986 (2017) ·Zbl 1374.60186 |
| [24] | Rolla, L.; Sidoravicius, V.; Tournier, L., Greedy clearing of persistent Poissonian dust, Stochastic Process. Appl., 124, 3496-3506 (2014) ·Zbl 1297.60032 |
| [25] | Smouse, P. E.; Focardi, S.; Moorcroft, P. R.; Kie, J. G.; Forester, J. D.; Morales, J. M., Stochastic modelling of animal movement, Phil. Trans. R. Soc. B, 365, 2201-2211 (2010) |
| [26] | Tóth, B., The “true” self-avoiding walk with bond repulsion on \(\mathbb{Z} \): Limit theorems, Ann. Probab., 23, 1523-1556 (1995) ·Zbl 0852.60083 |
| [27] | Tóth, B., Self-interacting random motions—a survey, (Random Walks (Budapest, 1998). Random Walks (Budapest, 1998), Bolyai Soc. Math. Stud., vol. 9 (1998)), 349-384 ·Zbl 0953.60027 |
| [28] | Tóth, B.; Werner, W., The true self-repelling motion, Probab. Theory Related Fields, 111, 375-452 (1998) ·Zbl 0912.60056 |
| [29] | Zerner, M., On the speed of a planar random walk avoiding its past convex hull, Ann. Inst. Henri Poincaré Probab. Stat., 41, 887-900 (2005) ·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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
