Entropy of Random Walk Range

Itai Benjamini, Gady Kozma, Ariel Yadin, Amir Yehudayoff

Published 2009-03-18Version 1

We study the entropy of the set traced by an $n$-step random walk on $\Z^d$. We show that for $d \geq 3$, the entropy is of order $n$. For $d = 2$, the entropy is of order $n/\log^2 n$. These values are essentially governed by the size of the boundary of the trace.