Finite Improbability Generator
485
2 Rare Event Simulation
res methods make more traces visit the rare states that satisfy a property ϕ (the
set S ϕ ), to reduce the variance of smc estimators. For a fixed budget of traces
n, this yields more precise cis than classical Monte Carlo simulation (cmc).
FIG implements importance splitting: a main res method that can work on
non-Markovian systems without special considerations. isplit splits the states
of the model into layers that wrap S ϕ like an onion. Reaching a state in S ϕ from
the surface is then broken down into many steps. The i-th step estimates the
conditional probability to reach (the inner) layer i + 1 from (the outer) layer i.
This stepwise estimation of conditional probabilities can be much more efficient
than trying to go in one leap from the surface of the onion to its core [20].
Formally, let S be the states of a model with initial states S 0 and rare states
S ϕ . isplit works on a partition
M
i=0 S i = S, where S ϕ = S M . To estimate the
probability γ = Prob(S ϕ | S 0 ), each conditional probability γ i = Prob(S i | S i−1 )
is estimated separately via cmc. Then simply ˆ
γ =
M
i=1 ˆ
γ i ≈
M
i=1 γ i = γ.
This approach is correct, i.e. it yields an unbiased estimator ˆ
γ
n→∞
− −−− → γ.
However, it is efficient iff ∀
M
i=1 . γ i γ, which depends on how the S i layers
where chosen. For this, an importance function f : S → R 0 and thresholds
i ∈ R 0 are defined: then S i = {s ∈ S | i f (s) < < i+1 }, where 0 = 0,
and S ϕ are the states with highest importance, i.e. f (s) M . The efficiency of
isplit is thus delegated to the choice of { i }
M
i=1 and the importance function f .
These choices are the key challenge in isplit [20]. Theoretical developments
assume f is given [12, 8], and applications define it ad hoc via (res and domain)
expert knowledge [30, 27]. Yet there is one general rule: importance must be
proportional to the probability of reaching S ϕ . Thus for s, s
∈ S, if a trace
that visits s
is more likely to observe a rare state, one wants f (s) f (s
). This
means that f depends both on the model M and the property ϕ that define S ϕ .
FIG, an smc tool, exploits the formal definitions of M and ϕ to derive f and
{ i }
M
i=1 so as to reflect this rule. For this, FIG runs bfs from S ϕ on the (inverted) transitions of M. This computes the number-of-transitions distance from each
state to S ϕ . The heuristic importance function of FIG, f
, is the inverse of this
distance, stored as an array the size of S. To avoid the state explosion FIG works
on modular formalisms, deriving local f
i for the M i whose parallel composition
forms M. f
is an aggregation of these functions, e.g. adding the f
i of every M i
with variables in ϕ. Details are in [2] and also in [5], where the difference with
the (later) implementation in modes is that FIG uses the dnf of ϕ.
f
is solely based on the number-of-transitions distance. Stochastic behaviour
of M omitted by f
, such as probabilistic labels in the transitions, is captured in
the thresholds i . For this, FIG runs short simulations that start from S 0 . Say K 1
out of N simulations visit states with importance i 1 > i 0 = f
(S 0 ). Then, 1 out
of e 1 =
N
K1
simulations are expected to reach threshold 1 = i 1 . Next, repeat
this procedure starting from states with importance i 1 to choose 2 and e 2 . Etc.
Such threshold-selection algorithms (see Sec. 4) are fully described in [4].
Thus, just from M and ϕ, FIG enables isplit by computing f
and { i , e i }
M
i=1 .
485
2 Rare Event Simulation
res methods make more traces visit the rare states that satisfy a property ϕ (the
set S ϕ ), to reduce the variance of smc estimators. For a fixed budget of traces
n, this yields more precise cis than classical Monte Carlo simulation (cmc).
FIG implements importance splitting: a main res method that can work on
non-Markovian systems without special considerations. isplit splits the states
of the model into layers that wrap S ϕ like an onion. Reaching a state in S ϕ from
the surface is then broken down into many steps. The i-th step estimates the
conditional probability to reach (the inner) layer i + 1 from (the outer) layer i.
This stepwise estimation of conditional probabilities can be much more efficient
than trying to go in one leap from the surface of the onion to its core [20].
Formally, let S be the states of a model with initial states S 0 and rare states
S ϕ . isplit works on a partition
M
i=0 S i = S, where S ϕ = S M . To estimate the
probability γ = Prob(S ϕ | S 0 ), each conditional probability γ i = Prob(S i | S i−1 )
is estimated separately via cmc. Then simply ˆ
γ =
M
i=1 ˆ
γ i ≈
M
i=1 γ i = γ.
This approach is correct, i.e. it yields an unbiased estimator ˆ
γ
n→∞
− −−− → γ.
However, it is efficient iff ∀
M
i=1 . γ i γ, which depends on how the S i layers
where chosen. For this, an importance function f : S → R 0 and thresholds
i ∈ R 0 are defined: then S i = {s ∈ S | i f (s) < < i+1 }, where 0 = 0,
and S ϕ are the states with highest importance, i.e. f (s) M . The efficiency of
isplit is thus delegated to the choice of { i }
M
i=1 and the importance function f .
These choices are the key challenge in isplit [20]. Theoretical developments
assume f is given [12, 8], and applications define it ad hoc via (res and domain)
expert knowledge [30, 27]. Yet there is one general rule: importance must be
proportional to the probability of reaching S ϕ . Thus for s, s
∈ S, if a trace
that visits s
is more likely to observe a rare state, one wants f (s) f (s
). This
means that f depends both on the model M and the property ϕ that define S ϕ .
FIG, an smc tool, exploits the formal definitions of M and ϕ to derive f and
{ i }
M
i=1 so as to reflect this rule. For this, FIG runs bfs from S ϕ on the (inverted) transitions of M. This computes the number-of-transitions distance from each
state to S ϕ . The heuristic importance function of FIG, f
, is the inverse of this
distance, stored as an array the size of S. To avoid the state explosion FIG works
on modular formalisms, deriving local f
i for the M i whose parallel composition
forms M. f
is an aggregation of these functions, e.g. adding the f
i of every M i
with variables in ϕ. Details are in [2] and also in [5], where the difference with
the (later) implementation in modes is that FIG uses the dnf of ϕ.
f
is solely based on the number-of-transitions distance. Stochastic behaviour
of M omitted by f
, such as probabilistic labels in the transitions, is captured in
the thresholds i . For this, FIG runs short simulations that start from S 0 . Say K 1
out of N simulations visit states with importance i 1 > i 0 = f
(S 0 ). Then, 1 out
of e 1 =
N
K1
simulations are expected to reach threshold 1 = i 1 . Next, repeat
this procedure starting from states with importance i 1 to choose 2 and e 2 . Etc.
Such threshold-selection algorithms (see Sec. 4) are fully described in [4].
Thus, just from M and ϕ, FIG enables isplit by computing f
and { i , e i }
M
i=1 .