Page 466 - Discrete Mathematics and Its Applications

CH A P TER

7 Discrete Probability

7.1 An ombinatorics and probability theory share common origins. The theory of probability was
Introduction to Cfirst developed more than 300 years ago, when certain gambling games were analyzed.
Discrete Although probability theory was originally invented to study gambling, it now plays an essential
Probability role in a wide variety of disciplines. For example, probability theory is extensively applied in
the study of genetics, where it can be used to help understand the inheritance of traits. Of course,
7.2 Probability
probability still remains an extremely popular part of mathematics because of its applicability
Theory
to gambling, which continues to be an extremely popular human endeavor.
7.3 Bayes’
In computer science, probability theory plays an important role in the study of the com-
Theorem
plexity of algorithms. In particular, ideas and techniques from probability theory are used to
7.4 Expected Value determine the average-case complexity of algorithms. Probabilistic algorithms can be used to
and Variance solve many problems that cannot be easily or practically solved by deterministic algorithms.
In a probabilistic algorithm, instead of always following the same steps when given the same
input, as a deterministic algorithm does, the algorithm makes one or more random choices,
which may lead to different output. In combinatorics, probability theory can even be used to
show that objects with certain properties exist. The probabilistic method, a technique in com-
binatorics introduced by Paul Erd˝os and Alfréd Rényi, shows that an object with a specified
property exists by showing that there is a positive probability that a randomly constructed object
has this property. Probability theory can help us answer questions that involve uncertainty, such
as determining whether we should reject an incoming mail message as spam based on the words
that appear in the message.

7.1 An Introduction to Discrete Probability

Introduction

Probability theory dates back to 1526 when the Italian mathematician, physician, and gambler
Girolamo Cardano wrote the first known systematic treatment of the subject in his book Liber
de Ludo Aleae (Book on Games of Chance). (This book was not published until 1663, which
may have held back the development of probability theory.) In the seventeenth century the
French mathematician Blaise Pascal determined the odds of winning some popular bets based
on the outcome when a pair of dice is repeatedly rolled. In the eighteenth century, the French
mathematician Laplace, who also studied gambling, defined the probability of an event as the
number of successful outcomes divided by the number of possible outcomes. For instance, the
probability that a die comes up an odd number when it is rolled is the number of successful
outcomes—namely, the number of ways it can come up odd—divided by the number of possible
outcomes—namely, the number of different ways the die can come up. There are a total of
six possible outcomes—namely, 1, 2, 3, 4, 5, and 6—and exactly three of these are successful
outcomes—namely, 1, 3, and 5. Hence, the probability that the die comes up an odd number is
3/6 = 1/2. (Note that it has been assumed that all possible outcomes are equally likely, or, in
other words, that the die is fair.)
Inthissectionwewillrestrictourselvestoexperimentsthathavefinitelymany,equallylikely,
outcomes. This permits us to use Laplace’s definition of the probability of an event. We will
continue our study of probability in Section 7.2, where we will study experiments with finitely
many outcomes that are not necessarily equally likely. In Section 7.2 we will also introduce

445