Difference equations, isoperimetric inequality and transience of certain random walks

Dodziuk, Jozef

doi:10.1090/S0002-9947-1984-0743744-X

Difference equations, isoperimetric inequality and transience of certain random walks
HTML articles powered by AMS MathViewer

by Jozef Dodziuk PDF

Trans. Amer. Math. Soc. 284 (1984), 787-794 Request permission

Abstract:

The difference Laplacian on a square lattice in ${{\mathbf {R}}^n}$ has been studied by many authors. In this paper an analogous difference operator is studied for an arbitrary graph. It is shown that many properties of the Laplacian in the continuous setting (e.g. the maximum principle, the Harnack inequality, and Cheeger’s bound for the lowest eigenvalue) hold for this difference operator. The difference Laplacian governs the random walk on a graph, just as the Laplace operator governs the Brownian motion. As an application of the theory of the difference Laplacian, it is shown that the random walk on a class of graphs is transient.

References

Lars V. Ahlfors and Leo Sario, Riemann surfaces, Princeton Mathematical Series, No. 26, Princeton University Press, Princeton, N.J., 1960. MR 0114911

A lower bound for the lowest eigenvalue of the Laplacian

Über die partiellen Differenzengleichungen der mathematischen Physik

100

David R. DeBaun, $L^{2}$-cohomology of noncompact surfaces, Trans. Amer. Math. Soc. 284 (1984), no. 2, 543–565. MR 743732, DOI 10.1090/S0002-9947-1984-0743732-3
Jozef Dodziuk, Every covering of a compact Riemann surface of genus greater than one carries a nontrivial $L^{2}$ harmonic differential, Acta Math. 152 (1984), no. 1-2, 49–56. MR 736211, DOI 10.1007/BF02392190
R. J. Duffin, Discrete potential theory, Duke Math. J. 20 (1953), 233–251. MR 70031
John G. Kemeny, J. Laurie Snell, and Anthony W. Knapp, Denumerable Markov chains, 2nd ed., Graduate Texts in Mathematics, No. 40, Springer-Verlag, New York-Heidelberg-Berlin, 1976. With a chapter on Markov random fields, by David Griffeath. MR 0407981