  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 order $n^{3/4}$ to 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.
