Random Walks on Infinite Graphs and Groups

by Wolfgang Woess

• ISBN13: 9780521552929
• ISBN10: 0521552923
• Format: Hardcover
• Copyright: 2000-02-13
• Publisher: Cambridge University Press

Summary

The main theme of this book is the interplay between the behaviour of a class of stochastic processes (random walks) and discrete structure theory. The author considers Markov chains whose state space is equipped with the structure of an infinite, locally-finite graph, or as a particular case, of a finitely generated group. The transition probabilities are assumed to be adapted to the underlying structure in some way that must be specified precisely in each case. From the probabilistic viewpoint, the question is what impact the particular type of structure has on various aspects of the behaviour of the random walk. Vice-versa, random walks may also be seen as useful tools for classifying, or at least describing the structure of graphs and groups. Links with spectral theory and discrete potential theory are also discussed. This book will be essential reading for all researchers working in stochastic process and related topics.

Table of Contents

Preface	viii
The type problem	1	(80)
Basic facts	1	(13)
Polya's walk	1	(1)
Irreducible Markov chains	2	(5)
Random walks on graphs	7	(2)
Trees	9	(1)
Random walks on finitely generated groups	10	(2)
Locally finite graphs and topological groups	12	(2)
Recurrence and transience of infinite networks	14	(11)
Reversible Markov chains	14	(4)
Flows, capacity, and Nash-Williams' criterion	18	(5)
Comparison with non-reversible Markov chains	23	(2)
Applications to random walks	25	(14)
Comparison theorems for random walks on graphs	25	(5)
Growth and the classification of recurrent groups	30	(6)
Random walks on quasi-transitive graphs	36	(3)
Isoperimetric inequalities	39	(10)
Isoperimetric and Sobolev inequalities	39	(4)
Cartesian products	43	(2)
Isoperimetric inequalities and growth	45	(4)
Transient subtrees, and the classification of the recurrent quasi-transitive graphs	49	(7)
Transient subtrees	49	(5)
Transient subtrees in quasi-transitive graphs	54	(2)
More on recurrence	56	(25)
Generalized lattices	56	(6)
More on trees	62	(5)
Extremal length and plane tilings	67	(4)
Circle packings and random walks	71	(6)
Notes and remarks	77	(4)
The spectral radius	81	(58)
Superharmonic functions and ρ-recurrence	81	(3)
The spectral radius and superharmonic functions	81	(1)
ρ-Recurrence	82	(2)
The spectral radius, the rate of escape, and generalized lattices	84	(9)
The rate of escape	84	(4)
Application to generalized lattices	88	(5)
Computing the Green function	93	(17)
Singularities of the Green function	93	(5)
A functional equation	98	(3)
Free products	101	(9)
The spectral radius and strong isoperimetric inequalities	110	(8)
The spectral radius of reversible Markov chains	110	(2)
Application to random walks on graphs	112	(2)
Examples: trees, strongly ramified graphs, and tilings	114	(4)
A lower bound for simple random walks	118	(5)
The spectral radius and amenability	123	(16)
Amenable groups	123	(2)
Automorphism groups and the spectral radius	125	(4)
Some explicit computations	129	(7)
Notes and remarks	136	(3)
The asymptotic behaviour of transition probabilities	139	(81)
The local central limit theorem on the grid	139	(6)
Growth, isoperimetric inequalities, and the asymptotic type of random walk	145	(15)
Upper bounds and Nash inequalities	146	(6)
Gaussian upper bounds	152	(5)
Lower bounds	157	(3)
The asymptotic type of random walks on amenable groups	160	(11)
Comparison and stability of asymptotic type on groups	160	(4)
Polycyclic groups	164	(4)
The solvable Baumslag-Solitar groups	168	(1)
Random walks on lamplighter groups	169	(2)
Simple random walks on the Sierpinski graphs	171	(10)
Stopping times and an equation for the Green function	172	(4)
Singularity analysis	176	(5)
Local limit theorems on free products	181	(14)
The typical case: n-3/2	183	(6)
Instability of the exponent	189	(6)
Intermezzo: Cartesian products	195	(4)
Free groups and homogeneous trees	199	(21)
Space-time asymptotics for aperiodic simple random walks on TM	199	(6)
Finite range random walks on free groups	205	(8)
Radial random walks on the homogeneous tree	213	(3)
Notes and remarks	216	(4)
An introduction to topological boundary theory	220	(95)
A probabilistic approach to the Dirichlet problem, and a class of compactifications	220	(10)
The Dirichlet problem and convergence to the boundary	220	(4)
Compactifications with ``hyperbolic'' properties	224	(6)
Ends of graphs and the Dirichlet problem	230	(12)
The transitive case	232	(7)
Geometric adaptedness conditions	239	(3)
Hyperbolic graphs and groups	242	(10)
The Dirichlet problem for circle packing graphs	252	(4)
The construction of the Martin boundary	256	(6)
Generalized lattices, Abelian and nilpotent groups, and graphs with polynomial growth	262	(13)
Exponentials and extended exponentials	262	(6)
The Martin compactification of random walks on the grid	268	(7)
Trees, ends, and free products	275	(13)
Thin ends and trees	277	(6)
Free products	283	(5)
The Martin boundary of hyperbolic graphs	288	(9)
Cartesian products	297	(18)
Minimal harmonic functions on Cartesian products	297	(4)
The Martin compactification of T x Z	301	(8)
Notes and remarks	309	(6)
Acknowledgments	315	(1)
Bibliography	316	(15)
Index	331