Transience of Simple Random Walks With Linear Entropy Growth

Abstract

Using the technique of evolving sets, we explore the connection between entropy growth and transience for simple random walks on connected infinite graphs with bounded degree. In particular we show that for a simple random walk starting at a vertex $x_0$, if the entropy after $n$ steps, $E_n$ is at least $Cn$ where the $C$ is independent of $x_0$, then the random walk is transient. We also give an example which demonstrates that the condition of $C$ being independent of $x_0$ is necessary.

8 pages, 1 figure