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

J. Cole Smith, Sheldon H. Jacobson

Research output: Contribution to journalArticle

10 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)321-327
Number of pages7
JournalINFORMS Journal on Computing
Volume17
Issue number3
DOIs
StatePublished - Jun 1 2005
Externally publishedYes

Keywords

  • Analysis of algorithms
  • Computational complexity
  • Optimization
  • Random variable generation
  • Simulation

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'An analysis of the alias method for discrete random-variate generation'. Together they form a unique fingerprint.

  • Cite this