Branching Subset Simulation

Subset Simulation is a Markov chain Monte Carlo method that was initially conceived to compute small failure probabilities in structural reliability problems. This is done by iteratively sampling from nested subsets on the input space of a performance function. Subset Simulation has since been adapted to perform as a sampler in other realms such as optimisation, Bayesian updating and history matching. In all of these contexts, it can be that either the geometry of the input domain or the nature of the corresponding performance function cause Subset Simulation to suffer from ergodicity problems. This paper proposes an enhancement to Subset Simulation called Branching Subset Simulation. The proposed framework uses a nearest neighbours algorithm and Voronoi diagrams to partition the input space, and recursively begins Branching Subset Simulation anew in each partition. It is shown that Branching Subset Simulation is less likely than Subset Simulation to suffer from ergodicity problems and has improved sampling efficiency