Principles of Random Walk

In this edition a large number of errors have been corrected, an occasional proof has been streamlined, and a number of references are made to recent pro­ gress. These references are to a supplementary bibliography, whose items are referred to as [S1] through [S26]. A thorough revision was not attempted. The development of the subject in the last decade would have required a treatment in a much more general con­ text. It is true that a number of interesting questions remain open in the concrete setting of random walk on the integers. (See [S 19] for a recent survey). On the other hand, much of the material of this book (foundations, fluctuation theory, renewal theorems) is now available in standard texts, e.g. Feller [S9], Breiman [S1], Chung [S4] in the more general setting of random walk on the real line. But the major new development since the first edition occurred in 1969, when D. Ornstein [S22] and C. J. Stone [S26] succeeded in extending the recurrent potential theory in· Chapters II and VII from the integers to the reals. By now there is an extensive and nearly complete potential theory of recurrent random walk on locally compact groups, Abelian ( [S20], [S25]) as well as non­ Abelian ( [S17], [S2] ). Finally, for the non-specialist there exists now an unsurpassed brief introduction to probabilistic potential theory, in the context of simple random walk and Brownian motion, by Dynkin and Yushkevich [S8].