Back to Search
Start Over
An Analysis of the Alias Method for Discrete Random-Variate Generation.
- Source :
- INFORMS Journal on Computing; Summer2005, Vol. 17 Issue 3, p321-327, 7p
- Publication Year :
- 2005
-
Abstract
- This paper introduces and studies an optimization problem related to the alias method for discrete random-variate generation. The alias method is an efficient method to generate random variates from a discrete probability distribution. The efficiency of the alias method can be improved by designing the alias table such that the expected number of computations that must be performed per value generated is minimized. The problem of optimizing the construction of the alias table is proven to be strongly NP-hard, even if either of two variations of the alias method relaxing the alias-table-generation restrictions are used. Integer-programming formulations describing these three optimization problems are presented, and insights regarding necessary optimality criteria and relationships among their optimal solutions are discussed. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10919856
- Volume :
- 17
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- INFORMS Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 17948629
- Full Text :
- https://doi.org/10.1287/ijoc.1030.0063