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.
30.3.2 Expected Value
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
 
 
 
Search WWH ::




Custom Search