RareEventProbabilityEstimator Class

public sealed class RareEventProbabilityEstimator : CrossEntropyProgram

Public NotInheritable Class RareEventProbabilityEstimator
	Inherits CrossEntropyProgram

public ref class RareEventProbabilityEstimator sealed : public CrossEntropyProgram

[<SealedAttribute>]
type RareEventProbabilityEstimator = 
    class
        inherit CrossEntropyProgram
    end

Inheritance

Object    CrossEntropyProgram    RareEventProbabilityEstimator

The Cross-Entropy method for rare event simulation

The current implementation of the RareEventProbabilityEstimator class is based on the main Cross-Entropy program for rare event simulation proposed by Rubinstein and Kroese (Algorithm 2.3.1)^[1].

A Cross-Entropy estimator is designed to evaluate the probability of rare events regarding the performance of complex systems. It is assumed that such probability must be evaluated with respect to a specific density function, member of a parametric family



where is a vector representing a possible state of the system, and is the set of allowable values for parameter . Let be the specific parameter value under which the probability must be evaluated. This is referred to as the nominal parameter.

A given event is eligible for being targeted by a RareEventProbabilityEstimator if it can be defined as



or



where is the state space of the system, is the function returning the system performance at state and is a performance value, which is referred to as the threshold level of the event under study, such that the set is rare under .

The target probability can thus be represented as



where is or , and is the indicator function of . In principle, one can base its estimation on a sample drawn from by evaluating the crude Monte Carlo estimator



However, if is rare under , a large number of indicator functions will evaluate to zero, leading to inefficiencies. To overcome such difficulty, the Cross-Entropy method suggests to exploit a likelihood ratio estimator: instead of sampling from , the method select another density in by identifying a parameter that guarantees the most accurate estimate of the target probability for a specified simulation effort, or sample size . Given a sample from , the probability is thus estimated as



where



is the likelihood ratio of to evaluated at state .

The idea behind the Cross-Entropy method is to select by taking into account the estimator based on the ratio



where



is the density of conditional on . Such estimator is unusable, since it depends on the target probability. However, it is ideally optimal because its variance is equal to zero. For this reason, it is proposed to select the parameter such that the corresponding density is the closest to the optimal one, the difference between two densities, say and , being measured as a Kullback–Leibler divergence:



The selection is thus obtained by minimizing the divergence between the generic density in , say , and the ideal density :

Such minimization corresponds to the maximization



where is the expectation operator under , or, equivalently, to



for every parameter . This implies that, given a sample from , a solution to such optimization can be estimated through the solution to the program:



where



and



In this context, is said the sampling reference parameter, while the elements in set are referred to as the elite sample positions, and the corresponding sample points , for , as the elite sampled states. The interest in such an approach is due to the possibility of choosing a parameter under which the event is less rare under density than under density . In this way, in order to obtain a good estimation, a smaller simulation effort would be required.

The selection of the optimal reference parameter is an iterative multi step procedure, in which, at each iteration , a new level and a new reference parameter are identified. The goal being to obtain, after a number of iterations , a reference parameter very close to the optimal one and set . The algorithm has two main steps.

Sampling step

The first one, the sampling step, is responsible for generating diverse candidate states of the system. Let be the reference parameter at iteration , with , and let be the sample drawn from .

Updating step

To avoid the difficulties due to the rareness of under , the sample drawn in the sampling step is not exploited to estimate . Instead, an iteration specific target event is defined in terms of a new iteration level , which is set as follows.

Let be the sampled state such that , , and consider a constant, referred to as the rarity of the program, say , set to a value in the interval .

If then the points occupying a position greater than or equal to are the elite sampled states, with being the ceiling function. In this case, the current iteration is said to reach a performance level equal to .

Otherwise, if then elite sampled states can be defined as those points occupying a position less than or equal to , where is the floor function. Such points are thus , and the current iteration is said to reach a performance level equal to .

Once that the elite states have been identified, the joint distribution from which the states will be sampled in the next iteration is updated by estimating its parameters using the elite states only.

The iteration parameter is chosen to be the optimal one for estimating by solving the program

In this way, new reference parameters are selected so that the target event becomes more and more probable than under the nominal distribution of interest. As discussed in the remarks about the CrossEntropyProgram class, these operations correspond to the updating step of a Cross-Entropy program.

The algorithm stops iterating when the iteration level reaches the event level, i.e. when if ; otherwise, when .

Executing a Cross-Entropy estimator

Class RareEventProbabilityEstimator follows the Template Method pattern^[2] by defining in an operation the structure of a Cross-Entropy algorithm aimed to estimate the probability of a rare event. Estimate is the template method, in which the invariant parts of a Cross-Entropy estimator are implemented once, deferring the implementation of behaviors that can vary to a RareEventProbabilityEstimationContext instance, that method Estimate receives as a parameter.

RareEventProbabilityEstimationContext inherits or defines abstract or virtual methods which represent some primitive operations of the template method, i.e. those varying steps that its subclasses will override to define the concrete behavior of the algorithm. See the documentation of class RareEventProbabilityEstimationContext for examples of how to implement a context for rare event simulations.

Reference