QUICK ESTIMATION OF RARE EVENTS IN STOCHASTIC NETWORKS

This paper presents a method for fast estimation of probabilities of r are events in stochastic networks, with a particular emphasis on coher ent reliability systems. The method is based on the concepts of likeli hood-ratios (LR), change of probability measure) and the bottleneck-cu t in the network. Both polynomial and exponential-time Monte Carlo est imators are defined, and conditions under which the time complexity of the proposed LR estimators is bounded by a polynomial are discussed. The accuracy of the method depends only on the size (cardinality) of t he bottleneck-cut, not on the topology and actual size of the network. Supporting numerical results are presented, with the cardinality of t he bottleneck-cut less than or equal to 20.