IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Random Number Generation Using a Biased Source

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/11103

Files in this item

File Description Format
PDF Random Number Generation Using a Biased Source.pdf (500KB) (no description provided) PDF
Title: Random Number Generation Using a Biased Source
Author(s): Pae, Sung-il
Subject(s): random number generation algorithms
Abstract: We study random number generation using a biased source motivated by previous works on this topic, mainly, von Neumman (1951), Elias (1972), Knuth and Yao (1976) and Peres (1992). We study the problem in two cases: first, when the source distribution is unknown, and second, when the source distribution is known. In the first case, we characterize the functions that use a discrete random source of unknown distribution to simulate a target discrete random variable with a given rational distribution. We identify the functions that minimize the ratio of source inputs to target outputs. We show that these optimal functions are efficiently computable. In the second case, we prove that it is impossible to construct an optimal tree algorithm recursively, using algebraic decision procedures. Our model of computation is sufficiently general to encompass previously known algorithms for this problem. Pae, Sung-il
Issue Date: 2005-05
Genre: Technical Report
Type: Text
URI: http://hdl.handle.net/2142/11103
Other Identifier(s): UIUCDCS-R-2005-2527
Rights Information: You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS: 2009-04-20
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 701
  • Downloads this Month: 27
  • Downloads Today: 0

Browse

My Account

Information

Access Key