Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 15(2010) > Paper 36 open journal systems 


Entropy of random walk range on uniformly transient and on uniformly recurrent graphs

David Windisch, The Weizmann Institute of Science


Abstract
We study the entropy of the distribution of the set Rn of vertices visited by a simple random walk on a graph with bounded degrees in its first n steps. It is shown that this quantity grows linearly in the expected size of Rn if the graph is uniformly transient, and sublinearly in the expected size if the graph is uniformly recurrent with subexponential volume growth. This in particular answers a question asked by Benjamini, Kozma, Yadin and Yehudayoff (preprint).


Full text: PDF

Pages: 1143-1160

Published on: July 7, 2010
Bibliography
  1. I. Benjamini, G. Kozma, A. Yadin, A. Yehudayoff. Entropy of random walk range. Ann. Inst. H. Poincaré Probab. Statist., to appear. Math. Review number not available.
  2. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms. (second edition) MIT Press, Cambridge, MA, 2001. Math. Review MR1848805 (2002e:68001)
  3. T.M. Cover, J.A. Thomas. Elements of information theory. John Wiley & Sons, Inc., New York, 1991. Math. Review MR1122806 (92g:94001)
  4. R. Durrett. Probability: Theory and Examples. (third edition) Brooks/Cole, Belmont, 2005. Math. Review number not available.
  5. A. Erschler. On drift and entropy growth for random walks on groups. Ann. Probab. 31/3, pp. 1193-1204, 2003. Math. Review MR1988468 (2004c:60018)
  6. V.A. Kaĭmanovich, A.M. Vershik. Random walks on discrete groups: boundary and entropy. Ann. Probab., 11/3, pp. 457-490, 1983. Math. Review MR0704539 (85d:60024)
  7. A. Naor, Y. Peres. Embeddings of discrete groups and the speed of random walks. International Mathematics Research Notices 2008, Art. ID rnn 076. Math. Review MR2439557 (2009m:20067)
  8. P. Révész. Random walk in random and non-random environments. Second edition. World Scientific Publishing Co. Pte. Ltd., Singapore, 2005. Math. Review MR2168855 (2006e:60003)
  9. C.E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, Vol. 27, pp. 379-423, 623-656, 1948. Math. Review MR0026286 (10,133e)
  10. N.T. Varopoulos. Long range estimates for Markov chains. Bull. Sci. Math. (2) 109, pp. 225-252, 1985. Math. Review MR0822826 (87j:60100)
  11. W. Woess. Random walks on infinite graphs and groups. Cambridge University Press, Cambridge, 2000. Math. Review MR1743100 (2001k:60006)
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489