Graphics Reference
In-Depth Information
This function takes on real values (either 0, 1, or 2), and it's defined on the set
S
;
hence, it's a random variable. As in this example, we'll use the letter
X
to denote
nearly every random variable in this chapter.
A random variable can be used to define events. For example, the set of out-
comes
s
for which
X
(
s
)=
1, that is,
E
=
{
s
∈
S
:
X
(
s
)=
1
}
and
(30.4)
=
{
ht
,
th
}
,
(30.5)
is an event with probability
2
. We write this
Pr
=
2
, that is, we use the
predicate
X
=
1 as a shorthand for the event defined by that predicate.
Let's look at a piece of code for simulating the experiment represented by the
formalities above:
{
X
=
1
}
1
2
3
4
5
6
7
headcount
=0
if (randb()):
// first coin flip
headcount
++
if (randb()):
// second coin flip
headcount
++
return
headcount
Here we're assuming the existence of a
randb()
procedure that returns a boolean,
which is
true
half the time.
How is this simulation related to the formal probability theory? After all, when
we run the program the returned value will be either 0, 1, or 2, not some mix of
these. (If we run it a second time, we may get a different value, of course.)
The relationship between the program and the abstraction is this:
Imagine the set
S
of
all possible executions
of the program, declaring two
executions to be the same if the values returned by
randb
are pairwise identical.
This means that there are four possible program executions, in which the two
randb()
invocations return
TT
,
TF
,
FT
, and
FF
. Our belief and experience is that
these four executions are equally likely, that is, each occurs just about one-quarter
of the time when we run the program many times.
The analogy is now clear: The set of possible program executions, with associ-
ated probabilities, is a probability space; the variables in the program that depend
on
randb
invocations are random variables. This is a quite clever piece of mathe-
matical modeling of computation. You should be certain that you understand it.
There's nice formalism in which a procedure that invokes
randb
-like func-
tions is replaced by one with an extra argument, which is a long string of bits; these
bits are used instead of
randb
calls. This revised procedure is
deterministic;
it
becomes randomized only when we invoke it with a sequence of random bits. In
this formalism, the probability space is the set of all possible bit strings that are
provided as the extra argument.
The
expectation
or
expected value
or
mean
of a random variable
X
on a finite
probability space
S
is defined as
E
[
X
]=
s
p
(
s
)
X
(
s
)
.
(30.6)
∈
S