Collisions of random walks
Annales de l'I.H.P. Probabilités et statistiques, Tome 48 (2012) no. 4, pp. 922-946.

Un graphe récurrent G a la propriété de collisions infinies si deux marches aléatoires indépendantes dans G, issues du même état, se rencontrent infiniment souvent presque sûrement. Nous donnons un critère simple à l’aide de fonctions de Green qui implique cette propriété, et nous l’utilisons pour prouver que la propriété de collisions infinies a lieu dans les cas suivants: un arbre de Galton-Watson critique avec variance finie conditionné à survivre, l’amas de percolation critique conditionné à être infini dans d avec d19 et l’arbre couvrant uniforme dans 2 . Pour le graphe en forme de peigne aléatoire avec queues polynomiales et les arbres à symétrie sphérique, nous déterminons précisément la région critique dans l’espace des phases pour les collisions infinies.

A recurrent graph G has the infinite collision property if two independent random walks on G, started at the same point, collide infinitely often a.s. We give a simple criterion in terms of Green functions for a graph to have this property, and use it to prove that a critical Galton-Watson tree with finite variance conditioned to survive, the incipient infinite cluster in d with d19 and the uniform spanning tree in 2 all have the infinite collision property. For power-law combs and spherically symmetric trees, we determine precisely the phase boundary for the infinite collision property.

Classification : 60J10,  60J35,  60J80,  05C81
Mots clés : random walks, collisions, transition probability, branching processes
     author = {Barlow, Martin T. and Peres, Yuval and Sousi, Perla},
     title = {Collisions of random walks},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     pages = {922--946},
     publisher = {Gauthier-Villars},
     volume = {48},
     number = {4},
     year = {2012},
     doi = {10.1214/12-AIHP481},
     mrnumber = {3052399},
     language = {en},
     url = {}
Barlow, Martin T.; Peres, Yuval; Sousi, Perla. Collisions of random walks. Annales de l'I.H.P. Probabilités et statistiques, Tome 48 (2012) no. 4, pp. 922-946. doi : 10.1214/12-AIHP481.

[1] M. T. Barlow, T. Coulhon and T. Kumagai. Characterization of sub-Gaussian heat kernel estimates on strongly recurrent graphs. Comm. Pure Appl. Math. LVIII (2005) 1642-1677. | MR 2177164 | Zbl 1083.60060

[2] M. T. Barlow and T. Kumagai. Random walk on the incipient infinite cluster on trees. Illinois J. Math. 50 (2006) 33-65. | MR 2247823 | Zbl 1110.60090

[3] M. T. Barlow and R. Masson. Spectral dimension and random walks on the two dimensional uniform spanning tree. Comm. Math. Phys. 305 (2011) 23-57. | MR 2802298 | Zbl 1223.05285

[4] I. Benjamini, O. Gurel-Gurevich and R. Lyons. Recurrence of random walk traces. Ann. Probab. 35 (2007) 732-738. | Zbl 1118.60059

[5] I. Benjamini and G. Kozma. A resistance bound via an isoperimetric inequality. Combinatorica 25 (2005) 645-650. | MR 2199429 | Zbl 1098.60075

[6] D. Bertacchi, N. Lanchier and F. Zucca. Contact and voter processes on the infinite percolation cluster as models of host-symbiont interactions. Ann. Appl. Probab. 21 (2011) 1215-1252. | MR 2857447 | Zbl 1234.60093

[7] D. Blackwell and D. Freedman. The tail σ-field of a Markov chain and a theorem of Orey. Ann. Math. Statist. 35 (1964) 1291-1295. | MR 164375 | Zbl 0127.35204

[8] X. Chen and D. Chen. Two random walks on the open cluster of 2 meet infinitely often. Preprint, 2009. | Zbl 1216.05147

[9] D. Chen, B. Wei and F. Zhang. A note on the finite collision property of random walks. Statist. Probab. Lett. 78 (2008) 1742-1747. | MR 2453913 | Zbl 1154.60301

[10] D. Croydon and T. Kumagai. Random walks on Galton-Watson trees with infinite variance offspring distribution conditioned to survive. Electron. J. Probab. 13 (2008) 1419-1441. | Zbl 1191.60121

[11] I. Fujii and T. Kumagai. Heat kernel estimates on the incipient infinite cluster for critical branching processes. In Proceedings of RIMS Workshop on Stochastic Analysis and Applications 85-95. RIMS Kokyuroku Bessatsu B6. Res. Inst. Math. Sci. (RIMS), Kyoto, 2008. | MR 2407556 | Zbl 1135.60060

[12] G. Grimmett. Percolation, 2nd edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 321. Springer, Berlin, 1999. | MR 1707339

[13] H. Kesten. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986) 425-487. | Numdam | MR 871905 | Zbl 0632.60106

[14] T. Konstantopoulos. Ballot theorems revisited. Statist. Probab. Letters 24 (1995) 331-338. | MR 1353891 | Zbl 0832.60017

[15] G. Kozma and A. Nachmias. The Alexander-Orbach conjecture holds in high dimensions. Invent. Math. 178 (2009) 635-654. | MR 2551766 | Zbl 1180.82094

[16] M. Krishnapur and Y. Peres. Recurrent graphs where two independent random walks collide infinitely often. Electron. Commun. Probab. 9 (2004) 72-81. | MR 2081461 | Zbl 1060.60044

[17] D. A. Levin, Y. Peres and E. Wilmer. Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI, 2008. | MR 2466937 | Zbl 1160.60001

[18] T. Lindvall and L. C. G. Rogers. Coupling of multidimensional diffusions by reflection. Ann. Probab. 14 (1986) 860-872. | MR 841588 | Zbl 0593.60076