Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example

2011/10/17 by Richard Arratia, Arratia, Richard, Stephen DeSalvo +1
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #FOS: Mathematics #Probability (math.PR) #Statistical Methods and Bayesian Inference #Statistical Methods in Clinical Trials #math.PR

paper · pdf · doi:10.48550/arxiv.1110.3856

25 pages, revised writing. Added reference. Added Lemmas 3.9 and 3.10

openalex publication_date 2011/10/17 · arxiv created 2015/11/24 · arxiv updated 2015/11/25 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Partially Recursive Acceptance Rejection
• Probabilistic divide-and-conquer: deterministic second half
• Random Sampling of Contingency Tables via Probabilistic Divide-and-Conquer
• Random sampling of contingency tables and partitions: Two practical examples of the Burnside process
• Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method