Probability Estimation with Truncated Inverse Binomial Sampling

In science and engineering, it is an ubiquitous problem to estimate the probability of event based on Monte Carlo simulation. For instance, in engineering technology, a critical c oncern is the probability of failure or risk, which is generally considered as the probability that certain pre -specified requirements for the relevant system are violated in the presence of uncertainties. Ever since th e advent of modern computers, extensive research works have been devoted to quantitative approaches o f risk evaluation for engineering systems (see, e.g., [1, 8, 9, 11, 16, 18, 20] and the references therein). I n additional to theoretical development, many softwares have been developed for risk evaluation. For exam ple, for control systems, a software called RACT has been developed for evaluating the risk of uncertain syste ms [7, 21]. Many softwares such as APMC [13], PRISM [15], UPPAAL [6], have been developed for evaluating t he risk of stochastic discrete event systems (see, [1] and the references therein). One of the remarkable achievements of existing theories and softw ares is the rigorous control of error in the estimation of probability, that is, the probability of relevant ev ent can be evaluated with certified reliability. Theoretically, for a priori given α, δ (0, 1), existing methods are able to produce an estimate null p for the true value of the probability p so that one can be 100(1 δ)% confident that null p p α holds. 1 Unfortunately, existing methods suffer from huge computational complexity as the margin of absolute error α is small, e.g. 10