Entropy of random walk range
Annales de l'I.H.P. Probabilités et statistiques, Volume 46 (2010) no. 4, pp. 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: 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},
     pages = {1080--1092},
     publisher = {Gauthier-Villars},
     volume = {46},
     number = {4},
     year = {2010},
     doi = {10.1214/09-AIHP345},
     zbl = {1208.82046},
     mrnumber = {2744887},
     language = {en},
     url = {http://www.numdam.org/articles/10.1214/09-AIHP345/}
}
TY  - JOUR
AU  - Benjamini, Itai
AU  - Kozma, Gady
AU  - Yadin, Ariel
AU  - Yehudayoff, Amir
TI  - Entropy of random walk range
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2010
DA  - 2010///
SP  - 1080
EP  - 1092
VL  - 46
IS  - 4
PB  - Gauthier-Villars
UR  - http://www.numdam.org/articles/10.1214/09-AIHP345/
UR  - https://zbmath.org/?q=an%3A1208.82046
UR  - https://www.ams.org/mathscinet-getitem?mr=2744887
UR  - https://doi.org/10.1214/09-AIHP345
DO  - 10.1214/09-AIHP345
LA  - en
ID  - AIHPB_2010__46_4_1080_0
ER  - 
%0 Journal Article
%A Benjamini, Itai
%A Kozma, Gady
%A Yadin, Ariel
%A Yehudayoff, Amir
%T Entropy of random walk range
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2010
%P 1080-1092
%V 46
%N 4
%I Gauthier-Villars
%U https://doi.org/10.1214/09-AIHP345
%R 10.1214/09-AIHP345
%G en
%F 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/articles/10.1214/09-AIHP345/

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

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

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

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

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

[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

Cited by Sources: