Probability on Trees and Networks

Höfundar: Russell Lyons; Yuval Peres (Útgáfa: 0)
Probability on Trees and Networks

Kaup valmöguleikar

Starting around the late 1950s, several research communities began relating the geometry of graphs to stochastic processes on these graphs. This book, twenty years in the making, ties together research in the field, encompassing work on percolation, isoperimetric inequalities, eigenvalues, transition probabilities, and random walks. Written by two leading researchers, the text emphasizes intuition, while giving complete proofs and more than 850 exercises.

Nánar um bókina

Útgefandi
Cambridge University Press
ISBN
9781316784372
Print ISBN
9781107160156
Format
ePub
Útgáfa
0
Höfundar
Russell Lyons; Yuval Peres
Tungumál
English
Útgefið
2017-01-20
Prent takmörkun á líftíma
10

Kaflar

  • Cover
  • Half title
  • Dedication
  • Series
  • Title
  • Copyright
  • Table of Contents
  • Preface
  • Chapter 1: Some Highlights
  • 1. Graph Terminology
  • 2. Branching Number
  • 3. Electric Current
  • 4. Random Walks
  • 5. Percolation
  • 6. Branching Processes
  • 7. Random Spanning Trees
  • 8. Hausdorff Dimension
  • 9. Capacity
  • 10. Embedding Trees into Euclidean Space
  • 11. Notes
  • 12. Collected In-Text Exercises
  • 13. Additional Exercises
  • Chapter 2: Random Walks and Electric Networks
  • 1. Circuit Basics and Harmonic Functions
  • 2. More Probabilistic Interpretations
  • 3. Network Reduction
  • 4. Energy
  • 5. Transience and Recurrence
  • 6. Rough Isometries and Hyperbolic Graphs
  • 7. Hitting, Commute, and Cover Times
  • 8. The Canonical Gaussian Field
  • 9. Notes
  • 10. Collected In-Text Exercises
  • 11. Additional Exercises
  • Chapter 3: Special Networks
  • 1. Flows, Cutsets, and Random Paths
  • 2. Trees
  • 3. Growth of Trees
  • 4. Cayley Graphs
  • 5. Notes
  • 6. Collected In-Text Exercises
  • 7. Additional Exercises
  • Chapter 4: Uniform Spanning Trees
  • 1. Generating Uniform Spanning Trees
  • 2. Electrical Interpretations
  • 3. The Square Lattice Z[sup(2)]
  • 4. Notes
  • 5. Collected In-Text Exercises
  • 6. Additional Exercises
  • Chapter 5: Branching Processes, Second Moments, and Percolation
  • 1. Galton-Watson Branching Processes
  • 2. The First-Moment Method
  • 3. The Weighted Second-Moment Method
  • 4. Quasi-independent Percolation
  • 5. Transience of Percolation Clusters in Z[sup(d)]
  • 6. Reversing the Second-Moment Inequality
  • 7. Surviving Galton-Watson Trees
  • 8. Harris’s Inequality
  • 9. Galton-Watson Networks
  • 10. Notes
  • 11. Collected In-Text Exercises
  • 12. Additional Exercises
  • Chapter 6: Isoperimetric Inequalities
  • 1. Flows and Submodularity
  • 2. Spectral Radius
  • 3. Nonbacktracking Paths and Cogrowth
  • 4. Relative Mixing Rate, Spectral Gap, and Expansion in Finite Networks
  • 5. Planar Graphs
  • 6. Euclidean Lattices and Entropy
  • 7. Expansion Profiles and Decay of Transition Probabilities
  • 8. Anchored Isoperimetric Profiles and Transience
  • 9. Anchored Expansion and Percolation
  • 10. Notes
  • 11. Collected In-Text Exercises
  • 12. Additional Exercises
  • Chapter 7: Percolation on Transitive Graphs
  • 1. Groups and Amenability
  • 2. Tolerance and Ergodicity
  • 3. The Number of Infinite Clusters
  • 4. Inequalities for p[sub(c)]
  • 5. Merging Infinite Clusters and Invasion Percolation
  • 6. Upper Bounds for p[sub(u)]
  • 7. Lower Bounds for p[sub(u)]
  • 8. Bootstrap Percolation on Regular Trees
  • 9. Notes
  • 10. Collected In-Text Exercises
  • 11. Additional Exercises
  • Chapter 8: The Mass-Transport Technique and Percolation
  • 1. The Mass-Transport Principle for Cayley Graphs
  • 2. Beyond Cayley Graphs: Unimodularity
  • 3. Infinite Clusters in Invariant Percolation
  • 4. Critical Percolation on Nonamenable Transitive Unimodular Graphs
  • 5. Bernoulli Percolation on Planar Quasi-transitive Graphs
  • 6. Properties of Infinite Clusters
  • 7. Invariant Percolation on Amenable Graphs
  • 8. Appendix: Unimodularity of Planar Quasi-transitive Graphs
  • 9. Notes
  • 10. Collected In-Text Exercises
  • 11. Additional Exercises
  • Chapter 9: Infinite Electrical Networks and Dirichlet Functions
  • 1. Free and Wired Electrical Currents
  • 2. Planar Duality
  • 3. Harmonic Dirichlet Functions
  • 4. Planar Graphs and Hyperbolic Graphs
  • 5. Random Walk Traces
  • 6. Notes
  • 7. Collected In-Text Exercises
  • 8. Additional Exercises
  • Chapter 10: Uniform Spanning Forests
  • 1. Limits over Exhaustions
  • 2. Coupling, Harmonic Dirichlet Functions, and Expected Degree
  • 3. Planar Networks and Euclidean Lattices
  • 4. Tail Triviality
  • 5. The Number of Trees
  • 6. The Size of the Trees
  • 7. Loop-Erased Random Walk and Harmonic Measure from Infinity
  • 8. Appendix: Von Neumann Dimension and ℓ[sup(2)]-Betti Numbers
  • 9. Notes
  • 10. Collected In-Text Exercises
  • 11. Additional Exercises
  • Chapter 11: Minimal Spanning Forests
  • 1. Minimal Spanning Trees
  • 2. Deterministic Results
  • 3. Basic Probabilistic Results
  • 4. Tree Sizes
  • 5. Planar Graphs
  • 6. Nontreeable Groups
  • 7. Notes
  • 8. Collected In-Text Exercises
  • 9. Additional Exercises
  • Chapter 12: Limit Theorems for Galton-Watson Processes
  • 1. Size-Biased Trees and Immigration
  • 2. Supercritical Processes: Proof of the Kesten-Stigum Theorem
  • 3. Subcritical Processes
  • 4. Critical Processes
  • 5. Notes
  • 6. Collected In-Text Exercises
  • 7. Additional Exercises
  • Chapter 13: Escape Rate of Random Walks and Embeddings
  • 1. Basic Examples
  • 2. The Varopoulos-Carne Bound
  • 3. An Application to Mixing Time
  • 4. Markov Type of Metric Spaces
  • 5. Embeddings of Finite Metric Spaces
  • 6. A Diffusive Lower Bound for Cayley Graphs
  • 7. Branching Number of a Graph
  • 8. Tree-Indexed Random Walks
  • 9. Notes
  • 10. Collected In-Text Exercises
  • 11. Additional Exercises
  • Chapter 14: Random Walks on Groups and Poisson Boundaries
  • 1. Tail, Entropy, and Speed for Transitive Markov Chains
  • 2. Harmonic Functions and the Liouville Property
  • 3. Harmonic Functions and the Poisson Boundary
  • 4. Identifying the Poisson Boundary
  • 5. Appendix: Ergodic Theorems
  • 6. Appendix: The Zero-Two Law for Transitive Markov Chains
  • 7. Notes
  • 8. Collected In-Text Exercises
  • 9. Additional Exercises
  • Chapter 15: Hausdorff Dimension
  • 1. Basics
  • 2. Coding by Trees
  • 3. Galton-Watson Fractals
  • 4. Hölder Exponent
  • 5. Derived Trees
  • 6. Notes
  • 7. Collected In-Text Exercises
  • 8. Additional Exercises
  • Chapter 16: Capacity and Stochastic Processes
  • 1. Definitions
  • 2. Percolation on Trees
  • 3. Euclidean Space
  • 4. Fractal Percolation and Brownian Intersections
  • 5. Generalized Diameters and Average Meeting Height on Trees
  • 6. Notes
  • 7. Collected In-Text Exercises
  • 8. Additional Exercises
  • Chapter 17: Random Walks on Galton-Watson Trees
  • 1. Markov Chains and Ergodic Theory
  • 2. Stationary Measures on Trees
  • 3. Speed on Galton-Watson Trees
  • 4. Harmonic Measure: The Goal
  • 5. Flow Rules and Markov Chains on the Space of Trees
  • 6. The Hölder Exponent of Limit Uniform Measure
  • 7. Dimension Drop for Other Flow Rules
  • 8. Harmonic-Stationary Measure
  • 9. Confinement of Simple Random Walk
  • 10. Numerical Calculations
  • 11. Notes
  • 12. Collected In-Text Exercises
  • 13. Additional Exercises
  • Comments on Exercises
  • Bibliography
  • Glossary of Notation
  • Index