Effective branching splitting method under cost constraint (Q952828)

The paper is devoted to a development and a study of an effective method for obtaining accurate estimates of rare event probability. The main idea is that there exist some well identifiable intermediate system states that are visited much more often than target states themselves, and behave as gateway states for reaching the rare event. Thus, a decreasing sequence of conditioning events leading to the rare event is under consideration, and then, the probability of this event can be calculated. It is proposed that the conditioning events are not rare, but the conditioning probabilities are in general not available explicitly. A particular method is considered in the paper. The principle of the proposed method is at first to run simultaneously several particles starting from a given intermediate state. After a while, some of them are evolving ``badly'', while the others are have evolved ``well'', i.e. have succeeded to reach the next intermediate stage. ``Bad'' particles are then moved to position of ``good'' ones and so until a rare event is reached. This approach is known, but in practice, the trajectory splitting method is difficult to apply, because the difficulties of finding theoretically the optimal sequence of conditioning events, leading to the rare event. Furthermore, the probability of reaching an intermediate conditioning event varies generally with the state of entrance in the previous level. It soon becomes clear that, even in the case when the calculated probability is close to optimal, the fact that the number of replicas is not integer destroys rapidly the accuracy of the algorithm. In such a case, one can take splitting trails equal to the closest integer (\(k\) or \(k+1\)) of the optimal value but whatever the choice is made, the criticality of the Galton-Watson process will be lost and the loss of precision is significant. The paper is concerned with the study of different ways to overcome this problem. The main goal of the author is to propose a probability estimation algorithm that is as close as possible to the optimal one. Precise estimates of the rare event are derived using several bounding functions, instead of a single one. Several bounding functions are used to obtain sharper upper and lower estimates. These bounding functions are chosen in the low dimensional Lie groups of the homographic and affine functions. The higher the dimension of the Lie group, the more precise the approximation, since the dimension describes the number of parameters for the adjusting function. Unfortunately, the author did not find higher dimensional Lie algebras of monotone functions (a necessary property for merely iterating the inequalities obtained). The interest of using such functions lies also in the fact that iterates can be explicitly computed. This technique leads to accurate bounds on the rare event probability. The relative simplicity of the considered model allows the author to state explicit results such as Chernoff's bounds of the relative error of the rare event estimate. Going further in the calculus, using the presented heuristic, one can also deduce a central limit theorem and thus Berry-Esseen bounds. The sensitivity of Chernoff's bounds is studied, depending on the choice of the splitting number in three different algorithms based on the branching splitting model. They provide precise estimates of the relative error between rare event probability and its estimate.