An Automatic Generator for a Large Class of Unimodal Discrete Distributions

Hörmann, Wolfgang and Derflinger, Gerhard (1997) An Automatic Generator for a Large Class of Unimodal Discrete Distributions. Preprint Series / Department of Applied Statistics and Data Processing, 19. Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, Vienna.


Download (205kB)


The automatic Algorithm ARI developed in this paper can generate variates from a large class of unimodal discrete distributions. It is only necessary to know the mode of the distribution and to have a subprogram available that can evaluate the probabilities. In a set up step the algorithm constructs a table mountain shaped hat function. Then rejection inversion, a new variant of the rejection method for discrete distributions that needs only one uniform random number per iteration, is used to sample from the desired distribution. It is shown that the expeceted number of iterations is uniformly bounded for all T-concave discrete distributions. Utilizing a simple squeeze or an auxiliary table of moderate size, which is initialized during generation and not in the set up, Algorithm ARI is fast, at least as fast as the fastest known methods designed for the Poisson, binomial and hypergeometric distributions. The set up time of the algorithm is not affected by the size of the domain of the distribution and is about ten times longer than the generation of one variate. Compared with the very fast and well known alias and indexed search methods the set up of Algorithm ARI is much faster but the generation time is about two times slower. More important than the speed is the fact that Algorithm ARI is the first automatic algorithm that can generate samples from discrete distributions with heavy tails. (author's abstract)

Item Type: Paper
Additional Information: published in: ESM'97. European Simulation Multiconference 1997, ed. A. R. Kaylan and A. Lehmann, Istanbul : Society for Computer Simulation, 1997, pp. 139-144
Keywords: random variate generation / discrete distributions / universal generator / T-concave
Classification Codes: MSC 65C10
Divisions: Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Depositing User: Repository Administrator
Date Deposited: 10 Jul 2006 11:21
Last Modified: 22 Oct 2019 00:41


View Item View Item


Downloads per month over past year

View more statistics