Random Walks and Graph Geometry: a Survey

Thierry Coulhon

Universit de Cergy-Pontoise

Algorithms Seminar

April 12, 1999

[summary by Philippe Robert]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

If G is an infinite graph with bounded degree, this talk analyzes the relations between the asymptotic behavior of a nearest neighbor Markov chain on the graph and some simple geometric characteristics of the graph.

1   Notations

We denote x~ y if x, y G are neighbors. For kN the quantity pk(x,x)=Prx(Mk=x) is the probability that the random walk (Mn) starting from x G returns to x at the k-th step. In the case of the simple random walk p(x,y)=p1(x,y) is 1/deg(x) if y~ x and and 0 otherwise. Let m be a positive function on G such that the relation m(x)p(x,y)=m(y)p(y,x) holds for x,yG. In the case of a finite graph, this is a reversibility assumption: m is the equilibrium measure and the random walk run backward is similar to the original random walk. From an analytic point of view this condition gives an Hilbertian setting to some of the questions considered here. The Lp spaces considered here are with the measure m. The quantity m(x)p(x,y) is denoted by xy, the matrix (xy) is thus symmetrical. In the finite case, xy is the throughput between x and y at equilibrium.

The distance d on the graph between two nodes is the minimum number of edges between them, B(x,r) is the ball of center x G and radius r>0 and V(x,r) is the volume of this ball V(x,r)=y B(x,r) m(y). The boundary of a subset A of G is given by A= {x A; $ yA, x~ y}.
Definition 1   The graph G associated to has the doubling property if there exists C>0 such that for all xG and r>0,
V(x,2r) C V(x,r).     (D)
If c0(A) is the set of functions on G with a finite support in the subset A, for f in c0(G) the length of the gradient is defined by
| f|(x)=



y~ x


for xG. It is easy to verify that the identity || f||22=<(I-P)f,f> holds. The left-hand side is called the Dirichlet form associated to P, in a finite setting this functional is related to the convergence to equilibrium of the Markov chain.

The basic problem considered in this talk is of finding a relation between the asymptotics of (pk(x,x)) as k tends to infinity and the behavior of (V(x,r)) as r gets large.

2   Graphs with a Polynomial Growth

The first result on this subject is the following proposition, due to Varopoulos.
Proposition 1   For D>2, the inequality
pk(x,x) C m(x)k-D/2,     (2)
for all xG and k 1 is equivalent to the Sobolev inequality for all f c0(G): ||f||2D/D-2 C || f||2.
The relation with the geometry of the graph is as follows. The Sobolev inequality implies that V(x,r) c rD for some constant c>0. On the other hand the isoperimetric inequality
x A,yA, x~ A
for all finite subsets A, implies relation (1). With only a condition on the volume growth, we have the following theorem.
Theorem 1   If c rD V(x,r) C rD, for any x G and r>0, there exists c', C' such that
p2k(x,x) C'k
and the bounds are optimal.

3   Upper Bounds: Regular Volume Growth

In this section graphs without prescribed volume assumption are considered.
Definition 2  
pk(x,y) C


  " x,y G, k1.     (UE)
The inequality (DUE) is the above inequality but with x=y.
p2k(x,y) c
   " x G, k1.     (DLE)
The graph G is said to satisfy a Faber-Krahn inequality if there exists a, n>0 such that
inf { || | f|||22;f c0(A), ||f||2=1 }



,     (FK)
for all finite subsets A, x G and r 1/2.
With these definitions one has the following equivalences between the asymptotic behavior of (pk(x,x)) and the geometry of G.
Theorem 2   The following properties are equivalent (i) the Faber-Krahn inequality (FK); (ii) the inequalities (UE) and (D); (iii) the inequalities (DUE) and (D). Each of them implies (DLE).


Coulhon (Thierry). -- Heat kernels on non-compact Riemannian manifolds: a partial survey. In Sminaire de Thorie Spectrale et Gomtrie, No. 15, Anne 1996--1997, pp. 167--187. -- Universit Grenoble I, 1997.

Grigor'yan (Alexander). -- Analytic and geometric background of recurrence and non-explosion of the Brownian motion on Riemannian manifolds. Bulletin of the American Mathematical Society, vol. 36, n°2, 1999, pp. 135--249.

Rosenberg (Steven). -- The Laplacian on a Riemannian manifold. -- Cambridge University Press, Cambridge, 1997, x+172p. An introduction to analysis on manifolds.

This document was translated from LATEX by HEVEA.