The simplest mathematical model of the Brownian motion of physics is the simple, symmetric random walk. This book collects and compares current results — mostly strong theorems which describe the properties of a random walk. The modern problems of the limit theorems of probability theory are treated in the simple case of coin tossing. Taking advantage of this simplicity, the reader is familiarized with limit theorems (especially strong ones) without the burden of technical tools and difficulties. An easy way of considering the Wiener process is also given, through the study of the random walk.
Since the first and second editions were published in 1990 and 2005, a number of new results have appeared in the literature. The first two editions contained many unsolved problems and conjectures which have since been settled; this third, revised and enlarged edition includes those new results. In this edition, a completely new part is included concerning Simple Random Walks on Graphs. Properties of random walks on several concrete graphs have been studied in the last decade. Some of the obtained results are also presented.

Preface to the First Edition v

Preface to the Second Edition vii

Preface to the Third Edition ix

Introduction xvii

I. SIMPLE SYMMETRIC RANDOM WALK IN Z1

Notations and abbreviations 3

1 Introduction of Part I 9

1.1 Random walk 9

1.2 Dyadic expansion 10

1.3 Rademacher functions 10

1.4 Coin tossing 11

1.5 The language of the probabilist 11

2 Distributions 13

2.1 Exact distributions 13

2.2 Limit distributions 19

3 Recurrence and the Zero-One Law 23

3.1 Recurrence 23

3.2 The zero-one law 25

4 From the Strong Law of Large Numbers to the Law of Iterated Logarithm 27

4.1 BorelCantelli lemma and Markov inequality 27

4.2 The strong law of large numbers 29

4.3 Between the strong law of large numbers and the law of iterated logarithm 30

4.4 The LIL of Khinchine 31

5 Lévy Classes 35

5.1 Definitions 35

5.2 EFKP LIL 36

5.3 The laws of Chung and Hirsch 41

5.4 When will Sn be very large? 41

5.5 A theorem of Csáki 43

6 Wiener Process and Invariance Principle 49

6.1 Four lemmas 49

6.2 Joining of independent random walks 51

6.3 Definition of the Wiener process 53

6.4 Invariance Principle 54

7 Increments 59

7.1 Long head-runs 59

7.2 The increments of a Wiener process 68

7.3 The increments of SN 79

8 Strassen Type Theorems 85

8.1 The theorem of Strassen 85

8.2 Strassen theorems for increments 92

8.3 The rate of convergence in Strassen's theorems 94

8.4 A theorem of Wichura 97

9 Distribution of the Local Time 99

9.1 Exact distributions 99

9.2 Limit distributions 105

9.3 Definition and distribution of the local time of a Wiener process 106

10 Local Time and Invariance Principle 111

10.1 An invariance principle 111

10.2 A theorem of Lévy 113

11 Strong Theorems of the Local Time 119

11.1 Strong theorems for ξ(x, n) and ξ(n) 119

11.2 Increments of η(x, t) 121

11.3 Increments of ξ(x, n) 125

11.4 Strassen type theorems 126

11.5 Stability 128

12 Excursions 137

12.1 On the distribution of the zeros of a random walk 137

12.2 Local time and the number of long excursions (Mesure du voisinage) 143

12.3 Local time and the number of high excursions 148

12.4 The local time of high excursions 149

12.5 How many times can a random walk reach its maximum? . 154

13 Frequently and Rarely Visited Sites 159

13.1 Favourite sites 159

13.2 Rarely visited sites 163

14 An Embedding Theorem 165

14.1 On the Wiener sheet 165

14.2 The theorem 166

14.3 Applications 170

15 A Few Further Results 173

15.1 On the location of the maximum of a random walk 173

15.2 On the location of the last zero 177

15.3 The OrnsteinUhlenbeck process and a DarlingErd®s theorem 181

15.4 A discrete version of the Itô formula 185

16 Summary of Part I 189

II. SIMPLE SYMMETRIC RANDOM WALK IN Zd

Notations 193

17 The Recurrence Theorem 195

18 Wiener Process and Invariance Principle 205

19 The Law of Iterated Logarithm 209

20 Local Time 213

20.1 ξ(0, n) in Z2 213

20.2 ξ(n) in Zd 220

20.3 A few further results 222

21 The Range 223

21.1 The strong law of large numbers 223

21.2 CLT, LIL and Invariance Principle 227

21.3 Wiener sausage 228

22 Heavy Points and Heavy Balls 229

22.1 The number of heavy points 229

22.2 Heavy balls 238

22.3 Heavy balls around heavy points 242

22.4 Wiener process 243

23 Crossing and Self-crossing 245

24 Large Covered Balls 249

24.1 Completely covered discs centered in the origin of Z2 249

24.2 Completely covered disc in Z2 with arbitrary centre 267

24.3 Almost covered disc centred in the origin of Z2 268

24.4 Discs covered with positive density in Z2 270

24.5 Completely covered balls in Zd 276

24.6 Large empty balls 281

24.7 Summary of Chapter 24 284

25 Long Excursions 285

25.1 Long excursions in Z2 285

25.2 Long excursions in high dimension 288

26 Speed of Escape 291

27 A Few Further Problems 297

27.1 On the Dirichlet problem 297

27.2 DLA model 300

27.3 Percolation 301

III. RANDOM WALK IN RANDOM ENVIRONMENT Notations 305

28 Introduction of Part III 307

29 In the First Six Days 311

30 After the Sixth Day 315

30.1 The recurrence theorem of Solomon 315

30.2 Guess how far the particle is going away in an RE 317

30.3 A prediction of the Lord 318

30.4 A prediction of the physicist 330

31 What Can a Physicist Say About the Local Time ξ(0, n)? 333

31.1 Two further lemmas on the environment 333

31.2 On the local time ξ(0, n) 334

32 On the Favourite Value of the RWIRE 341

33 A Few Further Problems 349

33.1 Two theorems of Golosov 349

33.2 Non-nearest-neighbour random walk 351

33.3 RWIRE in Z 352

33.4 Non-independent environments 354

33.5 Random walk in random scenery 354

33.6 Random environment and random scenery 357

33.7 Reinforced random walk 357

IV. RANDOM WALKS IN GRAPHS

34 Introduction of Part IV 363

35 Random Walk in Comb 365

35.1 Definitions and legend 365

35.2 Approximation 366

35.3 Extremes of a comb-walk 367

35.4 Local time of a comb-walk 368

35.5 Large square covered by a comb-random-walk 369

36 Random Walk in a Comb and in a Brush with Crossings 371

36.1 Comb with crosslines 371

36.2 A question on a brush with crossings 372

37 Random Walk on a Spider 373

38 Random Walk in Half-Plane-Half-Comb 377

References 379

Author Index 397

Subject Index 401

中科院文献情报中心