Nonconcentration of return times

Abstract

We show that the distribution of the first return time $\tau$ to the origin, v, of a simple random walk on an infinite recurrent graph is heavy tailed and nonconcentrated. More precisely, if $d_v$ is the degree of v, then for any $t\ge 1$ we have \[\mathbf{P}_v(τ\ge t)\ge\frac{c}{d_v\sqrt{t}}\] and \[\mathbf{P}_v(τ=t\midτ\geq t)\leq\frac{C\log(d_vt)}{t}\] for some universal constants $c>0$ and $C<\infty$. The first bound is attained for all t when the underlying graph is $\mathbb{Z}$, and as for the second bound, we construct an example of a recurrent graph G for which it is attained for infinitely many t's. Furthermore, we show that in the comb product of that graph G with $\mathbb{Z}$, two independent random walks collide infinitely many times almost surely. This answers negatively a question of Krishnapur and Peres [Electron. Commun. Probab. 9 (2004) 72-81] who asked whether every comb product of two infinite recurrent graphs has the finite collision property.

Published in at http://dx.doi.org/10.1214/12-AOP785 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)