Linear-time exact sampling of sum-constrained random variables
Frédérique Bassino, Andrea Sportiello · HAL (Le Centre pour la Communication Scientifique Directe) · 2018
In the problem of exactly-sampling from a probability distribution, one is often led to sample from a measure of the form µ(x 1 ,. .. , x n) ∝ i f i (x i) × δ x1+•••+xn,m , with f i 's integer-valued distributions. When the f i 's are all equal, an algorithm of Devroye essentially solves this problem in linear time. However, in several important cases these f i 's are in the same family, but have distinct parameters. A typical example is the sampling of random set partitions, related to a set of f i 's which are geometric distributions with different averages. We describe here a simple algorithmic solution for a large family of n-tuples of functions. At this aim we provide the notion of "positive decomposition" of one probability distribution into another.