Transactions of the American Mathematical Society

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

Author(s): Bernhard Krön; Elmar Teufl
Journal: Trans. Amer. Math. Soc. 356 (2004), 393-414.
MSC (2000): Primary 60J10; Secondary 05A15, 30D05
Posted: August 21, 2003
Retrieve article in: PDF DVI PostScript

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

of the boundary of $\hat C$ . It is proved that the expected number of returns to

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

-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

-step transition probabilities.

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

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

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

DOI: 10.1090/S0002-9947-03-03352-X
PII: S 0002-9947(03)03352-X
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
Posted: 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 of article: Copyright 2003, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS