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

David Windisch

Published 2010-01-03, updated 2010-07-11Version 2

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