Next: A Generalization of AISBN:
Up: AISBN: Adaptive Importance Sampling
Previous: Heuristic Initialization in AISBN
There are several tunable parameters in the AISBN algorithm. We
base the choice of these parameters on the Central Limit Theorem
(CLT). According to CLT, if Z_{1}, Z_{2}, ..., Z_{n} are
independent and identically distributed random variables with
E(Z_{i}) = and Var
(Z_{i}) = , i = 1, ...,
n, then
= (Z_{1} + ... + Z_{n})/n is approximately
normally distributed when n is sufficiently large. Thus,
P( ^{ . }t) = e^{x2/2}dx .

(11) 
Although this approximation holds when n approaches infinity,
CLT is known to be very robust and lead to excellent
approximations even for small n. The formula of
Equation 11 is an (
, ) Relative Approximation, which is an estimate
of that satisfies
If has been fixed,
where
(z) = e^{x2/2}dx.
Since in our sampling problem, (corresponding to
Pr() in Figure 2) has been fixed, setting
to a smaller value amounts to letting
/ be smaller. So, we can adjust the parameters
based on
/, which can be estimated using
Equation 3. It is also the theoretical intuition
behind our recommendation
w^{k} 1/ in
Section 3.1. While we expect that this should work well
in most networks, no guarantees can be given here  there exist
always some extreme cases in sampling algorithms in which no good
estimate of variance can be obtained.
Next: A Generalization of AISBN:
Up: AISBN: Adaptive Importance Sampling
Previous: Heuristic Initialization in AISBN
Jian Cheng
20001001