A linear algorithm for generating random numbers with a given distribution

Let xi be a random variable over a finite set with an arbitrary probability distribution. Improvements to a fast method of generating sample values for xi in constant time are suggested. The proposed modification reduces the time required for initialization to O(n). For a simple genetic algorithm, t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on software engineering 1991-09, Vol.17 (9), p.972-975
Main Author: Vose, M.D.
Format: Article
Language:English
Subjects:
Arrays
Computational modeling
Computer science
Genetic algorithms
Probability
Probability distribution
Random number generation
Random variables
Roundoff errors
Software engineering
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let xi be a random variable over a finite set with an arbitrary probability distribution. Improvements to a fast method of generating sample values for xi in constant time are suggested. The proposed modification reduces the time required for initialization to O(n). For a simple genetic algorithm, this improvement changes an O(g n 1n n) algorithm into an O(g n) algorithm (where g is the number of generations, and n is the population size).< >
ISSN:0098-5589
1939-3520
DOI:10.1109/32.92917