Asymptotic Behaviour of the Simple Random Walk on the 2-dimensional Comb

Daniela Bertacchi (Universita` di Milano-Bicocca)

Abstract


We analyze the differences between the horizontal and the vertical component of the simple random walk on the 2-dimensional comb. In particular we evaluate by combinatorial methods the asymptotic behaviour of the expected value of the distance from the origin, the maximal deviation and the maximal span in $n$ steps, proving that for all these quantities the order is $n^{1/4}$ for the horizontal projection and $n^{1/2}$ for the vertical one (the exact constants are determined). Then we rescale the two projections of the random walk dividing by $n^{1/4}$ and $n^{1/2}$ the horizontal and vertical ones, respectively. The limit process is obtained. With similar techniques the walk dimension is determined, showing that the Einstein relation between the fractal, spectral and walk dimensions does not hold on the comb.

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

Pages: 1184-1203

Publication Date: December 7, 2006

DOI: 10.1214/EJP.v11-377

References

  1. Barlow, Martin T.; Bass, Richard F. Random walks on graphical Sierpinski carpets. Random walks and discrete potential theory (Cortona, 1997), 26--55, Sympos. Math., XXXIX, Cambridge Univ. Press, Cambridge, 1999. MR1701339
  2. Bender, Edward A. Asymptotic methods in enumeration. SIAM Rev. 16 (1974), 485--515. MR0376369
  3. Bertacchi, Daniela; Zucca, Fabio Uniform asymptotic estimates of transition probabilities on combs. J. Aust. Math. Soc. 75 (2003), no. 3, 325--353. MR 2015321
  4. Cassi, D.; Regina, S. Random walks on $d$-dimensional comb lattices. Modern Phys. Lett. B 6 (1992), no. 22, 1397--1403. MR 1188155
  5. Cherny, A. S.; Shiryaev, A. N.; Yor, M. Limit behaviour of the "horizontal-vertical" random walk and some extensions of the Donsker-Prokhorov invariance principle. Theory Probab. Appl. 47 (2003), no. 3, 377--394 MR 1975425
  6. Doetsch, Gustav Handbuch der Laplace-Transformation. Band III. Anwendungen der Laplace-Transformation, 2. Abteilung. Birkhäuser Verlag, Basel und Stuttgart, 1956. MR 0084635
  7. Feller, William An introduction to probability theory and its applications. Vol. I. John Wiley & Sons, Inc., New York-London-Sydney 1968 MR 0228020
  8. Feller, William An introduction to probability theory and its applications. Vol. II. John Wiley & Sons, Inc., New York-London-Sydney 1971 MR 0270403
  9. Flajolet, Philippe; Odlyzko, Andrew Singularity analysis of generating functions. SIAM J. Discrete Math. 3 (1990), no. 2, 216--240. MR 1039294
  10. Gerl, Peter Natural spanning trees of $Z^d$ are recurrent. Discrete Math. 61 (1986), no. 2-3, 333--336. MR 0855341
  11. Grigor'yan, Alexander; Telcs, Andras Sub-Gaussian estimates of heat kernels on infinite graphs. Duke Math. J. 109 (2001), no. 3, 451--510. MR 1853353
  12. Jones, Owen Dafydd Transition probabilities for the simple random walk on the Sierpi'nski graph. Stochastic Process. Appl. 61 (1996), no. 1, 45--69. MR 1378848
  13. Karatzas, Ioannis; Shreve, Steven E. Brownian motion and stochastic calculus. Graduate Texts in Mathematics, 113. Springer-Verlag, New York, 1991 MR 1121940
  14. Krishnapur, Manjunath; Peres, Yuval Recurrent graphs where two independent random walks collide finitely often. Electron. Comm. Probab. 9 (2004), 72--81 MR 2081461
  15. Panny, Wolfgang; Prodinger, Helmut The expected height of paths for several notions of height. Studia Sci. Math. Hungar. 20 (1985), no. 1-4, 119--132. MR 0886012
  16. Telcs, András Spectra of graphs and fractal dimensions. I. Probab. Theory Related Fields 85 (1990), no. 4, 489--497. MR 1061940
  17. Telcs, András Spectra of graphs and fractal dimensions. II. J. Theoret. Probab. 8 (1995), no. 1, 77--96. MR 1308671
  18. Telcs, András Local sub-Gaussian estimates on graphs: the strongly recurrent case. Electron. J. Probab. 6 (2001), no. 22 MR 1873299
  19. Weiss, George H.; Havlin, Shlomo Some properties of a random walk on a comb structure. Physica 134A(1986), 474--482. Math. Review number not available.
  20. Whittaker, E. T.; Watson, G. N. A course of modern analysis. An introduction to the general theory of infinite processes and of analytic functions: with an account of the principal transcendental functions. Reprinted Cambridge University Press, New York 1962 MR 0178117
  21. Woess, Wolfgang Random walks on infinite graphs and groups. Cambridge Tracts in Mathematics, 138. Cambridge University Press, Cambridge, 2000. MR 1743100
Bookmark and Share


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