Discrete Probability
Expressions of chance and probability are common in everyday language and thinking. We
speak of the chance of rain, the probability of getting heads when flipping a coin, and the
chance of surviving a disease. We may wonder which of several moves in a board game
is most likely to succeed or whether responding to a magazine's contest is worth the price
of a stamp. This chapter makes these ideas mathematically precise so that we can reason
about them and compute with them.
The chapter contains discussion of five major topics sections. The first gives the formal
definition of a probability density function and shows how to use the frequency of occur-
rence for an outcome in defining a probability density function. The probability of unions
and intersections of events are also discussed. The second introduces the idea of interpret-
ing events in sample spaces as events in the product of these sample spaces. The important
application to Bernoulli trial processes is discussed, and the relationship between the prob-
abilities on individual sample spaces and the probability in the cross product of sample
spaces is explored. The third deals with the important ideas of independent events and con-
ditional probabilities. Independence tells when the probabilities of two events do not affect
each other. Conditional probability gives insight regarding how probabilities can change if
one knows that some outcome has occurred. For example, asking the probability of flipping
a head using two fair coins is a question whose answer may change if new information is
received (for example, the first coin landed tails). The last two topics deal with random
variables, which are in fact functions defined on a sample space that is endowed with a
probability density function. We see how a probability density function can be associated
with a random variable, and we ask questions about what values can be expected from a
large number of repetitions of an experiment and how likely it is that these values deviate
very much from their average.W Ideas of Chance in Computer Science
Ideas of chance arise in computer science in at least two important and related ways.
First, many systems (for example, the stock market, traffic flow in a network, ecological
systems) behave in complex ways that have seemingly random aspects. Probability theory
is used to create models for the computer simulation of such systems. Second, probability
475