Entropy of random walk range

Itai Benjamini; Gady Kozma; Ariel Yadin; Amir Yehudayoff

Annales de l'I.H.P. Probabilités et statistiques (2010)

  • Volume: 46, Issue: 4, page 1080-1092
  • ISSN: 0246-0203

Abstract

top
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.

How to cite

top

Benjamini, Itai, et al. "Entropy of random walk range." Annales de l'I.H.P. Probabilités et statistiques 46.4 (2010): 1080-1092. <http://eudml.org/doc/240018>.

@article{Benjamini2010,
abstract = {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.},
author = {Benjamini, Itai, Kozma, Gady, Yadin, Ariel, Yehudayoff, Amir},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {random walk; entropy},
language = {eng},
number = {4},
pages = {1080-1092},
publisher = {Gauthier-Villars},
title = {Entropy of random walk range},
url = {http://eudml.org/doc/240018},
volume = {46},
year = {2010},
}

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
PB - Gauthier-Villars
VL - 46
IS - 4
SP - 1080
EP - 1092
AB - 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.
LA - eng
KW - random walk; entropy
UR - http://eudml.org/doc/240018
ER -

References

top
  1. [1] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, New York, 1991. Zbl1140.94001MR1122806
  2. [2] G. F. Lawler. Intersections of Random Walks. Springer, New York, 1996. Zbl0925.60078
  3. [3] Y. Peres. Intersection-equivalence of Brownian paths and certain branching processes. Comm. Math. Phys. 177 (1996) 417–434. Zbl0851.60080MR1384142
  4. [4] P. Révész. Random Walk in Random and Non-Random Environments. World Scientific, Hackensack, NJ, 2005. Zbl1090.60001MR2168855
  5. [5] D. Revuz and M. Yor. Continuous Martingales and Brownian Motion. Springer, Berlin, 1991. Zbl0917.60006MR1083357
  6. [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. Zbl1226.60070MR2659760

NotesEmbed ?

top

You must be logged in to post comments.