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

DOI10.1017/S0963548315000358MaRDI QIDQ5366902zbMATH OpenOpenAlexFDO

Authors Richard Arratia, Stephen DeSalvo

Publication date 10 October 2017

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(16)

• 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
• Random sampling of contingency tables via probabilistic divide-and-conquer
• Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method
• From spectral to scattering form factor
• Simulating the component counts of combinatorial structures
• Boltzmann distribution on ``short integer partitions with power parts: limit laws and sampling
• Improvements to exact Boltzmann sampling using probabilistic divide-and conquer and the recursive method
• On the largest part size of low‐rank combinatorial assemblies
• scientific article; zbMATH DE number 2080064 (Why is no real title available?)
• A random arrival rule for division problems with multiple references
• Limit shapes via bijections
• Centered partition processes: informative priors for clustering (with discussion)
• Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer
• On the random sampling of pairs, with Pedestrian examples

Describes a project that uses

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)