User:Cjrieds/Alias method
 | This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. For guidance on developing this draft, see Wikipedia:So you made a userspace draft. Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
The alias method is an algorithm for returning a discrete, finite, random value in constant time. As such, it is a means of Pseudo-random number sampling. Given a discrete probability distribution, the method takes SOME AMOUNT OF TIME to create an object that can then be used for constant-time variable creation.
History
[edit]The alias method was described in a paper by Walker , however with a N^2 time table creation, I THINK. A further refinement by SOMEONE ELSE brought the table creation to a SOMETHING ELSE bound, in THIS PAPER.
Algorithm
[edit]DESCRIPTION OF THE TWO STEPS
TABLE CREATION
ALGORITHM
Comparison to other algorithms
[edit]WOOHOO, CONSTANT TIME VERSUS WORSE STUFF!
References
[edit]External links
[edit]Category:Pseudorandom number generators Category:Non-uniform random numbers