We present a probabilistic divide-and-conquer (PDC) method for \emph{ exact} sampling of conditional distributions of the form $\mathcal{ L}( { \bf X}\, |\, { \bf X} \in E)$, where ${ \bf X}$ is a random variable on $\mathcal{ X}$, a complete, separable metric space, and event $E$ with $\mathbb{ P}(E) \geq 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 $\mathcal{ X}$ via sets $\mathcal{ A}$ and $\mathcal{ B}$ such that $\mathcal{ X} = \mathcal{ A} \times \mathcal{ B}$, and sample from each separately. The deterministic second half approach is to select the sets $\mathcal{ A}$ and $\mathcal{ B}$ such that for each element $a\in \mathcal{ A}$, there is only one element $b_a \in \mathcal{ B}$ for which $(a,b_a)\in 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.
Categories: math.PR