Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Asymptotics of the transition probabilities of the simple random walk on self-similar graphs

Authors: Bernhard Krön and Elmar Teufl
Journal: Trans. Amer. Math. Soc. 356 (2004), 393-414
MSC (2000): Primary 60J10; Secondary 05A15, 30D05
Published electronically: August 21, 2003
MathSciNet review: 2020038
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown explicitly how self-similar graphs can be obtained as `blow-up' constructions of finite cell graphs $\hat C$. This yields a larger family of graphs than the graphs obtained by discretising continuous self-similar fractals.

For a class of symmetrically self-similar graphs we study the simple random walk on a cell graph $\hat C$, starting at a vertex $v$ of the boundary of $\hat C$. It is proved that the expected number of returns to $v$before hitting another vertex in the boundary coincides with the resistance scaling factor.

Using techniques from complex rational iteration and singularity analysis for Green functions, we compute the asymptotic behaviour of the $n$-step transition probabilities of the simple random walk on the whole graph. The results of Grabner and Woess for the Sierpinski graph are generalised to the class of symmetrically self-similar graphs, and at the same time the error term of the asymptotic expression is improved. Finally, we present a criterion for the occurrence of oscillating phenomena of the $n$-step transition probabilities.

References [Enhancements On Off] (What's this?)

  • 1. S. Alexander and R. Orbach, Density of states on fractals: fractons, J. Physique Lettres 43 (1982), L625-L631.
  • 2. M. T. Barlow, Diffusions on fractals, Lectures on probability theory and statistics (Saint-Flour, 1995), Springer, Berlin, 1998, pp. 1-121. MR 2000a:60148
  • 3. M. T. Barlow and E. A. Perkins, Brownian motion on the Sierpinski gasket, Probab. Theory Related Fields 79 (1988), no. 4, 543-623. MR 89g:60241
  • 4. A. F. Beardon, Iteration of rational functions, Springer-Verlag, New York, 1991. MR 92j:30026
  • 5. G. Ben Arous and T. Kumagai, Large deviations of Brownian motion on the Sierpinski gasket, Stochastic Process. Appl. 85 (2000), no. 2, 225-235. MR 2000k:60160
  • 6. P. Brémaud, Markov chains, Springer-Verlag, New York, 1999. MR 2000k:60137
  • 7. N. G. de Bruijn, An asymptotic problem on iterated functions, Nederl. Akad. Wetensch. Indag. Math. 41 (1979), no. 2, 105-110. MR 80j:41049
  • 8. P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), no. 2, 216-240. MR 90m:05012
  • 9. M. Fukushima and T. Shima, On a spectral analysis for the Sierpinski gasket, Potential Anal. 1 (1992), no. 1, 1-35. MR 95b:31009
  • 10. I. P. Goulden and D. M. Jackson, Combinatorial enumeration, John Wiley & Sons, New York, 1983. MR 84m:05002
  • 11. P. J. Grabner, Functional iterations and stopping times for Brownian motion on the Sierpinski gasket, Mathematika 44 (1997), no. 2, 374-400. MR 99b:60128
  • 12. P. J. Grabner and W. Woess, Functional iterations and periodic oscillations for simple random walk on the Sierpinski graph, Stochastic Process. Appl. 69 (1997), no. 1, 127-138. MR 98h:60104
  • 13. C. Inninger, Rational iteration, Universitätsverlag Rudolf Trauner, Linz, 2001, Dissertation, University of Linz, 2001. MR 2002b:37057
  • 14. O. D. Jones, Transition probabilities for the simple random walk on the Sierpinski graph, Stochastic Process. Appl. 61 (1996), no. 1, 45-69. MR 97b:60115
  • 15. J. Kigami, Harmonic calculus on p.c.f. self-similar sets, Trans. Amer. Math. Soc. 335 (1993), no. 2, 721-755. MR 93d:39008
  • 16. -, Analysis on fractals, Cambridge Univ. Press, Cambridge, 2001. MR 2002c:28015
  • 17. J. Kigami and M. L. Lapidus, Weyl's problem for the spectral distribution of Laplacians on p.c.f. self-similar fractals, Comm. Math. Phys. 158 (1993), no. 1, 93-125. MR 94m:58225
  • 18. B. Krön, Green functions on self-similar graphs and bounds for the spectrum of the Laplacian, Ann. Inst. Fourier 52 (2002), no. 6, 1875-1900.
  • 19. -, Growth of self-similar graphs, preprint, 2002.
  • 20. T. Lindstrøm, Brownian motion on nested fractals, Mem. Amer. Math. Soc. 83 (1990), no. 420, iv+128. MR 90k:60157
  • 21. L. Malozemov and A. Teplyaev, Pure point spectrum of the Laplacians on fractal graphs, J. Funct. Anal. 129 (1995), no. 2, 390-405. MR 96e:60114
  • 22. -, Self-similarity, operators and dynamics, preprint, 2001.
  • 23. A. M. Odlyzko, Periodic oscillations of coefficients of power series that satisfy functional equations, Adv. in Math. 44 (1982), no. 2, 180-205. MR 84a:30042
  • 24. R. Rammal, Random walk statistics on fractal structures, J. Statist. Phys. 36 (1984), no. 5-6, 547-560. MR 85m:82118
  • 25. R. Rammal and G. Toulouse, Random walks on fractal structures and percolation clusters, J. Physique Lettres 44 (1983), L13-L22.
  • 26. C. Sabot, Spectral properties of hierarchical lattices and iteration of rational maps, Mem. Soc. Math. Fr. (N.S.) 92 (2003), vi + 104pp.
  • 27. E. Teufl, The average displacement of the simple random walk on the Sierpinski graph, Combin. Probab. Comput. 12 (2003), 203-222.
  • 28. W. Woess, Random walks on infinite graphs and groups, Cambridge University Press, Cambridge, 2000. MR 2001k:60006

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 60J10, 05A15, 30D05

Retrieve articles in all journals with MSC (2000): 60J10, 05A15, 30D05

Additional Information

Bernhard Krön
Affiliation: Erwin Schrödinger Institute (ESI) Vienna, Boltzmanngasse 9, 1090 Wien, Austria
Address at time of publication: Department of Mathematics, University of Vienna, Strudlhofgasse 4, 1090 Wien, Austria

Elmar Teufl
Affiliation: Department of Mathematics C, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria

Keywords: Self-similar graphs, simple random walk, transition probability
Received by editor(s): August 19, 2002
Received by editor(s) in revised form: March 9, 2003
Published electronically: August 21, 2003
Additional Notes: The first author was supported by the project P14379-MAT of the Austrian Science Fund (FWF)
The second author was supported by the START-project Y96-MAT of the FWF
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society