Probabilistic divide-and-conquer: Deterministic second half

We present a probabilistic divide-and-conquer (PDC) method for exact sampling of conditional distributions of the form L(X|X∈E), where X is a random variable on X, a complete, separable metric space, and event E with P(E)≥0 is assumed to have sufficient regularity such that the conditional distribution exists and is unique up to almost sure equivalence. The PDC approach is to define a decomposition of X via sets A and B such that X=A×B, and sample from each separately. The deterministic second half approach is to select the sets A and B such that for each element a∈A, there is only one element ba∈B for which (a,ba)∈E. We show how this simple approach provides non-trivial improvements to several conventional random sampling algorithms in combinatorics, and we demonstrate its versatility with applications to sampling from sufficiently regular conditional distributions.