Probabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an Example

DOI10.1017/S0963548315000358zbMath1372.60006arXiv1110.3856OpenAlexW2963094082MaRDI QIDQ5366902

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 aspects of partitions of integers (05A17) Combinatorial probability (60C05)

Related Items

Probabilistic divide-and-conquer: deterministic second half ⋮ Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer ⋮ Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method ⋮ On the largest part size of low‐rank combinatorial assemblies ⋮ On Poisson approximations for the Ewens sampling formula when the mutation parameter grows with the sample size ⋮ Simulating the component counts of combinatorial structures ⋮ Limit Shapes via Bijections ⋮ Centered partition processes: informative priors for clustering (with discussion) ⋮ Random sampling of contingency tables via probabilistic divide-and-conquer ⋮ On the Random Sampling of Pairs, with Pedestrian Examples ⋮ On sampling representatives of relational schemas with a functional dependency

Uses Software

• Mathematica

Cites Work

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