Splitting sequential Monte Carlo for efficient unreliability estimation of highly reliable networks

• Estimating the terminal network reliability is difficult.
• The existing Lomonosov’s method is not accurate for many cases.
• We present a general modification to solve this problem.
• This modification is shown to outperform the current state-of-the-art.

Assessing the reliability of complex technological systems such as communication networks, transportation grids, and bridge networks is a difficult task. From a mathematical point of view, the problem of estimating network reliability belongs to the #P complexity class. As a consequence, no analytical solution for solving this problem in a reasonable time is known to exist and one has to rely on approximation techniques. In this paper we focus on a well-known sequential Monte Carlo algorithm — Lomonosov’s turnip method. Despite the fact that this method was shown to be efficient under some mild conditions, it is known to be inadequate for a stable estimation of the network reliability in a rare-event setting. To overcome this obstacle, we suggest a quite general combination of sequential Monte Carlo and multilevel splitting. The proposed method is shown to bring a significant variance reduction as compared to the turnip algorithm, is easy to implement and parallelize, and has a proven performance guarantee for certain network topologies.