This text is intended as an introduction to elementary probability theory and stochastic processes. It is particularly well suited for those wanting to see how probability theory can be applied to the study of phenomena in fields such as engineering, computer science,management science, the physical and social sciences, and operations research.
It is generally felt that there are two approaches to the study of probability theory.One approach is heuristic and nonrigorous and attempts to develop in the student an intuitive feel for the subject that enables him or her to “think probabilistically.” The other approach attempts a rigorous development of probability by using the tools of measure theory. It is the first approach that is employed in this text. However, because it is extremely important in both understanding and applying probability theory to be able to “think probabilistically,” this text should also be useful to students interested primarily in the second approach.
New to This Edition
The eleventh edition includes new text material, examples, and exercises. Some of the key new examples are the following.
• Example 3.6, which derives the density function of the t-random variable.
• Example 3.32, which analyzes a serve and rally competition where the winner of a rally is the server for the next point.
• Example 5.19, which considers a one lane road with no overtaking.
• Example 6.22, which uses the reverse chain to analyze a sequential queuing system.
• Example 7.20, which analyzes a system where both people and buses randomly arrive at a bus stop.
New sections include
• Section 4.4, on the long-run proportions and limiting probabilities of a Markov chain.
• Section 5.5, on random intensity functions and Hawkes processes.
• Section 6.7, on the reverse chain of continuous-time Markov chains
• Section 10.5, which analyzes the maximum variable of a Brownian motion with drift process.
We have also tried to simplify and clarify existing material wherever possible.Examples include a new proof of the result that the number of events of a nonhomogeneous Poisson process that occur in an interval is Poisson distributed, as well as the introduction of Wald's Equation (Theorem 7.2) and its subsequent use in proving the elementary renewal theorem.
Ideally, this text would be used in a one-year course in probability models. Other possible courses would be a one-semester course in introductory probability theory (involving Chapters 1–3 and parts of others) or a course in elementary stochastic processes. The textbook is designed to be flexible enough to be used in a variety of possible courses. For example, I have used Chapters 5 and 8, with smatterings from Chapters 4 and 6, as the basis of an introductory course in queueing theory.
Examples and Exercises
Many examples are worked out throughout the text, and there are also a large number of exercises to be solved by students. More than 100 of these exercises have been starred and their solutions provided at the end of the text. These starred problems can be used for independent study and test preparation. An Instructor’s Manual, containing solutions to all exercises, is available free to instructors who adopt the book for class.
Chapters 1 and 2 deal with basic ideas of probability theory. In Chapter 1 an axiomatic framework is presented, while in Chapter 2 the important concept of a random variable is introduced. Section 2.6.1 gives a simple derivation of the joint distribution of the sample mean and sample variance of a normal data sample.
Chapter 3 is concerned with the subject matter of conditional probability and conditional expectation. “Conditioning” is one of the key tools of probability theory, and it is stressed throughout the book. When properly used, conditioning often enables us to easily solve problems that at first glance seem quite difficult. The final section of this chapter presents applications to (1) a computer list problem, (2) a random graph,and (3) the Polya urn model and its relation to the Bose-Einstein distribution. Section 3.6.5 presents k -record values and the surprising Ignatov’s theorem.
In Chapter 4 we come into contact with our first random, or stochastic, process,known as a Markov chain, which is widely applicable to the study of many real-world phenomena. Applications to genetics and production processes are presented. The concept of time reversibility is introduced and its usefulness illustrated. Section 4.5.3 presents an analysis, based on random walk theory, of a probabilistic algorithm for the satisfiability problem. Section 4.6 deals with the mean times spent in transient states by a Markov chain. Section 4.9 introduces Markov chain Monte Carlo methods.In the final section we consider a model for optimally making decisions known as a Markovian decision process.
In Chapter 5 we are concerned with a type of stochastic process known as a counting process. In particular, we study a kind of counting process known as a Poisson process. The intimate relationship between this process and the exponential distribution is discussed. New derivations for the Poisson and nonhomogeneous Poisson processes are discussed. Examples relating to analyzing greedy algorithms,minimizing highway encounters, collecting coupons, and tracking the AIDS virus, as well as material on compound Poisson processes, are included in this chapter. Section 5.2.4 gives a simple derivation of the convolution of exponential random variables.
Chapter 6 considers Markov chains in continuous time with an emphasis on birth and death models. Time reversibility is shown to be a useful concept, as it is in the study of discrete-time Markov chains. Section 6.7 presents the computationally important technique of uniformization.
Chapter 7, the renewal theory chapter, is concerned with a type of counting process more general than the Poisson. By making use of renewal reward processes,limiting results are obtained and applied to various fields. Section 7.9 presents new results concerning the distribution of time until a certain pattern occurs when a sequence of independent and identically distributed random variables is observed.In Section 7.9.1, we show how renewal theory can be used to derive both the mean and the variance of the length of time until a specified pattern appears, as well as the mean time until one of a finite number of specified patterns appears. In Section 7.9.2, we suppose that the random variables are equally likely to take on any of m possible values, and compute an expression for the mean time until a run of m distinct values occurs. In Section 7.9.3, we suppose the random variables are continuous and derive an expression for the mean time until a run of m consecutive increasing values occurs.
Chapter 8 deals with queueing, or waiting line, theory. After some preliminaries dealing with basic cost identities and types of limiting probabilities, we consider exponential queueing models and show how such models can be analyzed. Included in the models we study is the important class known as a network of queues. We then study models in which some of the distributions are allowed to be arbitrary.Included are Section 8.6.3 dealing with an optimization problem concerning a single server, general service time queue, and Section 8.8, concerned with a single server, general service time queue in which the arrival source is a finite number of potential users.
Chapter 9 is concerned with reliability theory. This chapter will probably be of greatest interest to the engineer and operations researcher. Section 9.6.1 illustrates a method for determining an upper bound for the expected life of a parallel system of not necessarily independent components and Section 9.7.1 analyzes a series structure reliability model in which components enter a state of suspended animation when one of their cohorts fails.
Chapter 10 is concerned with Brownian motion and its applications. The theory of options pricing is discussed. Also, the arbitrage theorem is presented and its relationship to the duality theorem of linear programming is indicated. We show how the arbitrage theorem leads to the Black–Scholes option pricing formula.
Chapter 11 deals with simulation, a powerful tool for analyzing stochastic models that are analytically intractable. Methods for generating the values of arbitrarily distributed random variables are discussed, as are variance reduction methods for increasing the efficiency of the simulation. Section 11.6.4 introduces the valuable simulation technique of importance sampling, and indicates the usefulness of tilted distributions when applying this method.
We would like to acknowledge with thanks the helpful suggestions made by the many reviewers of the text. These comments have been essential in our attempt to continue to improve the book and we owe these reviewers, and others who wish to remain anonymous, many thanks:
Mark Brown, City University of New York
Zhiqin Ginny Chen, University of Southern California
Tapas Das, University of South Florida
Israel David, Ben-Gurion University
Jay Devore, California Polytechnic Institute
Eugene Feinberg, State University of New York, Stony Brook
Ramesh Gupta, University of Maine
Marianne Huebner, Michigan State University
Garth Isaak, Lehigh University
Jonathan Kane, University of Wisconsin Whitewater
Amarjot Kaur, Pennsylvania State University
Zohel Khalil, Concordia University
Eric Kolaczyk, Boston University
Melvin Lax, California State University, Long Beach
Jean Lemaire, University of Pennsylvania
Andrew Lim, University of California, Berkeley
George Michailidis, University of Michigan
Donald Minassian, Butler University
Joseph Mitchell, State University of New York, Stony Brook
Krzysztof Osfaszewski, University of Illinois
Erol Pekoz, Boston University
James Propp, University of Massachusetts, Lowell
Anthony Quas, University of Victoria
Charles H. Roumeliotis, Proofreader
David Scollnik, University of Calgary
Mary Shepherd, Northwest Missouri State University
Galen Shorack, University of Washington, Seattle
Marcus Sommereder, Vienna University of Technology
Osnat Stramer, University of Iowa
Gabor Szekeley, Bowling Green State University
Marlin Thomas, Purdue University
Henk Tijms, Vrije University
Zhenyuan Wang, University of Binghamton
Ward Whitt, Columbia University
Bo Xhang, Georgia University of Technology
Julie Zhou, University of Victoria