Importance sampling the union of rare events with an application to power systems analysis
This paper presents a method for estimating the probability μ of a union of J rare events. The method uses n samples, each of which picks one of the rare events at random, samples conditionally on that rare event happening and counts the total number of rare events that happen. We call it ALORE, for `at least one rare event'. The ALORE estimate is unbiased and has a coefficient of variation no larger than √((J+J^-1-2)/(4n)). The coefficient of variation is also no larger than √((μ̅/μ-1)/n) where μ̅ is the union bound. Our motivating problem comes from power system reliability, where the phase differences between connected nodes have a joint Gaussian distribution and the J rare events arise from unacceptably large phase differences. In the grid reliability problems even some events defined by 5772 constraints in 326 dimensions, with probability below 10^-22, are estimated with a coefficient of variation of about 0.0024 with only n=10,000 sample values.
READ FULL TEXT