Entropy of random walk range
Annales de l'I.H.P. Probabilités et statistiques, Volume 46 (2010) no. 4, p. 1080-1092

We study the entropy of the set traced by an n-step simple symmetric random walk on ℤd. We show that for d≥3, the entropy is of order n. For d=2, the entropy is of order n/log2n. These values are essentially governed by the size of the boundary of the trace.

Nous étudions l'entropie de la trace d'une marche aléatoire simple et symétrique de longueur n sur ℤd. Nous montrons que si d≥3, cette entropie est d'ordre n, tandis que pour d=2 elle est d'ordre n/log2n. Ces valeurs proviennent essentiellement de la taille de la frontière de la trace.

DOI : https://doi.org/10.1214/09-AIHP345
Classification:  82C41,  94A17
Keywords: random walk, entropy
@article{AIHPB_2010__46_4_1080_0,
     author = {Benjamini, Itai and Kozma, Gady and Yadin, Ariel and Yehudayoff, Amir},
     title = {Entropy of random walk range},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {46},
     number = {4},
     year = {2010},
     pages = {1080-1092},
     doi = {10.1214/09-AIHP345},
     zbl = {1208.82046},
     mrnumber = {2744887},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2010__46_4_1080_0}
}
Benjamini, Itai; Kozma, Gady; Yadin, Ariel; Yehudayoff, Amir. Entropy of random walk range. Annales de l'I.H.P. Probabilités et statistiques, Volume 46 (2010) no. 4, pp. 1080-1092. doi : 10.1214/09-AIHP345. http://www.numdam.org/item/AIHPB_2010__46_4_1080_0/

[1] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, New York, 1991. | MR 1122806 | Zbl 1140.94001

[2] G. F. Lawler. Intersections of Random Walks. Springer, New York, 1996. | Zbl 0925.60078

[3] Y. Peres. Intersection-equivalence of Brownian paths and certain branching processes. Comm. Math. Phys. 177 (1996) 417-434. | MR 1384142 | Zbl 0851.60080

[4] P. Révész. Random Walk in Random and Non-Random Environments. World Scientific, Hackensack, NJ, 2005. | MR 2168855 | Zbl 1090.60001

[5] D. Revuz and M. Yor. Continuous Martingales and Brownian Motion. Springer, Berlin, 1991. | MR 1083357 | Zbl 0917.60006

[6] D. Windisch. Entropy of random walk range on uniformly transient and on uniformly recurrent graphs. Preprint. Available at http://arxiv.org/abs/1001.0355. | MR 2659760 | Zbl pre05946929