Probabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an Example
Richard Arratia, Stephen DeSalvo · Combinatorics Probability Computing · 2016
We propose a new method, probabilistic divide-and-conquer, for improving the success probability in rejection sampling. For the example of integer partitions, there is an ideal recursive scheme which improves the rejection cost from asymptotically ordern3/4to a constant. We show other examples for which a non-recursive, one-time application of probabilistic divide-and-conquer removes a substantial fraction of the rejection sampling cost. We also present a variation of probabilistic divide-and-conquer for generating i.i.d. samples that exploits features of the coupon collector's problem, in order to obtain a cost that is sublinear in the number of samples.