Collisions of random walks

Martin T. Barlow; Yuval Peres; Perla Sousi

Annales de l'I.H.P. Probabilités et statistiques (2012)

  • Volume: 48, Issue: 4, page 922-946
  • ISSN: 0246-0203

Abstract

top
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 d ≥ 19 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.

How to cite

top

Barlow, Martin T., Peres, Yuval, and Sousi, Perla. "Collisions of random walks." Annales de l'I.H.P. Probabilités et statistiques 48.4 (2012): 922-946. <http://eudml.org/doc/272095>.

@article{Barlow2012,
abstract = {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.},
author = {Barlow, Martin T., Peres, Yuval, Sousi, Perla},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {random walks; collisions; transition probability; branching processes; random walk; collision; branching process},
language = {eng},
number = {4},
pages = {922-946},
publisher = {Gauthier-Villars},
title = {Collisions of random walks},
url = {http://eudml.org/doc/272095},
volume = {48},
year = {2012},
}

TY - JOUR
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
PB - Gauthier-Villars
VL - 48
IS - 4
SP - 922
EP - 946
AB - 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.
LA - eng
KW - random walks; collisions; transition probability; branching processes; random walk; collision; branching process
UR - http://eudml.org/doc/272095
ER -

References

top
  1. [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. Zbl1083.60060MR2177164
  2. [2] M. T. Barlow and T. Kumagai. Random walk on the incipient infinite cluster on trees. Illinois J. Math.50 (2006) 33–65. Zbl1110.60090MR2247823
  3. [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. Zbl1223.05285MR2802298
  4. [4] I. Benjamini, O. Gurel-Gurevich and R. Lyons. Recurrence of random walk traces. Ann. Probab.35 (2007) 732–738. Zbl1118.60059
  5. [5] I. Benjamini and G. Kozma. A resistance bound via an isoperimetric inequality. Combinatorica25 (2005) 645–650. Zbl1098.60075MR2199429
  6. [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. Zbl1234.60093MR2857447
  7. [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. Zbl0127.35204MR164375
  8. [8] X. Chen and D. Chen. Two random walks on the open cluster of ℤ 2 meet infinitely often. Preprint, 2009. Zbl1216.05147
  9. [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. Zbl1154.60301MR2453913
  10. [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. Zbl1191.60121
  11. [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. Zbl1135.60060MR2407556
  12. [12] G. Grimmett. Percolation, 2nd edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 321. Springer, Berlin, 1999. Zbl0926.60004MR1707339
  13. [13] H. Kesten. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist.22 (1986) 425–487. Zbl0632.60106MR871905
  14. [14] T. Konstantopoulos. Ballot theorems revisited. Statist. Probab. Letters24 (1995) 331–338. Zbl0832.60017MR1353891
  15. [15] G. Kozma and A. Nachmias. The Alexander–Orbach conjecture holds in high dimensions. Invent. Math.178 (2009) 635–654. Zbl1180.82094MR2551766
  16. [16] M. Krishnapur and Y. Peres. Recurrent graphs where two independent random walks collide infinitely often. Electron. Commun. Probab.9 (2004) 72–81. Zbl1060.60044MR2081461
  17. [17] D. A. Levin, Y. Peres and E. Wilmer. Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI, 2008. Zbl1160.60001MR2466937
  18. [18] T. Lindvall and L. C. G. Rogers. Coupling of multidimensional diffusions by reflection. Ann. Probab.14 (1986) 860–872. Zbl0593.60076MR841588

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.