RES for non-Markovian repairable fault trees
469
Rare Event Simulation (RES). res techniques [35] increase the amount
of traces that observe the rare event, e.g. a top level event in an rft. Two
prominent classes of res techniques are importance sampling, which adjusts
the pdf of failures and repairs, and importance splitting (isplit [30]), which
samples more (partial) traces from states that are closer to the rare event. We
focus on isplit due to its flexibility with respect to the probability distributions.
isplit can be efficiently deployed as long as the rare event γ can be described as a nested sequence of less-rare events γ = γ M γ M −1 · · · γ 0 .
This decomposition allows isplit to study the conditional probabilities p k =
Prob(γ k+1 | γ k ) separately, to then compute p = Prob(γ) =
M -1
k=0 Prob(γ k+1 | γ k ).
Moreover, isplit requires all conditional probabilities p k to be much greater
than p, so that estimating each p k can be done efficiently with smc.
The key idea behind isplit is to define the events γ k via a so called importance function I : S → N that assigns an importance to each state s ∈ S. The
higher the importance of a state, the closer it is to the rare event γ M . Event γ k
collects all states with importance at least k , for certain sequence of threshold
levels 0 = 0 < < 1 < · · · < < M . Formally: γ k = {s ∈ S | I (s) k }.
To exploit the importance function I in the simulation procedure, isplit
samples more (partial) traces from states with higher importance. Two wellknown methods are deployed and compared in this paper: Fixed Effort and
restart. Fixed Effort (fe [19]) samples a predefined amount of traces in
each region S k = γ k \ γ k+1 = {s ∈ S | k+1 > I(s) k }. Thus, starting at γ 0
it first estimates the proportion of traces that reach γ 1 , i.e. p 0 = Prob(γ 1 | γ 0 ) =
Prob(S 0 ). Next, from the states that reached γ 1 new traces are generated to
estimate p 1 = Prob(S 1 ), and so on until p M . Fixed Effort thus requires that
(i) each trace has a clearly defined “end,” so that estimations of each p k finish
with probability 1, and (ii) all rare events reside in the uppermost region.
(a) fe5 for Prob(¬ U )
(b) rstes for UNRELT
Fig. 3: Importance Splitting algorithms Fixed Effort & restart
Example. Fig. 3a shows Fixed Effort estimating the probability to visit states
labelled before others labelled . States have importance >13, and thresholds 1 , , 2 = 4, 10 partition the state space in regions {S i }
2
i=0 s.t. all ∈ S 2 .
The effort is 5 simulations per region, for all regions: we call this algorithm fe 5 .
469
Rare Event Simulation (RES). res techniques [35] increase the amount
of traces that observe the rare event, e.g. a top level event in an rft. Two
prominent classes of res techniques are importance sampling, which adjusts
the pdf of failures and repairs, and importance splitting (isplit [30]), which
samples more (partial) traces from states that are closer to the rare event. We
focus on isplit due to its flexibility with respect to the probability distributions.
isplit can be efficiently deployed as long as the rare event γ can be described as a nested sequence of less-rare events γ = γ M γ M −1 · · · γ 0 .
This decomposition allows isplit to study the conditional probabilities p k =
Prob(γ k+1 | γ k ) separately, to then compute p = Prob(γ) =
M -1
k=0 Prob(γ k+1 | γ k ).
Moreover, isplit requires all conditional probabilities p k to be much greater
than p, so that estimating each p k can be done efficiently with smc.
The key idea behind isplit is to define the events γ k via a so called importance function I : S → N that assigns an importance to each state s ∈ S. The
higher the importance of a state, the closer it is to the rare event γ M . Event γ k
collects all states with importance at least k , for certain sequence of threshold
levels 0 = 0 < < 1 < · · · < < M . Formally: γ k = {s ∈ S | I (s) k }.
To exploit the importance function I in the simulation procedure, isplit
samples more (partial) traces from states with higher importance. Two wellknown methods are deployed and compared in this paper: Fixed Effort and
restart. Fixed Effort (fe [19]) samples a predefined amount of traces in
each region S k = γ k \ γ k+1 = {s ∈ S | k+1 > I(s) k }. Thus, starting at γ 0
it first estimates the proportion of traces that reach γ 1 , i.e. p 0 = Prob(γ 1 | γ 0 ) =
Prob(S 0 ). Next, from the states that reached γ 1 new traces are generated to
estimate p 1 = Prob(S 1 ), and so on until p M . Fixed Effort thus requires that
(i) each trace has a clearly defined “end,” so that estimations of each p k finish
with probability 1, and (ii) all rare events reside in the uppermost region.
(a) fe5 for Prob(¬ U )
(b) rstes for UNRELT
Fig. 3: Importance Splitting algorithms Fixed Effort & restart
Example. Fig. 3a shows Fixed Effort estimating the probability to visit states
labelled before others labelled . States have importance >13, and thresholds 1 , , 2 = 4, 10 partition the state space in regions {S i }
2
i=0 s.t. all ∈ S 2 .
The effort is 5 simulations per region, for all regions: we call this algorithm fe 5 .