Probabilistic divide-and-conquer: deterministic second half

2014/11/25 by DeSalvo, Stephen
#60C05 #65C05 #65C50 #FOS: Mathematics #G.3 #Probability (math.PR)

paper · doi:10.48550/arxiv.1411.6698

Abstract

We present a probabilistic divide-and-conquer (PDC) method for exact sampling of conditional distributions of the form L( \bf X | \bf X ∈ E), where \bf X is a random variable on X, a complete, separable metric space, and event E with ℙ(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 b_a ∈ B for which (a,b_a)∈ 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.

Related

• Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method
• Exact sampling algorithms for Latin squares and Sudoku matrices via\n probabilistic divide-and-conquer
• Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example
• Random sampling of Latin squares via binary contingency tables and probabilistic divide-and-conquer
• Random Sampling of Contingency Tables via Probabilistic Divide-and-Conquer