Transience of simple random walks with linear entropy growth (Q6178793)

Let \((X_n)_{n\geq 0}\) be a simple random walk on an infinite graph of bounded degree, with \(V\) denoting the set of vertices. It is proved that \((X_n)_{n\geq 0}\) is transient, provided that \[ -\sum_{x\in V}\mathbb{P}\{X_n=x\}\log \mathbb{P}\{X_n=x\}\geq Cn, \] where \(C\) is a constant, which does not depend on the starting point of the walk. An essential ingredient of the proof is working with evolving sets, which are a modification of similar objects used in [\textit{B. Morris} and \textit{Y. Peres}, Probab. Theory Relat. Fields 133, No. 2, 245--266 (2005; Zbl 1080.60071)]. Finally, it is shown that the assumption that the constant \(C\) does not depend on the starting position cannot be dispensed with.