476 CHAPTER 8 Discrete Probability
theory is used to design and to analyze the performance of algorithms that are run on
computers. As just one example, suppose that a certain algorithm for alphabetizing a list of
n names performs c • n^2 comparisons if the input to the program gives the names in reverse
order but only c • n comparisons if the input happens to give the names in order. Since the
performance differs greatly in these two situations, we might ask how many comparisons
are required on average, assuming that each of the n! permutations of the names is equally
likely to occur. If it is not easy to compute the average number of comparisons required,
then we might try the algorithm on several randomly chosen permutations of n names to
get an estimate of the algorithm's average performance. To do this, we would want to know
how to generate permutations at random using a computer.
Many of the examples in this chapter will be about dice, cards, and coin-flipping exper-
iments, because these provide simple and interesting ways to illustrate the basic concepts
of probability. Familiarity with basic probability concepts applied to these situations will
enable the reader to extend these ideas to other contexts, because they also arise in com-
puting courses, such as Artificial Intelligence, Algorithm Design and Analysis, Software
Engineering, Graphics, Networks, and Simulation.
Statements about probability and chance have many possible interpretations. For ex-
ample, what do we mean when we say that we have a 50-50 chance of getting heads when
we flip a coin? We may have in mind that there is no reason for the experiment to favor
either outcome, so we assign equal likelihood to the two outcomes and arrive at a 50%
chance for each. Perhaps we imagine that if we continue flipping the coin, we would get
heads about 50% of the time. (Nevertheless, we would be surprised to get heads exactly
500 times after 1000 repetitions of the experiment.) This so-called frequency interpretation
breaks down, however, when we consider an experiment that is not repeatable. If we say
that a certain daredevil has a 50% chance of surviving a plunge over Niagara Falls in a
barrel, do we mean that survival would be the outcome about half the time if the experi-
ment could be repeated many times under exactly the same conditions? And what do we
mean by "about half the time" and "exactly the same conditions"? Perhaps we mean that
we would be willing to bet "even money" on the daredevil-that is, we would stand to lose
or gain the same amount-depending on the outcome.
Probability theory has a philosophical and interpretive aspect that is not found in most
other branches of mathematics. No one has been able to give a single, precise definition of
probability that everyone agrees on, but it is possible to give mathematical rules for com-
bining probabilities once they are assigned. Everyone can agree on these rules, and they
form the basis for the mathematical subject of probability theory. One of the challenges
of this subject is to be alert to the difference between the following: making mathematical
deductions based on the axioms of probability, and reasoning based on common sense and
everyday experience.8.11 Introductory Examples
To begin the mathematical treatment of probability theory, we introduce some basic termi-
nology informally. Let us start by considering a familiar situation. Suppose that we roll a
pair of dice, A and B, and that we are interested in our chances of getting the sum of the
spots (also called pips) on the top faces to be a certain one of the values 2 through 12. This
is a typical instance of the following situation: There is a process (rolling the dice) with a