Probabilistic divide-and-conquer: deterministic second half

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}$isarandomvariableon$$\mathcal{X}$$, a complete, separable metric space, and event $E$ with $\mathbb{P}(E)\ge 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.