Recurrent Graphs where Two Independent Random Walks Collide Finitely Often

Manjunath Krishnapur (University of California at Berkeley, USA)
Yuval Peres (University of California at Berkeley, USA)

Abstract


We present a class of graphs where simple random walk is recurrent, yet two independent walkers meet only finitely many times almost surely. In particular, the comb lattice, obtained from $Z^2$ by removing all horizontal edges off the $x$-axis, has this property. We also conjecture that the same property holds for some other graphs, including the incipient infinite cluster for critical percolation in $Z^2$.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 72-81

Publication Date: July 30, 2004

DOI: 10.1214/ECP.v9-1111

References

  1. Erdõs, P. and Taylor, S. J. Some problems concerning the structure of random walk paths. Acta Math. Acad. Sci. Hungar. 11 (1960), 137-162. Math. Review 0121870
  2. Feller, W. An introduction to probability theory and its applications. Vol. I, (1978) Wiley. Math. Review 0228020
  3. Kesten, H. The incipient infinite cluster in two-dimensional percolation. Probab. Theory and Related Fields. 73 (1968) 369-394. Math. Review 89a:94023
  4. Kesten, H. Subdiffusive behaviour of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist., 22 (1986) 425-487. Math. Review 89a:94023
  5. Liggett, T. M. A characterization of the invariant measures for an infinite particle system with interactions II. Trans. Amer. Math. Soc., 198, (1974) 201-213 Math. Review 89a:94023
  6. Lyons, R. with Peres, Y. Probability on Trees. Book in preparation; draft available at http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html
  7. Pólya, G., George Pólya: Collected Papers volume IV, 582-585. The MIT Press, Cambridge, Massachusetts. Math. Review 89a:94023
  8. Woess, W. (2000). Random walks on infinite graphs and groups. Cambridge Tracts in Mathematics 138, Cambridge University Press. Math. Review 89a:94023
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.