Random Walks and Geometry : Proceedings of a Workshop at the Erwin Schrödinger Institute, Vienna, June 18 - July 13, 2001

Recent developments show that probability methods have become a very powerful tool in such different areas as statistical physics, dynamical systems, Riemannian geometry, group theory, harmonic analysis, graph theory and computer science. This volume is an outcome of the special semester 2001 - Random Walks held at the Schrödinger Institute in Vienna, Austria. It contains original research articles with non-trivial new approaches based on applications of random walks and similar processes to Lie groups, geometric flows, physical models on infinite graphs, random number generators, Lyapunov exponents, geometric group theory, spectral theory of graphs and potential theory. Highlights are the first survey of the theory of the stochastic Loewner evolution and its applications to percolation theory (a new rapidly developing and very promising subject at the crossroads of probability, statistical physics and harmonic analysis), surveys on expander graphs, random matrices and quantum chaos, cellular automata and symbolic dynamical systems, and others. The contributors to the volume are the leading experts in the area. The book will provide a valuable source both for active researchers and graduate students in the respective fields. Preface......Page 7 Table of contents......Page 9 Surveys and longer articles......Page 11 Some Markov chains on abelian groups withapplications......Page 13 Random walks and physical models on infinitegraphs: an introduction......Page 45 The Garden of Eden Theorem for cellularautomata and for symbolic dynamical systems......Page 82 Expander graphs, random matricesand quantum chaos......Page 118 The Ihara zeta function of infinite graphs, the KNSspectral measure and integrable maps......Page 151 Simplicité de spectres de Lyapounov et propriétéd’isolation spectrale pour une famille d’opérateursde transfert sur l’espace projectif......Page 191 An introduction to the StochasticLoewner Evolution......Page 271 A canonical form for automorphisms of totallydisconnected locally compact groups......Page 305 On the classification of invariant measures forhorosphere foliations on nilpotent covers ofnegatively curved manifolds......Page 329 Markov processes on vermiculated spaces......Page 347 Cactus trees and lower bounds on the spectralradius of vertex-transitive graphs......Page 359 Equilibrium measure, Poisson kernel and effectiveresistance on networks......Page 373 Internal diffusion limited aggregation on discretegroups of polynomial growth......Page 386 On the physical relevance of random walks:an example of random walks on a randomlyoriented lattice......Page 403 Random walks, entropy and hopfianity of freegroups......Page 423 Growth rates of small cancellation groups......Page 431 Recurrence properties of random walks on finitevolume homogeneous manifolds......Page 441 On the cohomology of foliations with amenablegroupoid......Page 454 Linear rate of escape and convergence in direction......Page 469 Remarks on harmonic functions on affine buildings......Page 483 Random walks, spectral radii, and Ramanujangraphs......Page 496 Cogrowth of arbitrary graphs......Page 511 Total variation lower bounds for finiteMarkov chains: Wilson’s lemma......Page 525 Annotation Recent developments show that probability methods have become a very powerful tool in such different areas as statistical physics, dynamical systems, Riemannian geometry, group theory, harmonic analysis, graph theory and computer science. This volume is an outcome of the special semester 2001 - Random Walks held at the Schrodinger Institute in Vienna, Austria. It contains original research articles with non-trivial new approaches based on applications of random walks and similar processes to Lie groups, geometric flows, physical models on infinite graphs, random number generators, Lyapunov exponents, geometric group theory, spectral theory of graphs and potential theory. Highlights are the first survey of the theory of the stochastic Loewner evolution and its applications to percolation theory (a new rapidly developing and very promising subject at the crossroads of probability, statistical physics and harmonic analysis), surveys on expander graphs, random matrices and quantum chaos, cellular automata and symbolic dynamical systems, and others. The contributors to the volume are the leading experts in the area Die jüngsten Entwicklungen zeigen, dass sich Wahrscheinlichkeitsverfahren zu einem sehr wirkungsvollen Werkzeug entwickelt haben, und das auf so unterschiedlichen Gebieten wie statistische Physik, dynamische Systeme, Riemann'sche Geometrie, Gruppentheorie, harmonische Analyse, Graphentheorie und Informatik. Kolmogorov complexity theory [7, 8] gives the logical foundation of probability theory but it can not be applied directly to the testing of "randomness" for specific bit strings. Editor, Vadim A. Kaimanovich, In Collaboration With Klaus Schmidt And Wolfgang Woess. Includes Bibilographical References.