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

Krön, Bernhard; Teufl, Elmar

doi:10.1090/S0002-9947-03-03352-X

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