xii Preface
Course
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, contain-
ing solutions to all exercises, is available free to instructors who adopt the book for
class.
Organization
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 vari-
able 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 con-
ditional 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 count-
ing process. In particular, we study a kind of counting process known as a Poisson
process. The intimate relationship between this process and the exponential distribu-
tion is discussed. New derivations for the Poisson and nonhomogeneous Poisson
processes are discussed. Examples relating to analyzing greedy algorithms, minimiz-
ing highway encounters, collecting coupons, and tracking the AIDS virus, as well as
