Random walks on infinite graphs and groups / Wolfgang Woess

The main topic of this book is the interplay between the behaviour of random walks and the properties of their state spaces. Random walks are time-homogeneous Markov chains whose state space is here an infinite graph. An important particular case is a random walk on an infinite group, where the graph is the Cayley graph of an infinite group. Here, the graphs are mostly locally finite and the groups are finitely generated. There is an interplay between properties of the stochastic process and the structure of the state space. For instance, one of the goals is the classification of these finitely generated groups which carry a recurrent random walk. The book contains a wealth of facts on random walks and discusses links with spectral theory, graph theory and discrete potential theory. Each of the four chapters centers around one aspect of the behaviour of random walks, and each of them contains historical notes and references.

Chapter I focusses on recurrence and transience of random walks. It contains facts on recurrence/transience of infinite networks, comparison theorems for random walks on graphs, isoperimetric inequalities, growth function and the classification of recurrent groups, random walks on trees and circlc packings. Chapter II concentrates on the spectral radius, and discusses Green functions, strong isoperimetric inequalities and amenability of groups. Chapter III deals with the asymptotic behaviour of transition probabilities. Among other things, the local central limit theorem, the asymptotic type of a random walk on an amenable group, free products and Cartesian products are considered. Examples are random walks on Sierpiński graphs and random walks on lamplighter groups. Chapter IV is on topological boundary theory, that is connections between the behaviour of the random walk, harmonic functions and compactifications of the state space. In particular, one investigates, for a transient random walk, convergence to the boundary, the Dirichlet problem at infinity and the identification of the Martin boundary. Hyperbolic graphs and groups, graphs with polynomial growth, Abelian and nilpotent groups, free products and Cartesian products are considered.

The book is well-organized, and notations have been handled in a user-friendly way. In spite of the disclaimer in the preface, the book seems to me very suitable for a graduate course or seminar. (Zentralblatt)

Bibliogr. p. 316-330. Index