A simple generator for discrete log-concave distributions (Q580867)

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.