A simple generator for discrete log-concave distributions
type: Item
instance of: scholarly article
title: A simple generator for discrete log-concave distributions
zbMATH Open document ID: 0626.65002
DOI: 10.1007/BF02307716
published in: Computing
publication date: 1987-01-01T00:00:00Z
review text: An algorithm is proposed for the hypergeometric distribution and generalizations and limiting cases thereof: binomial, Poisson, Pascal \((=negative\) binomial), geometric, rectangular, and many more ``similar'' ones as e.g. logarithmic series, hyper-Poisson, Polya-Eggenberger. It is the rejection algorithm for generating random variates in the cases, when the distribution is discrete univariate, unimodal and not feasibly invertible (by computation), but closely majorized by an easily computable function g(k). Considered are distributions \(p_ k\) (k\(\in {\mathbb{Z}})\) with log \(p_ k\) concave and therefore of limited variance in k (uniformly), which covers the above mentioned distributions. In this case g(k) can be a constant or simple stepwise exponentially) decreasing function, i.e.: \(g(k)=c\cdot e^{-a| m-k|}\) for k outside the range of the modes (points with maximal probability, m one of them, c depending on the sign of m-k). On the other hand, for the rejection algorithm, the expected number of trials turns out to be \(4+p_ m\) (less in special cases), where \(p_ m\) is the probability of a mode. The algorithm itself is a simple program of a few lines - besides using a call for the actual distribution function - consisting of usual arithmetic, a call for the exponential (as being the principal part of the majoriser), three calls for generating independent random variables (uniform in 0...1), a call for a random sign \((+/-)\), and a combination of comparisons as rejection condition; all this for each trial. The performance depends on the closeness of g(k) to the actual distribution and is not discussed.
reviewed by: K. G. Brokate
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 65C99
Mathematics Subject Classification ID: 62-04
Mathematics Subject Classification ID: 65C05
zbMATH DE Number: 4018202
zbMATH Keywords: logarithmically concave distributions
zbMATH Keywords: binomial distribution
zbMATH Keywords: Poisson distribution
zbMATH Keywords: Pascal distribution
zbMATH Keywords: geometric distribution
zbMATH Keywords: hyper-Poisson distribution
zbMATH Keywords: Polya-Eggenberger distribution
zbMATH Keywords: hypergeometric distribution
zbMATH Keywords: rejection algorithm
author: Luc Devroye
MaRDI profile type: Publication
cites work: Sampling from binomial and Poisson distributions: a method with bounded computation times
cites work: Computer Generation of Poisson Deviates from Modified Normal Distributions
cites work: Algorithm 599
cites work: The computer generation of Poisson random variables
cites work: A simple algorithm for generating random variates with a log-concave density
cites work: Q3723577
cites work: Q4043971
cites work: Computer generation of hypergeometric random variates†
cites work: A Threshold for Log-Concavity for Probability Generating Functions and Associated Moment Inequalities
cites work: Efficient Generation of Logarithmically Distributed Pseudo-Random Variables
cites work: Q3234902
full work available at URL: https://doi.org/10.1007/bf02307716
OpenAlex ID: W1554271285
Recommended article: A universal generator for discrete log-concave distributions
Recommended article: A simple algorithm for generating random variates with a log-concave density
Recommended article: A note on generating random variables with log-concave densities
Recommended article: A simple universal generator for continuous and discrete univariate T-concave distributions
Recommended article: Estimating a discrete log-concave distribution in higher dimensions
Recommended article: Q3785784
Recommended article: On a family of discrete log-symmetric distributions
Recommended article: Sampling from log-concave distributions
description: scientific article; zbMATH DE number 4018202