RANDOM WALKS ON INFINITE GRAPHS AND GROUPS

by

Wolfgang WOESS

Cambridge Tracts in Mathematics, Vol. 138,

Cambridge University Press, 334+xi pages , 2000



!!!!! ERRATA !!!!! - The book has now (2007) sold slightly more than 1000 copies, and CUP is preparing a paperback edition. Unfortunatley, the new reproduction techniques are such that I do not get a chance to carry out corrections within the text before reprinting. However, three pages of "errata" will be included at the end of the paperback regarding various misprints and two "true" mistakes. One concerns random walks on lamplighter groups in Section 15, where I chose the wrong (non-symmetric) law (a popular mistake), and the other concerns minimality of (Martin) boundary points of hyperbolic graphs in Section 22. Both could be overcome quite easily.

Here are two links: the first is to the announcement of my book on the website of CUP, and the second is a postscript file containing table of contents, preface, acknowledgements and the bibliography of my book. It has four chapters, subdivided into 28 Sections, most of which have several sub-sections.

Chapter I, "The type problem", starts with Polya's phenomenom of recurrence of simple random walk on the grids of dimensions one and two versus transience in higher dimensions. As one important feature, it aims at giving a quick and accessible tour to Varopoulos' classification of the recurrent groups; subsequently, recurrence is studied in detail for random walks on various types of structures. Chapter II, "The spectral radius", explains the links between exponential decay of transition probabilities, isoperimetric inequalities, amenability, and explains various methods of computation. Chapter III, "The asymptotic behaviour of transition probabilities", displays a wide range of methods from harmonic analysis via Nash inequalities and related functional analytic tools to singularity analysis and complex functions in order to compute explicit asymptotic equivalents of transition probabilities. In my view, one of the highlights is a careful exposition of Lalley's local limit theorem for finite range random walks on free groups. Chapter IV, "An introduction to topological boundary theory", deals with the interplay between positive harmonic functions and compactifications of the state space. The main problems addressed are the Dirichlet problem at infinity, almost sure convergence to the boundary, and the geometric realization of the Martin boundary. Among other, it contains a recent, elegant proof - comunicated to me by M. Babillot - of the Ney-Spitzer theorem for random walks on integer lattices, and an exposition of Ancona's identification of the Martin boundary of Gromov-hyperbolic graphs.

In this book, I have tried to give careful and ordered expositions of results taken from more than 80 research papers, most of which appeared in the last 20 years and previously were not accessible in any monograph. It is interdisciplinary between several Mathematical disciplines: Probability - Graph Theory - Geometric Group Theory - Discrete Geometry - Discrete Potential Theory - Harmonic Analysis and Spectral Theory.

Chapter I. The type problem
1. Basic facts
2. Recurrence and transience of infinite networks
3. Applications to random walks
4. Isoperimetric inequalities
5. Transient subtrees, and the classification of the recurrent quasi-transitive graphs
6. More on recurrence

Chapter II. The spectral radius
7. Superharmonic functions and rho-recurrence
8. The spectral radius, the rate of escape, and generalized lattices
9. Computing the Green function
10. The spectral radius and strong isoperimetric inequalities
11. A lower bound for simple random walks
12. The spectral radius and amenability

Chapter III. The asymptotic behaviour of transition probabilities
13. The local central limit theorem on the grid
14. Growth, isoperimetric inequalities, and the asymptotic type of random walk
15. The asymptotic type of random walks on amenable groups
16. Simple random walks on the Sierpinski graphs
17. Local limit theorems on free products
18. Intermezzo: Cartesian products
19. Free groups and homogeneous trees

Chapter IV. An introduction to topological boundary theory
20. A probabilistic approach to the Dirichlet problem, and a class of compactifications
21. Ends of graphs and the Dirichlet problem
22. Hyperbolic graphs and groups
23. The Dirichlet problem for circle packing graphs
24. The construction of the Martin boundary
25. Generalized lattices, Abelian and nilpotent groups, and graphs with polynomial growth
26. Trees, ends, and free products
27. The Martin boundary of hyperbolic graphs
28. Cartesian products

Here are the link to my homepage http://www.math.tugraz.at/~woess/
and my email address: woess [at] tugraz [dot] at

W. W.



Last modified on October 23, 2007