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)

Request Permissions   Purchase Content 


Volume growth and stochastic completeness of graphs

Author: Matthew Folz
Journal: Trans. Amer. Math. Soc. 366 (2014), 2089-2119
MSC (2010): Primary 60G50; Secondary 60J60, 31C25
Published electronically: September 4, 2013
MathSciNet review: 3152724
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given the variable-speed random walk on a weighted graph and a metric adapted to the structure of the random walk, we construct a Brownian motion on a closely related metric graph which behaves similarly to the VSRW and for which the associated intrinsic metric has certain desirable properties. Jump probabilities and moments of jump times for Brownian motion on metric graphs with varying edge lengths, jump conductances, and edge densities are computed. We use these results together with a theorem of Sturm for stochastic completeness, or non-explosiveness, on local Dirichlet spaces to prove sharp volume growth criteria in adapted metrics for stochastic completeness of graphs.

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

  • 1. M. T. Barlow. Random Walks on Graphs. Unpublished manuscript.
  • 2. M. T. Barlow. Random walks on supercritical percolation clusters, Ann. Probab. 32 (2004), 3024-3084. MR 2094438 (2006e:60146)
  • 3. M. T. Barlow, R. F. Bass. Stability of parabolic Harnack inequalities. Trans. Am. Math. Soc. 356 (2004), 1501-1533. MR 2034316 (2005e:60167)
  • 4. M. T. Barlow, J.-D. Deuschel. Invariance principle for the random conductance model with unbounded conductances. Ann. Probab. 38 (2010), 234-276. MR 2599199 (2011c:60329)
  • 5. M. T. Barlow, J. Pitman, M. Yor. On Walsh's Brownian motions. Sem. Prob. XXIV, 188-193. Lect. Notes Math. 1426, Springer, Berlin, 1990.
  • 6. J. R. Baxter, R. V. Chacon. The equivalence of diffusions on networks to Brownian motion. Contemp. Math. 26 (1984), 33-47. MR 737386 (85h:58179)
  • 7. B. M. Brown. A general three-series theorem. Proc. Am. Math. Soc. 28 (1971), 573-577. MR 0277020 (43:2757)
  • 8. E. B. Davies. Analysis on graphs and noncommutative geometry, J. Funct. Anal. 111 (1993), 398-430. MR 1203460 (93m:58110)
  • 9. J. L. Doob. Stochastic Processes. Wiley-Interscience, New York, 1990. MR 1038526 (91d:60002)
  • 10. M. Folz. Gaussian upper bounds for heat kernels of continuous time simple random walks on graphs. Elec. J. Prob. 62 (2011), 1693-1722. MR 2835251
  • 11. M. Folz. Volume growth and spectrum for general graph Laplacians. To appear in Math. Z. (currently available in its final form at
  • 12. R. L. Frank, D. Lenz, D. Wingert. Intrinsic metrics for non-local symmetric Dirichlet forms and applications to spectral theory. To appear in J. Funct. Anal..
  • 13. D. Gilat. On the Nonexistence of a Three Series Condition for Series of Nonindependent Random Variables. Ann. Math. Stat. 42 (1971), 409.
  • 14. A. Grigor'yan. On stochastically complete manifolds. Soviet Math. Dokl. 34 (1987), 310-313. MR 860324 (88a:58209)
  • 15. A. Grigor'yan. Analytic and geometric background of recurrence and non-explosion of the Brownian motion on Riemannian manifolds. Bull. Am. Math. Soc. 36 (1999), 135-249. MR 1659871 (99k:58195)
  • 16. A. Grigor'yan. Gaussian upper bounds for the heat kernel on arbitrary manifolds, J. Diff. Geom. 45 (1997), 33-52. MR 1443330 (98g:58167)
  • 17. A. Grigor'yan, X. Huang, J. Masamune. On stochastic completeness of jump processes, Math. Z. 271 (2012), no. 3-4, 1211-1239. MR 2945605
  • 18. S. Haeseler. Heat kernel estimates and related inequalities on metric graphs. Preprint.
  • 19. X. Huang. Stochastic incompleteness for graphs and weak Omori-Yau maximum principle. J. Math. Anal. Appl. 379 (2011), 764-782. MR 2784357 (2012c:60194)
  • 20. X. Huang. On uniqueness class for a heat equation on graphs, J. Math. Anal. Appl. 393 (2012), no. 2, 377-388. MR 2921681
  • 21. M. Keller, D. Lenz. Dirichlet forms and stochastic completeness of graphs and subgraphs, J. Reine. Angew. Math. 666 (2012), 189-223. MR 2920886
  • 22. M. Keller, D. Lenz, R. Wojciechowski. Volume growth, spectrum, and stochastic completeness of infinite graphs. Math. Z. 274 (2013), no. 3-4, 905-932. MR 3078252
  • 23. V. Kostrykin, J. Potthoff, R. Schrader. Brownian motion on metric graphs, J. Math. Phys. 53 (2012), no. 9, 095206, 36 pp. MR 2905788
  • 24. V. Kostrykin, J. Potthoff, R. Schrader. Construction of the paths of Brownian motion on star graphs I, Commun. Stoch. Anal. 6 (2012), no. 2, 223-245. MR 2927702
  • 25. V. Kostrykin, J. Potthoff, R. Schrader. Construction of the paths of Brownian motion on star graphs II, Commun. Stoch. Anal. 6 (2012), no. 2, 247-261. MR 2927703
  • 26. G. Zaimi. Assigning positive edge weights to a graph so that the weight incident to each vertex is 1. (2011).
  • 27. J. Masamune, T. Uemura. Conservation property of symmetric jump processes. Ann. I. H. Poincaré-PR. 47 (2011), 650-662. MR 2841069 (2012f:60291)
  • 28. L. C. G. Rogers. Ito excursion theory via resolvents. Z. Wahr. 63 (1983), 237-255. MR 701528 (85j:60143a)
  • 29. T. S. Salisbury. Construction of right processes from excursions. Z. Wahr. 73 (1986), 351-367. MR 859838 (88g:60177)
  • 30. K.-T. Sturm. Analysis on local Dirichlet spaces I. Recurrence, conservativeness and $ L^p$-Liouville properties. J. Reine. Angew. Math. 456 (1994), 173-196. MR 1301456 (95i:31003)
  • 31. N. Th. Varopoulos. Long range estimates for Markov Chains. Bull. Sci. Math. 109 (1985), 225-252. MR 822826 (87j:60100)
  • 32. J. Walsh. A diffusion with a discontinuous local time. Asterisque 52-53 (1978), 37-45.
  • 33. A. Weber. Analysis of the physical Laplacian and the heat flow on a locally finite graph, J. Math. Anal. Appl. 370 (2010), 146-158. MR 2651136 (2011f:35341)
  • 34. R. Wojciechowski. Stochastically incomplete manifolds and graphs, in Random walks, boundaries and spectra, 163-179, Progr. Probab., 64 Birkhäuser/Springer Basel AG, Basel. MR 3051698

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 60G50, 60J60, 31C25

Retrieve articles in all journals with MSC (2010): 60G50, 60J60, 31C25

Additional Information

Matthew Folz
Affiliation: Department of Mathematics, The University of British Columbia, 1984 Mathematics Road, Vancouver, British Columbia, Canada V6T 1Z2

Keywords: Random walks, stochastic completeness, volume growth, intrinsic metrics, Brownian motion on metric graphs, local Dirichlet spaces
Received by editor(s): March 16, 2012
Received by editor(s) in revised form: June 20, 2012, and August 2, 2012
Published electronically: September 4, 2013
Additional Notes: This research was supported by an NSERC Alexander Graham Bell Canada Graduate Scholarship
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society