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.
Author(s): Steven P. Lalley
Series: Graduate Texts in Mathematics 297
Edition: 1
Publisher: Springer Nature Switzerland
Year: 2023
Language: English
Pages: 369
City: Cham
Tags: Random Walks, Groups, Regodic Theorem, Harmonic Functions, Martingales, Entropy
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
