Graphics Reference
In-Depth Information
repeat
N
times:
s
=
a path in the FSA from state 0 to state 3, so
s(0) = 0.
(
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
i
,
value
)=
estimate
(
s
)
S
i
+=
value
;
return
(
S
1
/
N
,
S
2
/
N
)
// from an index sequence s(0) = 0, s(1) = ..., s(k+1) = 3,
// compute one sample of
x
s
(
1
)
; return sample and
s
(
1
)
.
define estimate(
s
):
u
=
s
(1);
// which entry of
x
we're estimating
T
=
1
p
1
u
// accumulated probability
value
=
T
b
u
for
i
=1to
k
−
1
:
j
=
s
i
k
=
s
i
+
1
T
*
=
m
jk
/
p
jk
value
+=
T
·
b
k
return (
u
,
value
)
·
Pause briefly to look at the big picture of this approach to computing
(
1
+
M
+
M
2
+
...
)
b
.
• Depending on the entries
p
0
i
, we may dedicate more or less of our time to
computing one entry of
x
than another.
• Depending on the entries
p
i
3
, the average length of a path may be short or
long. If it's short, but the powers of the matrix
M
don't decrease very fast,
then it may take lots of samples to get good estimates of
x
.
• There's a whole infinity of algorithms encoded in this single algorithm, in
the sense that the transition probabilities
p
ij
can be chosen at will, provided
the rows of
P
sum to one, that
p
ij
=
0 whenever
m
ij
=
0, and that
p
i
3
=
0
whenever
b
i
=
0.
We'll now build up a recursive approach to estimating the solution to
x
=
b
+
Mx
(31.89)
in several steps, all based on the ideas in Chapter 30.
As a warm-up, suppose that you wanted to estimate the sum of two numbers
A
and
B
using a Monte Carlo method. You could write
1
2
3
4
5
6
7
define estimate():
u = uniform(0, 1)
[
0, 1
]
// random number in
with
// uniform distribution
if (u < 0.5):
return A / 0.5
else:
return B / 0.5
This is just an importance-sampled estimate of the sum, with importance values
0.5 and 0.5.
