Random walks and geometry on infinite graphs. (English) Zbl 1063.60063

Coulhon, Thierry

Ambrosio, Luigi (ed.) et al., Lecture notes on analysis in metric spaces. Papers from the international summer school, Trento, Italy, May 1999. Pisa: Scuola Normale Superiore. Appunti dei Corsi Tenuti da Docenti della Scuola, 5-36 (2000).

This is a survey paper on the connection between the geometry of an infinite graph and the behaviour of random walks defined on it. The results are on a discrete analog of the relationship between the geometry of a subelliptic second-order differential operator on a non-compact manifold \(M\) (in particular the notion of isoperimetry associated to such an operator) and the parabolic smoothing effect of the associated heat equation. The main results in the discrete setting consist in estimates for iterates of Markov chain kernels and relations between isoperimetry, decay of random walks and volume growth. Some of the results are stated in terms of Sobolev inequalities, of Nash inequalities, of Faber-Krahn inequalities, of isoperimetric inequalities, of lower bounds on volume growth and of implications between these various inequalities. The author presents in particular some of his own results, for instance results on the \(L^2\) isoperimetric profile, as well as results he obtained with A. Grigor’yan. The continuous and the discrete time estimates are put into parallel. There are special results that hold in the particular case of Cayley graphs of groups.
For the entire collection see [Zbl 1048.00021].

Reviewer: Athanase Papadopoulos (Strasbourg)

MSC:

60G50	Sums of independent random variables; random walks
58J65	Diffusion processes and stochastic analysis on manifolds
58J35	Heat and other parabolic equation methods for PDEs on manifolds

Keywords:

random walks; infinite graphs; heat kernel; discretization; Markov chains; isoperimetric inequality; Sobolev inequalities; Nash inequalities