Abstract
We give a short algorithm that can be used to generate random integers with a log-concave distribution (such as the binomial, Poisson, hypergeometric, negative binomial, geometric, logarithmic series or Polya-Eggenberger distributions). The expected time is uniformly bounded over all these distributions. The algorithm can be implemented if a few lines of high level language code.
Zusammenfassung
Wir geben einen raschen Algorithmus an, der Zufallszahlen mit log-konkaver Verteilung (z. B. binomisch, Poisson, hypergeometrisch, negativ binomisch, geometrisch, logarithmisch, Polya-Eggenberger) erzeugt. Die mittlere Rechenzeit ist bezüglich all dieser Verteilungen gleichmäßig beschränkt. Der Algorithmus kann in wenigen Zeilen einer höheren Programmiersprache implementiert werden.
This is a preview of subscription content, log in via an institution to check access.
References
Ahrens, J. H., Dieter, U.: Sampling from binomial and Poisson distributions: a method with bounded computation times. Computing25, 193–208 (1980).
Ahrens, J. H., Dieter, U.: Computer generation of Poisson deviates from modified normal distributions. ACM Transactions on Mathematical Software8, 163–179 (1982).
Ahrens, J. H., Kohrt, K. D., Dieter, U.: Algorithm 599. Sampling from gamma and Poisson distributions. ACM Transactions on Mathematical Software9, 255–257 (1983).
Bosch, A. J.: The Polya distribution. Statistica Neerlandica17, 201–213 (1963).
Devroye, L., Naderisamani, A.: A binomial random variate generator. Technical Report, School of Computer Science, McGill University, Montreal 1980.
Devroye, L.: The computer generation of Poisson random variables. Computing26, 197–207 (1981).
Devroye, L.: A simple algorithm for generating random variates with a log-concave density. Computing33, 247–257 (1984).
Devroye, L.: Non-Uniform Random Variate Generation. New York: Springer-Verlag 1986.
Johnson, N. L., Kotz, S.: Distributions in Statistics: Discrete Distributions. New York: John Wiley 1969.
Kachitvichyanukul, V., Schmeiser, B. W.: Computer generation of hypergeometric random variates. Journal of Statistical Computation and Simulation22, 127–145 (1985).
Keilson, J.: A threshold for log-concavity for probability generating functions and associated moment inequalities. Annals of Mathematical Statistics43, 1702–1708 (1972).
Kemp, A. W.: Efficient generation of logarithmically distributed pseudo-random variables. Applied Statistics30, 249–253 (1981).
Kemp, C. D., Kemp, A. W.: Generalized hypergeometric distributions. Journal of the Royal Statistical Society, Series B18, 202–211 (1956).
Schmeiser, B. W., Kachitvichyanukul, V.: Poisson random variate generation. Research Memorandum 81-4, School of Industrial Engineering, Purdue University, West Lafayette, Indiana 1981.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Devroye, L. A simple generator for discrete log-concave distributions. Computing 39, 87–91 (1987). https://doi.org/10.1007/BF02307716
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02307716