Graphics Reference
In-Depth Information
→
R
is a real-valued function, and
X
∼
U
(
a
,
b
)
is
a uniform random variable on the interval
[
a
,
b
]
, then
(
b
Theorem: If
f
:[
a
,
b
]
−
a
)
f
(
X
)
is a random
variable whose expected value is
a
)
f
(
x
)] =
b
a
E
[(
b
−
f
(
x
)
dx
.
(30.48)
This is a big result!
It says that we can use a randomized algorithm to compute
the value of an integral, at least if we run the code often enough and average the
results. The remainder of this chapter amplifies and improves this result.
The proof of the theorem is simple. The pdf for
X
is
p
X
(
x
)=
1
b
−
a
,sothe
expected value for
(
b
−
a
)
f
(
X
)
is
a
)
f
(
X
)] =
b
a
E
[(
b
−
(
b
−
a
)
f
(
x
)
p
X
(
x
)
dx
;
(30.49)
=
b
a
1
(
b
−
a
)
f
(
x
)
dx
;
(30.50)
b
−
a
=
b
a
f
(
x
)
dx
.
(30.51)
Listing 30.4 shows the corresponding program.
Listing 30.4: Estimating the integral of the real-valued function f on an interval.
1
2
3
4
5
integrate1(double
*
f (double), double a, double b):
// estimate the integral of f on [a, b]
x = uniform(a, b)
// a random real number in [a, b]
y=(
*
f)(x)
*
(b-a)
return y
The value
y
returned by the program is a random variable that's an estimate of
the integral of
f
. The average quality of this estimate is measured by the variance
of
y
, which depends on the function
f
.If
f
is constant, for example, the estimate is
always exactly correct; if
f
has enormous variations (e.g.,
f
(
x
)=
10000
sin(
2
π
x
b
−
a
)
),
then the estimate is highly likely to be very bad. While it's true that if we run
the program many times and average the results, we'll get something close to the
correct value of the integral, any
individual
run of the program is likely to produce
a value that's very far from the correct value.
Inline Exercise 30.8:
Implement the small program above in your favorite
language, and apply it to estimate the average value of a few functions—say,
f
(
x
)=
4,
f
(
x
)=
x
2
, and
f
(
x
)=
sin
(
π
x
)
on the interval
[
0, 2
π
]
.
In general, when we think of a random variable as providing an estimate of
some value, low variance is good and high variance is bad.
Let's now improve our estimation of the integral by taking
two
iid samples
(see Listing 30.5).
