Nonconcentration of return times. (English) Zbl 1268.05183

Summary: 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 non concentrated. More precisely, if \(d_v\) is the degree of \(v\), then for any \(t\geq 1\) we have \[ {\mathbf P}_v(\tau\geq t)\geq{c\over d_v\sqrt{t}} \] and \[ {\mathbf P}_v(\tau= t\mid \tau\geq t)\leq {C\log(d_v t)\over 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 M. Krishnapur and Y. Peres [Electron. Commun. Probab. 9, 72–81 (2004; Zbl 1060.60044)] who asked whether every comb product of two infinite recurrent graphs has the finite collision property.


05C81 Random walks on graphs
05C63 Infinite graphs
60G50 Sums of independent random variables; random walks


Zbl 1060.60044
Full Text: DOI arXiv Euclid


[1] Barlow, M., Peres, Y. and Sousi, P. (2010). Collisions of random walks. Preprint. Available at . · Zbl 1285.60073
[2] Benjamini, I. and Kozma, G. (2005). A resistance bound via an isoperimetric inequality. Combinatorica 25 645-650. · Zbl 1098.60075 · doi:10.1007/s00493-005-0040-4
[3] Feller, W. (1971). An Introduction to Probability Theory and Its Applications. Vol. II , 2nd ed. Wiley, New York. · Zbl 0219.60003
[4] Halmos, P. R. (1963). What does the spectral theorem say? Amer. Math. Monthly 70 241-247. · Zbl 0132.35606 · doi:10.2307/2313117
[5] Krishnapur, M. and Peres, Y. (2004). Recurrent graphs where two independent random walks collide finitely often. Electron. Commun. Probab. 9 72-81 (electronic). · Zbl 1060.60044 · doi:10.1214/ECP.v9-1111
[6] Lyons, R. and Peres, Y. (2008). Probability on trees and networks. Unpublished manuscript. Current version available at .
[7] Rudin, W. (1991). Functional Analysis , 2nd ed. McGraw-Hill, New York. · Zbl 0867.46001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.