Effective branching splitting method under cost constraint
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.
- Branching in branch-and-price: A generic scheme
- Approximating optimum branchings in linear time
- Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
- Split manipulations in cost sharing of minimum cost spanning tree
- The split feasibility problem and its solution algorithm
- scientific article; zbMATH DE number 1431654
- A Branch and Price algorithm for the \(k\)-splittable maximum flow problem
- Optimal multiway split trees
- Decomposition branch and bound algorithm for optimization problems over efficient sets
- An efficient algorithm for minimum-weight bibranching
- A Generalized Bernoulli Scheme and Its Limit Distributions
- A large deviations perspective on the efficiency of multilevel splitting
- Branching Processes with Random Environments, II: Limit Theorems
- Fast simulation of rare events in queueing and reliability models
- scientific article; zbMATH DE number 1666084 (Why is no real title available?)
- scientific article; zbMATH DE number 4207654 (Why is no real title available?)
- scientific article; zbMATH DE number 2106098 (Why is no real title available?)
- scientific article; zbMATH DE number 795109 (Why is no real title available?)
- scientific article; zbMATH DE number 3410334 (Why is no real title available?)
- Iterated Random Functions
- Limit theorems for branching processes in a random environment
- Multilevel splitting for estimating rare event probabilities
- Normalisation d'un processus de branchement critique dans un environnement aléatoire. (Normalization of a critical branching process in a random environment)
- On a stochastic difference equation and a representation of non–negative infinitely divisible random variables
- On Branching Processes in Random Environments
- On Branching Processes with Random Environments: I: Extinction Probabilities
- On Monte Carlo estimation of large deviations probabilities
- Probability approximations via the Poisson clumping heuristic
- Random difference equations and renewal theory for products of random matrices
- RARE EVENT SIMULATION
- Strict stationarity of generalized autoregressive processes
- The random difference equation \(X_ n = A_ n X_{n-1} + B_ n\) in the critical case
- The stochastic equation Yn+1=AnYn + Bn with stationary coefficients
- Splitting for multi-objective optimization
- Unbiased simulation of rare events in continuous time
- Solving the market split problem via branch-and-cut
- Genetic genealogical models in rare event analysis
- Splitting for optimization
- Branching and interacting particle interpretations of rare event probabilities
- A large deviations perspective on the efficiency of multilevel splitting
- Splitting algorithms for rare events of semimartingale reflecting Brownian motions
- Sampling Conditionally on a Rare Event via Generalized Splitting
- A Two-Step Branching Splitting Model Under Cost Constraint for Rare Event Analysis
- Efficient Monte Carlo simulation via the generalized splitting method
This page was built for publication: Effective branching splitting method under cost constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q952828)
