Graphics Reference
In-Depth Information
be equally likely to be the output of any invocation of
rand
. We call
randb
a
uniform random variable,
because all of its outputs are equally likely.
Note that if
randb
is invoked a variable number of times in the program, then
some elements of the program's probability space will have greater probability
than others.
Inline Exercise 30.4:
Suppose we modify our coin-flipping program to only
flip twice if the first coin came up heads, as in Listing 30.1. Describe a probabil-
ity space for this code, and compute the expected value of the random variable
headcount
.
Listing 30.1: A program in which
randb
is invoked either once or twice.
1
2
3
4
5
6
headcount
=0
if (randb()):
// first coin flip
headcount
++
if (randb()):
// second coin flip
headcount
++
return
headcount
The values taken on by a random variable
X
may be clustered around the mean
X
, or widely dispersed. This dispersion is measured by the
variance,
the mean-
square average of
X
(
s
)
X
. Formally, the variance is
−
X
)
2
]
,
Var
[
X
]=
E
[(
X
−
(30.15)
which can be simplified (see Exercise 30.9) to
E
[
X
2
]
E
[
X
]
2
.
The units of variance are the units of
X
, squared; the square root of the variance
(known as the
standard deviation
) has the same units as
X
, and sometimes makes
better intuitive sense. As a useful rule of thumb, three-fourths of the values of
X
lie within two standard deviations of
X
.
Variance is
not
linear, but has the property that
Var
[
cX
+
d
]=
c
2
Var
[
X
]
for
any real numbers
c
and
d
.
The random variables
X
and
Y
are called
independent
if
−
Pr
{
X
=
x
and
Y
=
y
}
=
Pr
{
X
=
x
}·
Pr
{
Y
=
y
}
(30.16)
for every
x
and
y
in
R
. For instance, in the experiment where we flip an unbiased
coin twice, if
X
is the number of heads that show up on the first coin flip (either 0
or 1), and
Y
is the number of heads that show up on the second, then our experi-
ence tells us that
X
and
Y
are independent, that is, the probability of two heads in a
row is
1
4
. On the other hand, the variables
X
and
X
are distinctly
not
independent.
We'll generally assume that any two values produced by calls to
randb
or
rand
or other such functions correspond to independent random variables.
The important properties for
independent
random variables are
•
E
[
XY
]=
E
[
X
]
E
[
Y
]
•
Var
[
X
+
Y
]=
Var
[
X
]+
Var
[
Y
]
Returning to the coin-flip experiment and the associated program, we imple-
mented the two random variables via calls to a single random-number-generating
routine,
randb
. We call these random variables samples from the distribution
in which heads and tails have equal probability. The idea is that
randb
can be