1. Abridged English Version

1.1 A speed-up method

Computer-based evaluations of the stochastical probability of a rare event are infeasible if is without a second order momentum, and nevertheless very slow otherwise. Accelerating methods have thus been developed, such as importance sampling [1]. Let be a condition for , so: , and the simulations for and are together likely shorter than the original one. Our proposal is to use repeatedly such a triggering by an intermediate state, until the whole length of the simulation is enough reduced to be actually run.

For a Markov chain, the choice of that trigger events may be automated in the following way: let be a threshold frequency, and let be far bigger than but nevertheless such as a -sized simulation, the level 0, remains handy. Thereafter, consider the sub-system consisting of the states whose experimental frequencies are less than and also of the immediate predecessors of such states. One gets: for , and : these frequencies are therefore acceptable estimators.

Then a new simulation is proceeded (the level 1), involving only the system. And so on, until reaching the target state with a conditional frequency greater than . The probability of the rare event is then estimated by the product of the estimators of each level while its relative standard deviation is estimated with the well-known Pythagoras-like formula (in the tables, ccv stands for the squared ).

1.2 Finer tuning of the simulations

The -sized runs are split into blocks of events for the sake of evaluating the of the estimators with (EQ. 1), enabling the determination of the requested length for the final simulation with (EQ. 2).

An optimization, as exemplified in table 1, is to weight the different levels so that the level with the worst will be more upsized than the others (EQ. 3), thus replacing the otherwise quadratic mean on the by an arithmetical one. Boundaries-problems in the upsizing of the simulation, and the quality of the pseudo-random generator [2] are other problems to address.

1.3 A benchmark

Let us illustrate these principles with the Markov chain for the repairman: we model a workshop of machines, whose times to failure and repairs are iid random variables with an exponential law of parameters and . An example of a simulation is provided in tables 2 to 5, where and .

The underlying theoretical problem is explicitly solvable, leading to the probabilities (EQ. 4). The analytical computation of the variances is less obvious. (EQ. 5) is the formula for the variance of a quotient, applied to the frequencies obtained as the ratio of the elapsed time in state to the total time . (EQ. 6) states that equals the product of the number of visits by their mean duration: , independent of . But, estimated on a sized sample, the is .

Finally, let be the transformation matrix and the state-vector:

With some reckonings, we get (EQ. 7), with the hypothesis that be the single unimodular eigenvalue of , and be simple. In that Bernoulli-like formula, all -columns are equal to the stationary solution (EQ. 4), , and . In our example, the Markov chain will "remember" the original parity, thus is a -eigenvalue, and (EQ. 7) only applies to the matrices coding for the action of on the classes of the parity relation (cf table 6).

1.4 Conclusion

A quite good agreement is found between the variances issued from (EQ. 1) and from (EQ. 5), (EQ. 6), (EQ. 7). Moreover, the comparison, given table 7, between the requested number of events for evaluating, with the same precision, the probability of the total failure for three choices of the levels: our algorithm, the simple equidistant choice, and the theoretical (and time-consuming to establish...) optimum, shows that our algorithm is quasi-optimal.

Our hierarchical importance sampling is thus efficient when a set of "trigger events" can be identified in a given system that orderly imply each other and the rare events as well.