Random Walks on Infinite Groups

This text presents the basic theory of random walks on infinite, finitely generated groups, along with certain background material in measure-theoretic probability. The main objective is to show how structural features of a group, such as amenability/nonamenability, affect qualitative aspects of symmetric random walks on the group, such as transience/recurrence, speed, entropy, and existence or nonexistence of nonconstant, bounded harmonic functions. The book will be suitable as a textbook for beginning graduate-level courses or independent study by graduate students and advanced undergraduate students in mathematics with a solid grounding in measure theory and a basic familiarity with the elements of group theory. The first seven chapters could also be used as the basis for a short course covering the main results regarding transience/recurrence, decay of return probabilities, and speed. The book has been organized and written so as to be accessible not only to students in probability theory, but also to students whose primary interests are in geometry, ergodic theory, or geometric group theory. Preface Contents 1 First Steps 1.1 Prologue: Gambler's Ruin 1.2 Groups and Their Cayley Graphs 1.3 Random Walks: Definition 1.4 Recurrence and Transience 1.5 Symmetric Random Walks on Zd 1.6 Random Walks on Z2*Z2*Z2 1.7 Lamplighter Random Walks 1.8 Excursions of Recurrent Random Walks 2 The Ergodic Theorem 2.1 Formulation of the Theorem 2.2 The Range of a Random Walk 2.3 Cut Points of a Random Walk 2.4 Proof of the Ergodic Theorem 2.5 Non-Ergodic Transformations 3 Subadditivity and Its Ramifications 3.1 Speed of a Random Walk 3.2 Subadditive Sequences 3.3 Kingman's Subadditive Ergodic Theorem 3.4 The Trail of a Lamplighter 3.5 Proof of Kingman's Theorem 4 The Carne-Varopoulos Inequality 4.1 Statement and Consequences 4.2 Chebyshev Polynomials 4.3 A Transfer Matrix Inequality 4.4 Markov Operators 5 Isoperimetric Inequalities and Amenability 5.1 Amenable and Nonamenable Groups 5.2 Klein's Ping-Pong Lemma 5.3 Kesten's Theorem: Amenable Groups 5.4 The Dirichlet Form 5.5 Sobolev-Type Inequalities 5.6 Kesten's Theorem: Nonamenable Groups 5.7 Nash-Type Inequalities 6 Markov Chains and Harmonic Functions 6.1 Markov Chains 6.2 Harmonic and Superharmonic Functions 6.3 Space-Time Harmonic Functions 6.4 Reversible Markov Chains 7 Dirichlet's Principle and the Recurrence Type Theorem 7.1 Dirichlet's Principle 7.2 Rayleigh's Comparison Principle 7.3 Varopoulos' Growth Criterion 7.4 Induced Random Walks on Subgroups 8 Martingales 8.1 Martingales: Definitions and Examples 8.2 Doob's Optional Stopping Formula 8.3 The Martingale Convergence Theorem 8.4 Martingales and Harmonic Functions 8.5 Reverse Martingales 9 Bounded Harmonic Functions 9.1 The Invariant σ-Algebra I 9.2 Absolute Continuity of Exit Measures 9.3 Two Examples 9.4 The Tail σ-Algebra T 9.5 Weak Ergodicity and the Liouville Property 9.6 Coupling 9.7 Tail Triviality Implies Weak Ergodicity 10 Entropy 10.1 Avez Entropy and the Liouville Property 10.2 Shannon Entropy and Conditional Entropy 10.3 Avez Entropy 10.4 Conditional Entropy on a σ-Algebra 10.5 Avez Entropy and Boundary Triviality 10.6 Entropy and Kullback-Leibler Divergence 11 Compact Group Actions and Boundaries 11.1 -Spaces 11.2 Stationary and Invariant Measures 11.3 Transitive Group Actions 11.4 μ-Processes and μ-Boundaries 11.5 Boundaries and Speed 11.5.1 A. Random Walks on Fk 11.5.2 B. Random Walks on SL(2,Z) 11.6 The Busemann Boundary 11.7 The Karlsson–Ledrappier Theorem 12 Poisson Boundaries 12.1 Poisson and Furstenberg-Poisson Boundaries 12.2 Entropy of a Boundary 12.3 Lamplighter Random Walks 12.4 Existence of Poisson Boundaries 13 Hyperbolic Groups 13.1 Hyperbolic Metric Spaces 13.2 Quasi-Geodesics 13.3 The Gromov Boundary of a Hyperbolic Space 13.4 Boundary Action of a Hyperbolic Group 13.5 Random Walks on Hyperbolic Groups 13.6 Cannon's Lemma 13.7 Random Walks: Cone Points 14 Unbounded Harmonic Functions 14.1 Lipschitz Harmonic Functions 14.2 Virtually Abelian Groups 14.3 Existence of Harmonic Functions 14.4 Poincaré and Cacciopoli Inequalities 14.5 The Colding-Minicozzi-Kleiner Theorem 14.5.1 A. Preliminaries: Positive Semi-Definite Matrices 14.5.2 B. Preliminaries: Efficient Coverings 14.5.3 C. The Key Estimate 14.5.4 D. Bounded Doubling 14.5.5 E. The General Case 15 Groups of Polynomial Growth 15.1 The Kleiner Representation 15.2 Subgroups of UD 15.3 Milnor's Lemma 15.4 Sub-cubic Polynomial Growth 15.5 Gromov's Theorem A A 57-Minute Course in Measure–Theoretic Probability A.1 Definitions, Terminology, and Notation A.2 Sigma Algebras A.3 Independence A.4 Lebesgue Space A.5 Borel-Cantelli Lemma A.6 Hoeffding's Inequality A.7 Weak Convergence A.8 Likelihood Ratios A.9 Conditional Expectation References Index