Abstract

Regarding his 1920 paper proving recurrence of random walks in Z2, Polya wrote that his motivation was to determine whether 2 independent random walks in Z2 meet infinitely often. Of course, in this case, the problem reduces to the recurrence of a single random walk in Z2, by taking differences. Perhaps surprisingly, however, there exist graphs G where a single random walk is recurrent, yet G has the finite collision property : two independent random walks in G collide only finitely many times almost surely. Some examples were constructed by Krishnapur and Peres (2004), who asked whether critical Galton-Watson trees conditioned on nonextinction also have this property. In this talk I will answer this question as part of a systematic study of the finite collision property. In particular, for two classes of graphs, wedge combs and spherically symmetric trees, we exhibit a phase transition for the finite collision property when growth parameters are varied. I will state the main theorems and give some ideas of the proofs. This is joint work with Martin Barlow and Yuval Peres.