A simple recursive importance and stratified sampling scheme for stochastic network reliability estimation

Crude simulation for estimating reliability of a stochastic network often requires large sample size to obtain statistically significant results. In this paper, we propose a simple recursive importance and stratified sampling estimator which is shown to be unbiased and achieve smaller variance. Preallocation of sampling efforts of size two to each undetermined subnetwork on each stage makes it possible to estimate the variance of the proposed estimator and significantly enhances the effectiveness of variance reduction from stratification by deferring the termination of recursive stratification. Empirical results show that the proposed estimator achieves significant variance reduction, especially for highly reliable networks.