1. Preface to the First edition of Volume 1.
It is the purpose of this book to treat probability theory as a self-contained mathematical subject rigorously, avoiding non-mathematical concepts. At the same time, the book tries to describe the empirical background and to develop a feeling for the great variety of practical applications. This purpose is served by many special problems, numerical estimates, and examples which interrupt the main flow of the text. They are clearly set apart in print and are treated in a more picturesque language and with less formality. A number of special topics have been included in order to exhibit the power of general methods and to increase the usefulness of the book to specialists in various fields. To facilitate reading, detours from the main path are indicated by stars. The knowledge of starred sections is not assumed in the remainder.
A serious attempt has been made to unify methods. The specialist will find many simplifications of existing proofs and also new results. In particular, the theory of recurrent events has been developed for the purpose of this book. It leads to a new treatment of Markov chains which permits simplification even in the finite case.
The examples are accompanied by about 340 problems mostly with complete solutions. Some of them are simple exercises, but most of them serve as additional illustrative material to the text or contain various complements. One purpose of the examples and problems is to develop the reader's intuition and art of probabilistic formulation. Several previously treated examples show that apparently difficult problems may become almost trite once they are formulated in a natural way and put into the proper context.
There is a tendency in teaching to reduce probability problems to pure analysis as soon as possible and to forget the specific characteristics of probability theory itself. Such treatments are based on a poorly defined notion of random variables usually introduced at the outset. This book goes to the other extreme and dwells on the notion of sample space, without which random variables remain an artifice.
In order to present the true background unhampered by measurability questions and other purely analytic difficulties this volume is restricted to discrete sample spaces. This restriction is severe, but should be welcome to non-mathematical users. It permits the inclusion of special topics which are not easily accessible in the literature. At the same time, this arrangement makes it possible to begin in an elementary way and yet to include a fairly exhaustive treatment of such advanced topics as random walks and Markov chains. The general theory of random variables and their distributions, limit theorems, diffusion theory, etc., is deferred to a succeeding volume.
This book would not have been written without the support of the Office of Naval Research. One consequence of this support was a fairly regular personal contact with J L Doob, whose constant criticism and encouragement were invaluable. To him go my foremost thanks. The next thanks for help are due to John Riordan, who followed the manuscript through two versions. Numerous corrections and improvements were suggested by my wife who read both the manuscript and proof.
The author is also indebted to K L Chung, M Donsker, and S Goldberg, who read the manuscript and corrected various mistakes; the solutions to the majority of the problems were prepared by S Ooldberg. Finally, thanks are due to Kathryn Hoilenbach for patient and expert typing help; to E Elyash, W Hoffman, and J R Kinney for help in proof-reading.
The general plan, as described in the preface to the first edition, remains unchanged. To accommodate the manifold needs of readers with divergent backgrounds, interests, and degrees of mathematical sophistication, it was necessary frequently to deviate from the main path. The exposition therefore does not always progress from the easy to the difficult; comparatively technical sections appear at the beginning and easy sections in Chapters XV and XVII. Inexperienced readers should not attempt to follow many side lines lest they lose sight of the forest for too many trees. To facilitate orientation and the choice of desirable omissions, stars are used more systematically than in the first edition. The unstarred sections form a self-contained whole in which the starred sections are not used.
A first introduction to the basic notions of probability is contained in Chapters I, V, VI, IX; beginners should cover these with as few digressions as possible. Chapter II is designed to develop the student's technique and probabilistic intuition; some experience in its contents is desirable, but it is not necessary to cover the chapter systematically: it may prove more profitable to return to the elementary illustrations as occasion arises at later stages. For the purposes of a first introduction, the restriction to discrete distributions should not be a serious handicap since the elementary theory of continuous distributions requires only a few words of supplementary explanation.
From Chapter IX an introductory course may proceed directly to Chapter XI, considering generating functions as an example of more general transforms. Chapter XI should be followed by some applications in Chapters XIII (recurrent events) or XII (chain reactions, infinitely divisible distributions). Without generating functions it is possible to turn in one of the following directions: limit theorems and fluctuation theory (Chapters VIII, X, III); stochastic processes (Chapter XVII); random walks (Chapter III and the main part of XIV). These chapters are almost independent of each other. The Markov chains of Chapter XV depend conceptually on recurrent events, but they may be studied independently if the reader is willing to accept without proof the basic ergodic theorem.
Space saved by streamlining made it possible to add new material and to integrate the old third chapter with Chapter II. New emphasis is laid on waiting times, a topic now serving as a unifying thread throughout the book. This emphasis is reflected in the early introduction of waiting times in Chapter II and in the several independent treatments of the first-passage times in random walks.
Chapter III is entirely new. It illustrates the power of combinatorial methods by deriving in an elementary way important results previously obtained by advanced analytical tools. The results concerning fluctuations in coin tossing show that widely held beliefs about the law of large numbers are fallacious. These results are so amazing and so at variance with common intuition that even sophisticated colleagues doubted that coins actually misbehave as theory predicts. The record of a simulated experiment is therefore included in Section 7.
A new stress on the essential unity of recurrent events and Markov chains permitted improvements and simplifications, but at the cost of a change from the terminology of the first edition. I am deeply apologetic for the confusion which is bound to ensue.
Great care has been taken to render the index usable, but it cannot serve as a Who's Who in probability: the proper balance is destroyed by references to all papers that chanced to lead, often indirectly, to the construction of an example or exercise. I regret that sometimes important contributions are quoted in an irrelevant context not indicative of their value.
This edition was prepared under ideal working conditions without interruptions by routine duties. For this ease I must thank the Air Force Office of Scientific Research, Princeton University, and the stimulating hospitality of J Wolfowitz. I have continued to benefit from the helpful criticism of J L Doob. The careful checking of manuscript and proofs by my wife has removed many errors and effects of chance.
In view of this success the second volume is written in the same style. It involves harder mathematics, but most of the text can be read on different levels. The handling of measure theory may illustrate this point. Chapter IV contains an informal introduction to the basic ideas of measure theory and the conceptual foundations of probability. The same chapter lists the few facts of measure theory used in the subsequent chapters to formulate analytical theorems in their simplest form and to avoid futile discussions of regularity conditions. The main function of measure theory in this connection is to justify formal operations and passages to the limit that would never be questioned by a non-mathematician. Readers interested primarily in practical results will therefore not feel any need for measure theory.
To facilitate access to the individual topics the chapters are rendered as self-contained as possible, and sometimes special cases are treated separately ahead of the general theory. Various topics (such as stable distributions and renewal theory) are discussed at several places from different angles. To avoid repetitions, the definitions and illustrative examples are collected in Chapter VI, which may be described as a collection of introductions to the subsequent chapters. The skeleton of the book consists of Chapters V, VIII, and XV. The reader will decide for himself how much of the preparatory chapters to read and which excursions to take.
Experts will find new results and proofs, but more important is the attempt to consolidate and unify the general methodology. Indeed, certain parts of probability suffer from a lack of coherence because the usual grouping and treatment of problems depend largely on accidents of the historical development. In the resulting confusion closely related problems are not recognized as such and simple things are obscured by complicated methods. Considerable simplifications were obtained by a systematic exploitation and development of the best available techniques. This is true in particular for the proverbially messy field of limit theorems (Chapters XVI-XVII). At other places simplifications. were achieved by treating problems in their natural context. For example, an elementary consideration of a particular random walk led to a generalization of an asymptotic estimate which had been derived by hard and laborious methods in risk theory (and under more restrictive conditions independently in queuing).
I have tried to achieve mathematical rigour without pedantry in style. ... I fear that the brief historical remarks and citations do not render justice to the many authors who contributed to probability, but I have tried to give credit wherever possible. The original work is now in many cases superseded by newer research, and as a rule full references are given only to papers to which the reader may want to turn for additional information. For example, no reference is given to my own work on limit theorems, whereas a paper describing observations or theories underlying an example is cited even if it contains no mathematics. Under these circumstances the index of authors gives no indication of their importance for probability theory. Another difficulty is to do justice to the pioneer work to which we owe new directions of research, new approaches, and new methods. Some theorems which were considered strikingly original and deep now appear with simple proofs among more refined results. It is difficult to view such a theorem in its historical perspective and to realize that here as elsewhere it is the first step that counts.