Bounds for the annealed return probability on large finite percolation graphs

Florian Sobieczky (University of Denver)

Abstract


Bounds for the expected return probability of the delayed random walk on finite clusters of an invariant percolation on transitive unimodular graphs are derived. They are particularly suited for the case of critical Bernoulli percolation and the associated heavy-tailed cluster size distributions.  The upper bound relies on the fact that cartesian products of finite graphs with cycles of a certain minimal size are Hamiltonian. For critical Bernoulli bond percolation on the homogeneous tree this bound is sharp. The asymptotic type of the expected return probability for large times $t$ in this case is of order $t^{-3/4}$.

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

Pages: 1-17

Publication Date: September 21, 2012

DOI: 10.1214/EJP.v17-2329

References

  • Aldous, David. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 (1991), no. 2, 228--266. MR1102319
  • S. Alexander, R. Orbach: `Density of states on fractals: ''fractons'' ', J. Physique (Paris) Lett. 43, 625-631, (1982).
  • T. Antunovic, I. Veselic: `Spectral asymptotics of percolation hamiltonians on amenable Cayley graphs', In: Proceedings of OTAMP 2006. Operator Th.: Adv. Appl. (2007).
  • Bandyopadhyay, Antar; Steif, Jeffrey; Timár, Ádám. On the cluster size distribution for percolation on some general graphs. Rev. Mat. Iberoam. 26 (2010), no. 2, 529--550. MR2677006
  • Barlow, Martin T.; Kumagai, Takashi. Random walk on the incipient infinite cluster on trees. Illinois J. Math. 50 (2006), no. 1-4, ISBN: 0-9746986-1-X 33--65 (electronic). MR2247823
  • Batagelj, Vladimir; Pisanski, Tomaž. Hamiltonian cycles in the Cartesian product of a tree and a cycle. Discrete Math. 38 (1982), no. 2-3, 311--312. MR0676545
  • Benjamini, Itai; Lyons, Russell; Peres, Yuval; Schramm, Oded. Critical percolation on any nonamenable group has no infinite clusters. Ann. Probab. 27 (1999), no. 3, 1347--1356. MR1733151
  • A.G. Boshier: `Enlarging properties of graphs', Ph.D. thesis, Royal Holloway and Bedford New College, University of London, (1987).
  • Dimakopoulos, Vassilios V.; Palios, Leonidas; Poulakidas, Athanasios S. On the Hamiltonicity of the Cartesian product. Inform. Process. Lett. 96 (2005), no. 2, 49--53. MR2166269
  • Fisher, Michael E.; Essam, John W. Some cluster size and percolation problems. J. Mathematical Phys. 2 1961 609--619. MR0126305
  • Fontes, L. R. G.; Mathieu, P. On symmetric random walks with random conductances on ${\Bbb Z}^ d$. Probab. Theory Related Fields 134 (2006), no. 4, 565--602. MR2214905
  • Grimmett, Geoffrey. Percolation. Second edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321. Springer-Verlag, Berlin, 1999. xiv+444 pp. ISBN: 3-540-64902-6 MR1707339
  • Grimmett, G. R. On the number of clusters in the percolation model. J. London Math. Soc. (2) 13 (1976), no. 2, 346--350. MR0408045
  • van den Heuvel, J. Hamilton cycles and eigenvalues of graphs. Linear Algebra Appl. 226/228 (1995), 723--730. MR1344594
  • Hughes, Barry D. Random walks and random environments. Vol. 1. Random walks. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1995. xxii+631 pp. ISBN: 0-19-853788-3 MR1341369
  • Kesten, Harry. The critical probability of bond percolation on the square lattice equals ${1\over 2}$. Comm. Math. Phys. 74 (1980), no. 1, 41--59. MR0575895
  • Kesten, Harry. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 4, 425--487. MR0871905
  • Kesten, Harry. Scaling relations for $2$D-percolation. Comm. Math. Phys. 109 (1987), no. 1, 109--156. MR0879034
  • Kirsch, Werner; Müller, Peter. Spectral properties of the Laplacian on bond-percolation graphs. Math. Z. 252 (2006), no. 4, 899--916. MR2206633
  • Kolchin, Valentin F. Random mappings. Translated from the Russian. With a foreword by S. R. S. Varadhan. Translation Series in Mathematics and Engineering. Optimization Software, Inc., Publications Division, New York, 1986. xiv + 207 pp. ISBN: 0-911575-16-2 MR0865130
  • Kozma, Gady; Nachmias, Asaf. The Alexander-Orbach conjecture holds in high dimensions. Invent. Math. 178 (2009), no. 3, 635--654. MR2551766
  • R. Lyons, Y. Peres: `Probability on trees and networks', web-book: http://mypage.iu.edu/simrdlyons/prbtree/prbtree.html.
  • Mohar, Bojan. Isoperimetric numbers of graphs. J. Combin. Theory Ser. B 47 (1989), no. 3, 274--291. MR1026065
  • Müller, Peter; Stollmann, Peter. Spectral asymptotics of the Laplacian on supercritical bond-percolation graphs. J. Funct. Anal. 252 (2007), no. 1, 233--246. MR2357356
  • Norris, J. R. Markov chains. Reprint of 1997 original. Cambridge Series in Statistical and Probabilistic Mathematics, 2. Cambridge University Press, Cambridge, 1998. xvi+237 pp. ISBN: 0-521-48181-3 MR1600720
  • Saloff-Coste, Laurent. Lectures on finite Markov chains. Lectures on probability theory and statistics (Saint-Flour, 1996), 301--413, Lecture Notes in Math., 1665, Springer, Berlin, 1997. MR1490046
  • Sobieczky, Florian. An interlacing technique for spectra of random walks and its application to finite percolation clusters. J. Theoret. Probab. 23 (2010), no. 3, 639--670. MR2679951
  • Woess, Wolfgang. Random walks on infinite graphs and groups. Cambridge Tracts in Mathematics, 138. Cambridge University Press, Cambridge, 2000. xii+334 pp. ISBN: 0-521-55292-3 MR1743100
Bookmark and Share


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