Random Walks on Infinite Graphs and Groups

✍ Scribed by Wolfgang Woess

• Publisher: Cambridge University Press
• Year: 2000
• Tongue: English
• Leaves: 347
• Series: Cambridge Tracts in Mathematics 138
• Category: Library

✦ Synopsis

This eminent work focuses on the interplay between the behavior of random walks and discrete structure theory. Wolfgang Woess considers Markov chains whose state space is equipped with the structure of an infinite, locally-finite graph, or of a finitely generated group. He assumes the transition probabilities are adapted to the underlying structure in some way that must be specified precisely in each case. He also explores the impact the particular type of structure has on various aspects of the behavior of the random walk. In addition, the author shows how random walks are useful tools for classifying, or at least describing, the structure of graphs and groups.

✦ Table of Contents

Cover......Page 1
Cambridge Tracts in Mathematics 138......Page 2
Random Walks on Infinite Graphs and Groups......Page 4
0521552923......Page 5
Contents......Page 6
Preface......Page 9
A. Polya's walk......Page 14
B. Irreducible Markov chains......Page 15
C. Random walks on graphs......Page 20
D. Trees......Page 22
E. Random walks on finitely generated groups......Page 23
F. Locally finite graphs and topological groups......Page 25
A. Reversible Markov chains......Page 27
B. Flows, capacity, and Nash-Williams' criterion......Page 31
C. Comparison with non-reversible Markov chains......Page 36
A. Comparison theorems for random walks on graphs......Page 38
B. Growth and the classification of recurrent groups......Page 43
C. Random walks on quasi-transitive graphs......Page 49
A. Isoperimetric and Sobolev inequalities......Page 52
B. Cartesian products......Page 56
C. Isoperimetric inequalities and growth......Page 58
A. Transient subtrees......Page 62
B. Transient subtrees in quasi-transitive graphs......Page 67
A. Generalized lattices......Page 69
B. More on trees......Page 75
C. Extremal length and plane tilings......Page 80
D. Circle packings and random walks......Page 84
Notes and remarks......Page 90
A. The spectral radius and superharmonic functions......Page 94
B. p-Recurrence......Page 95
A. The rate of escape......Page 97
B. Application to generalized lattices......Page 101
A. Singularities of the Green function......Page 106
B. A functional equation......Page 111
C. Free products......Page 114
A. The spectral radius of reversible Markov chains......Page 123
B. Application to random walks on graphs......Page 125
C. Examples: trees, strongly ramified graphs, and tilings......Page 127
11. A lower bound for simple random walks......Page 131
A. Amenable groups......Page 136
B. Automorphism groups and the spectral radius......Page 138
C. Some explicit computations......Page 142
Notes and remarks......Page 149
13. The local central limit theorem on the grid......Page 152
14. Growth, isoperimetric inequalities, and the asymptotic type of random walk......Page 158
A. Upper bounds and Nash inequalities......Page 159
B. Gaussian upper bounds......Page 165
C. Lower bounds......Page 170
A. Comparison and stability of asymptotic type on groups......Page 173
B. Polycyclic groups......Page 177
C. The solvable Baumslag-Solitar groups......Page 181
D. Random walks on lamplighter groups......Page 182
16. Simple random walks on the Sierpinski graphs......Page 184
A. Stopping times and an equation for the Green function......Page 185
B. Singularity analysis......Page 189
17. Local limit theorems on free products......Page 194
A. The typical case: n^{-3/2}......Page 196
B. Instability of the exponent......Page 202
18. Intermezzo: Cartesian products......Page 208
A. Space-time asymptotics for aperiodic simple random walks on TM......Page 212
B. Finite range random walks on free groups......Page 218
C. Radial random walks on the homogeneous tree......Page 226
Notes and remarks......Page 229
A. The Dirichlet problem and convergence to the boundary......Page 233
B. Compactifications with "hyperbolic" properties......Page 237
21. Ends of graphs and the Dirichlet problem......Page 243
A. The transitive case......Page 245
B. Geometric adaptedness conditions......Page 252
22. Hyperbolic graphs and groups......Page 255
23. The Dirichlet problem for circle packing graphs......Page 265
24. The construction of the Martin boundary......Page 269
A. Exponentials and extended exponentials......Page 275
B. The Martin compactification of random walks on the grid......Page 281
26. Trees, ends, and free products......Page 288
A. Thin ends and trees......Page 290
B. Free products......Page 296
27. The Martin boundary of hyperbolic graphs......Page 301
A. Minimal harmonic functions on Cartesian products......Page 310
B. The Martin compactification o f T x Z......Page 314
Notes and remarks......Page 322
Acknowledgments......Page 328
Bibliography......Page 329
Index......Page 344