Random Walks and Graph Geometry: a Survey

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).

Abstract

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 kÎN the quantity p^k(x,x)=Pr_x(M_k=x) is the probability that the random walk (M_n) starting from xÎ G returns to x at the k-th step. In the case of the simple random walk p(x,y)=p¹(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,yÎG. 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 L^p 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; $ yÏA, x~ y}.

Definition 1 The graph G associated to µ has the doubling property if there exists C>0 such that for all xÎG and r>0,

V(x,2r)£ C V(x,r). (D)

If c₀(A) is the set of functions on G with a finite support in the subset A, for f in c₀(G) the length of the gradient is defined by

|Ñ f|(x)=

æ
ç
ç
ç
ç
è

ó
õ

y~ x

|f(x)-f(y)|²p(x,y)

ö
÷
÷
÷
÷
ø

1/2

for xÎG. It is easy to verify that the identity ||Ñ f||₂²=<(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 (p^k(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

p^k(x,x)£ C m(x)k^-D/2, (2)

for all xÎG and k³ 1 is equivalent to the Sobolev inequality for all fÎ c₀(G): ||f||_2D/D-2£ C ||Ñ f||₂.

The relation with the geometry of the graph is as follows. The Sobolev inequality implies that V(x,r)£ c r^D for some constant c>0. On the other hand the isoperimetric inequality

|A|

D-1

£ C

xÎ A,yÏA, x~ A

µ_xy,

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 r^D£ V(x,r)£ C r^D, for any xÎ G and r>0, there exists c', C' such that

c'k^-D/2£

sup

xÎG

p^2k(x,x)£ C'k

D+1

and the bounds are optimal.

3 Upper Bounds: Regular Volume Growth

In this section graphs without prescribed volume assumption are considered.

Definition 2

p^k(x,y)£ C

m(y)

V(x,(K)^1/2)

exp

æ
ç
ç
è

-c

d²(x,y)

ö
÷
÷
ø

" x,yÎ G, k³1. (UE)

The inequality (DUE) is the above inequality but with x=y.

p^2k(x,y)³ c

m(y)

V(x,(K)^1/2)

" xÎ G, k³1. (DLE)

The graph G is said to satisfy a Faber-Krahn inequality if there exists a, n>0 such that

inf

{

|| |Ñ f|||₂²;fÎ c₀(A), ||f||₂=1

}

r²

æ
ç
ç
è

V(x,r)

|A|

ö
÷
÷
ø

, (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 (p^k(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).

References

[1]: Coulhon (Thierry). -- Heat kernels on non-compact Riemannian manifolds: a partial survey. In Séminaire de Théorie Spectrale et Géométrie, No. 15, Année 1996--1997, pp. 167--187. -- Université Grenoble I, 1997.
[2]: 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.
[3]: 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 L^AT_EX by H^EV^EA.