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

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.

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.

DOI: 10.1214/12-AIHP481
Classification: 60J10, 60J35, 60J80, 05C81
Keywords: 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 = {}
AU  - Barlow, Martin T.
AU  - Peres, Yuval
AU  - Sousi, Perla
TI  - Collisions of random walks
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2012
SP  - 922
EP  - 946
VL  - 48
IS  - 4
PB  - Gauthier-Villars
UR  -
DO  - 10.1214/12-AIHP481
LA  - en
ID  - AIHPB_2012__48_4_922_0
ER  - 
%0 Journal Article
%A Barlow, Martin T.
%A Peres, Yuval
%A Sousi, Perla
%T Collisions of random walks
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2012
%P 922-946
%V 48
%N 4
%I Gauthier-Villars
%R 10.1214/12-AIHP481
%G en
%F AIHPB_2012__48_4_922_0
Barlow, Martin T.; Peres, Yuval; Sousi, Perla. Collisions of random walks. Annales de l'I.H.P. Probabilités et statistiques, Volume 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 | Zbl

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

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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

[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 | Zbl

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

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

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

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

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

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

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

Cited by Sources: