Graphics Reference
In-Depth Information
to Programs
A
discrete probability space
is a nonempty finite
1
set
S
together with a real-
valued function
p
:
S
→
R
with two properties.
∈
S
,wehave
p
(
s
)
≥
1. For every
s
0, and
hh
ht
1/4
2.
s
∈
S
p
(
s
)=
1.
The first property is called non-negativity, and the second is called normality. The
function
p
is called the
probability mass function,
and
p
(
s
)
is the probability
mass for
s
(or, informally, the probability of
s
). The intuition is that
S
represents a
set of outcomes of some experiment, and
p
(
s
)
is the probability of outcome
s
.For
example,
S
might be the set of four strings
hh
,
ht
,
th
,
tt
, representing the heads-or-
tails status of tossing a coin twice (see Figure 30.4). If the coin is fair, we associate
probability
4
1/4
tt
th
1/4
1/4
Figure 30.4: A four-element
probability space, with uniform
probabilities, shown as fractions
in red.
to each outcome.
Inline Exercise 30.1:
Explain why, in a discrete probability space
(
S
,
p
)
,we
have 0
≤
p
(
s
)
≤
∈
S
. The first inequality follows from the first
defining property of
p
. What about the second?
1 for every
s
hh
ht
1/4
1/4
An
event
is a subset of a probability space. The
probability
of an event
(see Figure 30.5) is the sum of the probability masses of the elements of the event,
that is,
tt
th
1/4
1/4
=
s
∈
E
Figure 30.5: An event (“At least
one 'tails' ”) with probability
Pr
{
E
}
p
(
s
)
.
(30.1)
3
4
.
Inline Exercise 30.2:
Prove that if
E
1
and
E
2
are events in the finite probability
space
S
, and
E
1
∩
.This
generalizes, by induction, to show that for any
finite
set of mutually disjoint
events,
Pr
E
2
=
∅
, then
Pr
{
E
1
∪
E
2
}
=
Pr
{
E
1
}
+
Pr
{
E
2
}
{
i
=
i
=
1
Pr
. One of the axioms of probability theory is
that this relation holds even for an infinite, but
countable,
collection of disjoint
events when we're working with continua, like
[
0, 1
]
or
R
, rather than a discrete
probability space.
E
i
}
{
E
i
}
A
random variable
is a
function,
usually denoted by a capital letter, from a
probability space to the real numbers:
X
:
S
→
R
.
(30.2)
The terminology is both suggestive and misleading. The function
X
is not a vari-
able; it's a real-valued function. It's not
random,
either:
X
(
s
)
is a single real num-
ber for any outcome
s
S
. On the other hand,
X
serves as a
model
for something
random. To give a concrete example, consider the four-element probability space
described earlier. There's a random variable
X
defined on that space by the notion
“How many heads came up?” or, more formally, “How many
h
s does the string
contain?” To be explicit, we can define the random variable
X
by
X
(
hh
)=
2
∈
X
(
ht
)=
1
X
(
th
)=
1
X
(
tt
)=
0.
(30.3)
1. Countably infinite sets such as the integers are often included in the study of discrete
probability, but we'll have no need for them, and restrict ourselves to the finite case.