An analysis of the alias method for discrete random-variate generation

An analysis of the alias method for discrete random-variate generation

0.00 Avg rating0 Votes
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: ,
Keywords: computers, control processes
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.

Reviews

Required fields are marked *. Your email address will not be published.