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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.