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

DOI10.1017/S0963548315000358zbMATH Open1372.60006arXiv1110.3856OpenAlexW2963094082MaRDI QIDQ5366902FDOQ5366902

Authors: Richard Arratia, Stephen DeSalvo 

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1110.3856

Recommendations

• Improvements to exact Boltzmann sampling using probabilistic divide-and conquer and the recursive method
• Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method
• Probabilistic divide-and-conquer: deterministic second half
• Random sampling of contingency tables via probabilistic divide-and-conquer
• scientific article; zbMATH DE number 269483

Mathematics Subject Classification ID

Combinatorial probability (60C05) Combinatorial aspects of partitions of integers (05A17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Paths in graphs
• Efficient implementation of the Hardy–Ramanujan–Rademacher formula
• Log-concavity of the partition function
• Partition bijections, a survey
• A method and two algorithms on the theory of partitions
• Rademacher-type formulas for restricted partition and overpartition functions
• Affine insertion and Pieri rules for the affine Grassmannian
• Title not available (Why is that?)
• Uniform generation of a Motzkin word
• The distribution of the number of summands in the partitions of a positive integer
• Title not available (Why is that?)
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Uniform generation of random regular graphs of moderate degree
• On a likely shape of the random Ferrers diagram
• The Erdős-Rényi law in distribution, for coin tossing and sequence matching
• Uniform random generation of decomposable structures using floating-point arithmetic
• Random Sampling of Plane Partitions
• Independent process approximations for random combinatorial structures
• The Structure of Random Partitions of Large Integers
• A Hardy-Ramanujan-Rademacher-type formula for \((r,s)\)-regular partitions
• Random set partitions: Asymptotics of subset counts
• Partition Asymptotics from Recursion Equations
• A Hardy-Ramanujan formula for restricted partitions
• Critical phenomena in sequence matching
• Probabilistic divide-and-conquer: deterministic second half
• Bijective proofs of some classical partition identities
• Log-concavity of the overpartition function
• Sur les entiers n pour lesquels il y à beaucoup de groupes abéliens d'ordre \(n\)
• Exact asymptotic formulas for the coefficients of nonmodular functions
• On the Amount of Dependence in the Prime Factorization of a Uniform Random Integer

Cited In (15)

• On sampling representatives of relational schemas with a functional dependency
• Probabilistic divide-and-conquer: deterministic second half
• On Poisson approximations for the Ewens sampling formula when the mutation parameter grows with the sample size
• Limit Shapes via Bijections
• Random sampling of contingency tables via probabilistic divide-and-conquer
• From spectral to scattering form factor
• Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method
• Boltzmann distribution on ``short integer partitions with power parts: limit laws and sampling
• Simulating the component counts of combinatorial structures
• On the largest part size of low‐rank combinatorial assemblies
• Title not available (Why is that?)
• A random arrival rule for division problems with multiple references
• On the Random Sampling of Pairs, with Pedestrian Examples
• Centered partition processes: informative priors for clustering (with discussion)
• Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer

Uses Software

• Mathematica

This page was built for publication: Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366902)