Article ID: | iaor2007480 |
Country: | United States |
Volume: | 17 |
Issue: | 3 |
Start Page Number: | 321 |
End Page Number: | 327 |
Publication Date: | Jun 2005 |
Journal: | INFORMS Journal On Computing |
Authors: | Jacobson Sheldon H., Smith J. Cole |
Keywords: | computers, control processes |
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.