Probability on Graphs: Random Processes on Graphs and Lattices

by Geoffrey Grimmett

Overview

Grimmett's concise and masterful introduction to the basic mathematical ideas needed to model such random processes as viral marketing, epidemics, random algorithms, and efficient routing. The selection of topics and the approach taken to them is strongly motivated by modern applications. Each chapter ends with exciting exercises.

Product Details

ISBN-13:	9781139035835
Publisher:	Cambridge University Press
Publication date:	06/24/2010
Series:	Institute of Mathematical Statistics Textbooks , #1
Sold by:	Barnes & Noble
Format:	eBook
File size:	9 MB

About the Author

Geoffrey Grimmett is Professor of Mathematical Statistics in the Statistical Laboratory at the University of Cambridge. He has written numerous research articles in probability theory, as well as popular research books on percolation and the random-cluster model. In addition, he is a co-author, along with David Stirzaker and Dominic Welsh, of two successful textbooks on probability and random processes at the undergraduate and postgraduate levels. He has served as Master of Downing College since 2013 and was elected to the Royal Society in 2014.

Table of Contents

Preface ix

1 Random walks on graphs 1

1.1 Random walks and reversible Markov chains 1

1.2 Electrical networks 3

1.3 Flows and energy 8

1.4 Recurrence and resistance 11

1.5 Pólya's theorem 14

1.6 Graph theory 16

1.7 Exercises 18

2 Uniform spanning tree 21

2.1 Definition 21

2.2 Wilson's algorithm 23

2.3 Weak limits on lattices 28

2.4 Uniform forest 31

2.5 Schramm-Löwner evolutions 32

2.6 Exercises 37

3 Percolation and self-avoiding walk 39

3.1 Percolation and phase transition 39

3.2 Self-avoiding walks 42

3.3 Coupled percolation 45

3.4 Oriented percolation 45

3.5 Exercises 48

4 Association and influence 50

4.1 Holley inequality 50

4.2 FKG inequality 53

4.3 BK inequality 54

4.4 Hoeffding inequality 56

4.5 Influence for product measures 58

4.6 Proofs of influence theorems 63

4.7 Russo's formula and sharp thresholds 75

4.8 Exercises 78

5 Further percolation 81

5.1 Subcritical phase 81

5.2 Supercritical phase 86

5.3 Uniqueness of the infinite cluster 92

5.4 Phase transition 95

5.5 Open paths in annuli 99

5.6 The critical probability in two dimensions 103

5.7 Cardy's formula 110

5.8 The critical probability via the sharp-threshold theorem 121

5.9 Exercises 125

6 Contact process 127

6.1 Stochastic epidemics 127

6.2 Coupling and duality 128

6.3 Invariant measures and percolation 131

6.4 The critical value 133

6.5 The contact model on a tree 135

6.6 Space-time percolation 138

6.7 Exercises 141

7 Gibbs states 142

7.1 Dependency graphs 142

7.2 Markov fields and Gibbs states 144

7.3 Ising and Potts models 148

7.4 Exercises 150

8 Random-cluster model 152

8.1 The random-cluster and Ising/Potts models 152

8.2 Basic properties 155

8.3 Infinite-volume limits and phase transition 156

8.4 Open problems 160

8.5 In two dimensions 163

8.6 Random even graphs 168

8.7 Exercises 171

9 Quantum Ising model 175

9.1 The model 175

9.2 Continuum random-cluster model 176

9.3 Quantum Ising via random-cluster 179

9.4 Long-range order 184

9.5 Entanglement in one dimension 185

9.6 Exercises 189

10 Interacting particle systems 190

10.1 Introductory remarks 190

10.2 Contact model 192

10.3 Voter model 193

10.4 Exclusion model 196

10.5 Stochastic Ising model 200

10.6 Exercises 203

11 Random graphs 205

11.1 Erdos-Rényi graphs 205

11.2 Giant component 206

11.3 Independence and colouring 211

11.4 Exercises 217

12 Lorentz gas 219

12.1 Lorentz model 219

12.2 The square Lorentz gas 220

12.3 In the plane 223

12.4 Exercises 224

References 226

Index 243

Editorial Reviews

"The book under review serves admirably for this “getting started” purpose. It provides a rigorous introduction to a broad range of topics centered on the percolation-IPS field discussed above... This book, like a typical Part III course, requires only undergraduate background knowledge but assumes a higher level of general mathematical sophistication. It also requires active engagement by the reader. As I often tell students, “Mathematics is not a spectator sport — you learn by actually doing the exercises!” For the reader who is willing to engage the material and is not fazed by the fact that some proofs are only outlined or are omitted, this style enables the author to cover a lot of ground in 247 pages."
David Aldous, Bulletin of the American Mathematical Society

"It is written in a condensed style with only the briefest of introductions or motivations, but it is a mine of information for those who are well prepared and know how to use it. It formed the basis for a Probability reading group at the University of Warwick last term and was well received, and parts of it are being used by a colleague for an undergraduate module this term on Probability and Discrete Mathematics."
R.S. MacKay, Contemporary Physics

'This is clearly a successful advanced textbook.' Fernando Q. Gouvêa, MAA Reviews

From the Publisher