Partial rejection sampling with an application to all-terminal network reliability
22nd February 2019, 3:30 pm – 4:30 pm
Main Maths Building, SM4
Rejection sampling, sometimes called the acceptance-rejection method, is a simple, classical technique for sampling from a conditional distribution given that some desirable event occurs. The idea is to sample from the unconditioned distribution (assumed to be simple, for example a product distribution), accept the sample if the desirable event occurs and reject otherwise. This trial is repeated until the first acceptance. Rejection sampling in this form is rarely a feasible approach to sampling combinatorial structures, as the acceptance probability is generally exponentially small in the size of the problem instance. However, some isolated cases had been discovered where an exact sample is obtained by resampling only that part of the structure that “goes wrong”, an example being the “sink-popping” algorithm of Cohn, Pemantle and Propp for sampling sink-free orientations in an undirected graph.
The situations in which this shortcut still yields an exact sample from the desired distribution can be characterised, and are related to so-called extreme instances for the Lovász Local Lemma. Even when this ideal situation does not obtain, we find that we can generate exact samples by resampling just the parts of the structure that go wrong “plus a bit more”. We call this “Partial rejection sampling”. As an application we consider the computation of "all-terminal network reliability". Let G be an undirected graph in which each edge is assigned a failure probability. Suppose the edges of G fail independently with the given probabilities. We show how to compute efficiently the probability that the resulting graph is connected. No polynomial-time algorithm for estimating this quantity within specified relative error was previously known.
Based on joint work with Heng Guo (Edinburgh) and Jingcheng Liu (UC, Berkeley).