Probabilistic divide-and-conquer: deterministic second half

DOI10.1016/J.AAM.2017.06.005MaRDI QIDQ2407388zbMATH OpenOpenAlexFDO

Authors Stephen DeSalvo

Publication date 29 September 2017

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic divide-and-conquer methodrandom sampling algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Stochastic programming (90C15)

Abstract: We present a probabilistic divide-and-conquer (PDC) method for emph{exact} sampling of conditional distributions of the form $$, where $$ is a random variable on $mathcalX$, a complete, separable metric space, and event $E$ with $mathbbP(E)geq0$ 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 $mathcalX$ via sets $mathcalA$ and $mathcalB$ such that $mathcalX=mathcalAimesmathcalB$, and sample from each separately. The deterministic second half approach is to select the sets $mathcalA$ and $mathcalB$ such that for each element $ainmathcalA$, there is only one element $b_{a}inmathcalB$ for which $(a,b_a)inE$. 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.

Recommendations

• Random sampling of contingency tables via probabilistic divide-and-conquer
• 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: a new exact simulation method, with integer partitions as an example
• Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer

Cites work

• A linear algorithm for the random sampling from regular languages
• A method and two algorithms on the theory of partitions
• A probabilistic approach to the geometry of the \(\ell^n_p\)-ball
• A problem of the Allocation of Particles in Cells and Cycles of Random Permutations
• An alternate development of conditioning
• An Inequality
• Analytic combinatorics
• Asymptotic properties of eulerian numbers
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Bounds for Kac's master equation
• Conditioning as disintegration
• Efficient implementation of the Hardy-Ramanujan-Rademacher formula
• Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Handbooks in operations research and management science: Simulation
• scientific article; zbMATH DE number 3873414 (Why is no real title available?)
• scientific article; zbMATH DE number 3957110 (Why is no real title available?)
• scientific article; zbMATH DE number 46578 (Why is no real title available?)
• scientific article; zbMATH DE number 3495416 (Why is no real title available?)
• scientific article; zbMATH DE number 1324223 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 2086647 (Why is no real title available?)
• scientific article; zbMATH DE number 3224156 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3075560 (Why is no real title available?)
• scientific article; zbMATH DE number 3104491 (Why is no real title available?)
• Independent process approximations for random combinatorial structures
• Log-concavity of the partition function
• Logarithmic combinatorial structures: A probabilistic approach
• On the Partition Function p (n )
• On the Remainders and Convergence of the Series for the Partition Function
• On the singularity of random Bernoulli matrices -- novel integer partitions and lower bound expansions
• Ordered Cycle Lengths in a Random Permutation
• Perfect simulation
• Permutohedra, Associahedra, and Beyond
• Poisson process approximations for the Ewens sampling formula
• Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example
• Probability. Theory and examples.
• Random generation using binomial approximations
• Random Sampling of Plane Partitions
• Random set partitions: Asymptotics of subset counts
• Small ball probability, inverse theorems, and applications
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• Sur les entiers n pour lesquels il y à beaucoup de groupes abéliens d'ordre \(n\)
• The cycle structure of random permutations
• The fundamental limit theorems in probability
• The sampling theory of selectively neutral alleles
• The Structure of Random Partitions of Large Integers
• Uniform generation of a Motzkin word
• Uniform random generation of decomposable structures using floating-point arithmetic

Cited in

(8)

• 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 Poisson approximations for the Ewens sampling formula when the mutation parameter grows with the sample size
• Improvements to exact Boltzmann sampling using probabilistic divide-and conquer and the recursive method
• Limit shapes via bijections
• Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example
• On the largest part size of low‐rank combinatorial assemblies
• Random sampling of contingency tables via probabilistic divide-and-conquer

This page was built for publication: Probabilistic divide-and-conquer: deterministic second half

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