Three Favorite Edges Occurs Infinitely Often for One-Dimensional Simple Random Walk

Abstract

For a one-dimensional simple symmetric random walk $(S_n)$, an edge x (between points $x-1$ and x) is called a favorite edge at time n if its local time at n achieves the maximum among all edges. In this paper, we show that with probability 1 three favorite edges occurs infinitely often. Our work is inspired by Tóth and Werner (Comb Probab Comput 6:359–369, 1997), and Ding and Shen (Ann Probab 46:2545–2561, 2018), disproves a conjecture mentioned in Remark 1 on page 368 of Tóth and Werner (1997).

Keywords

Random walk / Favorite edge / Invariance principle for one-side local times / Wiener process

References

[1] Abe Y. Maximum and minimum of local times for two-dimensional random walk. Electron. Commun. Probab.. 2015, 20 22

[2] Bass RF, Eisenbaum N, Shi Z. The most visited sites of symmetric stable processes. Probab. Theory Relat. Fields. 2000, 116 391-404

[3] Bass RF, Griffin PS. The most visited site of Brownian motion and simple random walk. Z. Wahrsch. Verw. Gebiete. 1985, 70 417-436

[4] Chen D, de Raphélis L, Hu Y. Favorite sites of randomly biased walks on a supercritical Galton–Watson tree. Stoch. Process. Appl.. 2018, 128 1525-1557

[5] Chung, K.L.: The strong law of large numbers. In: Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pp. 341–352. University of California Press (1951)

[6] Csáki E, Révész P. Strong invariance for local times. Z. Wahrsch. Verw. Gebiete. 1983, 62 263-278

[7] Csáki E, Révész P, Shi Z. Favourite sites, favourite values and jump sizes for random walk and Brownian motion. Bernoulli. 2000, 6 951-975

[8] Csáki E, Shi Z. Large favourite sites of simple random walk and the Wiener process. Electron. J. Probab.. 1998, 3 14

[9] Csörgő M, Horváth L. On best possible approximations of local time. Stat. Probab. Lett.. 1989, 8 301-306

[10] Dembo, A.: Favorite points, cover times and fractals. In: Lectures on Probability Theory and Statistics. Lecture Notes in Mathematics, vol. 1869, pp. 1–101. Springer, Berlin (2005)

[11] Dembo A, Peres Y, Rosen J, Zeitouni O. Thick points for planar Brownian motion and the Erdős–Taylor conjecture on random walk. Acta Math.. 2001, 186 239-270

[12] Ding J, Shen J. Three favorite sites occurs infinitely often for one-dimensional simple random walk. Ann. Probab.. 2018, 46 2545-2561

[13] Eisenbaum, N.: Temps locaux, excursions et lieu le plus visité par un mouvement brownien lineaire. Thèse de doctorat, Université de Paris 7 (1989)

[14] Eisenbaum N. On the most visited sites by a symmetric stable process. Probab. Theory Relat. Fields. 1997, 107 527-535

[15] Eisenbaum N, Khoshnevisan D. On the most visited sites of symmetric Markov processes. Stoch. Process. Appl.. 2002, 101 241-256

[16] Erdős P, Révész P. On the favourite points of a random walk. Math. Struct. Comput. Math. Math. Model.. 1984, 2 152-157

[17] Erdős, P., Révész, P.: Problems and results on random walks. In: Mathematical Statistics and Probability Theory, Vol. B (Bad Tatzmannsdorf, 1986). pp. 59–65. Reidel, Dordrecht (1987)

[18] Erdős P, Révész P. Three problems on the random walk in ${\textbf{Z} }^d$. Stud. Sci. Math. Hung.. 1991, 26 309-320

[19] Hao, C.-X., Hu, Z.-C., Ma, T., Song, R.: Favorite downcrossing sites for one-dimensional simple random walk (in Chinese). J. Sichuan Univ. Nat. Sci. Ed. 60, 051002 (2023)

[20] Hu Y, Shi Z. The problem of the most visited site in random environment. Probab. Theory Relat. Fields. 2000, 116 273-302

[21] Hu Y, Shi Z. The most visited sites of biased random walks on trees. Electron. J. Probab.. 2015, 20 62

[22] Kesten H. An interated logarithm law for the local time. Duke Math. J.. 1965, 32 447-456

[23] Kesten H, Spitzer F. A limit theorem related to a new class of self similar processes. Z. Wahrsch. Verw. Gebiete. 1979, 50 5-25

[24] Khoshnevisan D, Lewis TM. The favorite point of a Poisson process. Stoch. Process. Appl.. 1995, 57 19-38

[25] Knight FB. Random walks and a sojourn density process of Brownian motion. Trans. Am. Math. Soc.. 1963, 109 56-86

[26] Leuridan C. Le point d’un fermé le plus visité par le mouvement brownien. Ann. Probab.. 1997, 25 953-996

[27] Li B, Xiao Y, Yang X. On the favorite points of symmetric Lévy processes. J. Theor. Probab.. 2019, 32 1943-1972

[28] Lifshits MA, Shi Z. The escape rate of favorite sites of simple random walk and Brownian motion. Ann. Probab.. 2004, 32 129-152

[29] Marcus MB. The most visited sites of certain Lévy processes. J. Theor. Probab.. 2001, 14 867-885

[30] Okada, I.: Topics and problems on favorite sites of random walks. In: Stochastic Analysis on Large Scale Interacting Systems, pp. 129–139, RIMS Kôkyûroku Bessatsu, B59, Research Institute for Mathematical Sciences (RIMS), Kyoto (2016)

[31] Révész, P.: Local time and invariance. In: Analytical Methods in Probability Theory, Proceedings, Oberwolfach, Germany 1980, Lecture Notes in Mathematics, vol. 861, pp. 128–145. Springer, Berlin (1981)

[32] Révész P. Random Walk in Random and Non-random Environment. 1990 Singapore: World Scientific

[33] Shi Z, Tóth B. Favourite sites of simple random walk. Period. Math. Hung.. 2000, 41 237-249

[34] Tóth B. No more than three favorite sites for simple random walk. Ann. Probab.. 2001, 29 484-503

[35] Tóth B, Werner W. Tied favourite edges for simple random walk. Comb. Probab. Comput.. 1997, 6 359-369

Funding

National Natural Science Foundation of China(12171335)

National Natural Science Foundation of China(11871184)

Simons Foundation(429343)