Entropy of random walk range on uniformly transient and on uniformly recurrent graphs
arXiv:1001.0355
Abstract
We study the entropy of the distribution of the set R_n 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 R_n 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 (arXiv:0903.3179v1).
17 pages, 2 figures