×

Entropy of random walk range on uniformly transient and on uniformly recurrent graphs. (English) Zbl 1226.60070

Summary: 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 of \(R_{n}\) if the graph is uniformly recurrent with subexponential volume growth. This in particular answers a question asked by I. Benjamini, G. Kozma, A. Yadin and A. Yehudayoff [Ann. Inst. Henri PoincarĂ©, Probab. Stat. 46, No. 4, 1080–1092 (2010; Zbl 1208.82046)].

MSC:

60G50 Sums of independent random variables; random walks
60J05 Discrete-time Markov processes on general state spaces

Citations:

Zbl 1208.82046
PDF BibTeX XML Cite
Full Text: DOI arXiv EMIS