Asymptotics of the transition probabilities of the simple random walk on self-similar graphs
HTML articles powered by AMS MathViewer
- by Bernhard Krön and Elmar Teufl PDF
- Trans. Amer. Math. Soc. 356 (2004), 393-414 Request permission
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 Sierpiński 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
- S. Alexander and R. Orbach, Density of states on fractals: fractons, J. Physique Lettres 43 (1982), L625–L631.
- Martin T. Barlow, Diffusions on fractals, Lectures on probability theory and statistics (Saint-Flour, 1995) Lecture Notes in Math., vol. 1690, Springer, Berlin, 1998, pp. 1–121. MR 1668115, DOI 10.1007/BFb0092537
- Martin T. Barlow and Edwin A. Perkins, Brownian motion on the Sierpiński gasket, Probab. Theory Related Fields 79 (1988), no. 4, 543–623. MR 966175, DOI 10.1007/BF00318785
- Alan F. Beardon, Iteration of rational functions, Graduate Texts in Mathematics, vol. 132, Springer-Verlag, New York, 1991. Complex analytic dynamical systems. MR 1128089, DOI 10.1007/978-1-4612-4422-6
- Gerard Ben Arous and Takashi Kumagai, Large deviations of Brownian motion on the Sierpinski gasket, Stochastic Process. Appl. 85 (2000), no. 2, 225–235. MR 1731023, DOI 10.1016/S0304-4149(99)00075-7
- Pierre Brémaud, Markov chains, Texts in Applied Mathematics, vol. 31, Springer-Verlag, New York, 1999. Gibbs fields, Monte Carlo simulation, and queues. MR 1689633, DOI 10.1007/978-1-4757-3124-8
- N. G. de Bruijn, An asymptotic problem on iterated functions, Nederl. Akad. Wetensch. Indag. Math. 41 (1979), no. 2, 105–110. MR 535559, DOI 10.1016/1385-7258(79)90015-5
- Philippe Flajolet and Andrew Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), no. 2, 216–240. MR 1039294, DOI 10.1137/0403019
- M. Fukushima and T. Shima, On a spectral analysis for the Sierpiński gasket, Potential Anal. 1 (1992), no. 1, 1–35. MR 1245223, DOI 10.1007/BF00249784
- I. P. Goulden and D. M. Jackson, Combinatorial enumeration, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. With a foreword by Gian-Carlo Rota. MR 702512
- Peter J. Grabner, Functional iterations and stopping times for Brownian motion on the Sierpiński gasket, Mathematika 44 (1997), no. 2, 374–400. MR 1600494, DOI 10.1112/S0025579300012699
- Peter J. Grabner and Wolfgang Woess, Functional iterations and periodic oscillations for simple random walk on the Sierpiński graph, Stochastic Process. Appl. 69 (1997), no. 1, 127–138. MR 1464178, DOI 10.1016/S0304-4149(97)00033-1
- Clemens Inninger, Rational iteration, Schriften der Johannes-Keppler-Universität Linz. Reihe C: Technik und Naturwissenschaften [Publications of the Johannes-Keppler University Linz. Series C: Technology and Natural Sciences], vol. 35, Universitätsverlag Rudolf Trauner, Linz, 2001. Characterizations of functions with empty Fatou set, Jordan arc Julia sets and with real Julia sets; Dissertation, University of Linz, Linz, 2001. MR 1826372
- Owen Dafydd Jones, Transition probabilities for the simple random walk on the Sierpiński graph, Stochastic Process. Appl. 61 (1996), no. 1, 45–69. MR 1378848, DOI 10.1016/0304-4149(95)00074-7
- Jun Kigami, Harmonic calculus on p.c.f. self-similar sets, Trans. Amer. Math. Soc. 335 (1993), no. 2, 721–755. MR 1076617, DOI 10.1090/S0002-9947-1993-1076617-1
- Jun Kigami, Analysis on fractals, Cambridge Tracts in Mathematics, vol. 143, Cambridge University Press, Cambridge, 2001. MR 1840042, DOI 10.1017/CBO9780511470943
- Jun Kigami and Michel 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 1243717, DOI 10.1007/BF02097233
- 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.
- —, Growth of self-similar graphs, preprint, 2002.
- Tom Lindstrøm, Brownian motion on nested fractals, Mem. Amer. Math. Soc. 83 (1990), no. 420, iv+128. MR 988082, DOI 10.1090/memo/0420
- Leonid Malozemov and Alexander Teplyaev, Pure point spectrum of the Laplacians on fractal graphs, J. Funct. Anal. 129 (1995), no. 2, 390–405. MR 1327184, DOI 10.1006/jfan.1995.1056
- —, Self-similarity, operators and dynamics, preprint, 2001.
- A. M. Odlyzko, Periodic oscillations of coefficients of power series that satisfy functional equations, Adv. in Math. 44 (1982), no. 2, 180–205. MR 658540, DOI 10.1016/0001-8708(82)90005-6
- R. Rammal, Random walk statistics on fractal structures, J. Statist. Phys. 36 (1984), no. 5-6, 547–560. MR 773968, DOI 10.1007/BF01012921
- R. Rammal and G. Toulouse, Random walks on fractal structures and percolation clusters, J. Physique Lettres 44 (1983), L13–L22.
- C. Sabot, Spectral properties of hierarchical lattices and iteration of rational maps, Mem. Soc. Math. Fr. (N.S.) 92 (2003), vi + 104pp.
- E. Teufl, The average displacement of the simple random walk on the Sierpiński graph, Combin. Probab. Comput. 12 (2003), 203–222.
- Wolfgang Woess, Random walks on infinite graphs and groups, Cambridge Tracts in Mathematics, vol. 138, Cambridge University Press, Cambridge, 2000. MR 1743100, DOI 10.1017/CBO9780511470967
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
- Email: bernhard.kroen@univie.ac.at
- Elmar Teufl
- Affiliation: Department of Mathematics C, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria
- Email: elmar.teufl@tugraz.at
- 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 - © Copyright 2003 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 356 (2004), 393-414
- MSC (2000): Primary 60J10; Secondary 05A15, 30D05
- DOI: https://doi.org/10.1090/S0002-9947-03-03352-X
- MathSciNet review: 2020038