Collisions of random walks

Barlow, Martin T.; Peres, Yuval; Sousi, Perla

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 ${\mathbb{Z}}^d$ avec $d\ge 19$ et l’arbre couvrant uniforme dans ${\mathbb{Z}}^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 ${\mathbb{Z}}^d$ with $d\ge 19$ and the uniform spanning tree in ${\mathbb{Z}}^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

[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 $\sigma$-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 ${\mathbb{Z}}^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