{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/81665"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/81665","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Random Number Generation Using a Biased Source","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Pae, Sung-il"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Loui, Michael C."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-25T20:19:55Z","date_published":"2015-09-25T20:19:55Z","updated_at":"2026-07-22T22:26:16Z","subjects":["Engineering, Electronics and Electrical"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI3182342"],"render_values":[{"text":"(MiAaPQ)AAI3182342","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/81665","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Loui, Michael C."]},{"key":"dc:creator","label":"Author","values":["Pae, Sung-il"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-25T20:19:55Z","10000-01-01","2005"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/81665","(MiAaPQ)AAI3182342"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2015-09-25T20:19:55Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3182342.pdf: 2882247 bytes, checksum: 05bc77c24e1cbdb18f328026276b9ff2 (MD5) Previous issue date: 2005","Embargo set by: Seth Robbins for item 82946 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","81 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2005."]},{"key":"dc:title","label":"Title","values":["Random Number Generation Using a Biased Source"]}]}],"canonical_facts":{"dc:contributor":["Loui, Michael C."],"dc:creator":["Pae, Sung-il"],"dc:date":["2015-09-25T20:19:55Z","10000-01-01","2005"],"dc:description":["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.","Made available in DSpace on 2015-09-25T20:19:55Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3182342.pdf: 2882247 bytes, checksum: 05bc77c24e1cbdb18f328026276b9ff2 (MD5) Previous issue date: 2005","Embargo set by: Seth Robbins for item 82946 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","81 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2005."],"dc:identifier":["http://hdl.handle.net/2142/81665","(MiAaPQ)AAI3182342"],"dc:language":["eng"],"dc:subject":["Engineering, Electronics and Electrical"],"dc:title":["Random Number Generation Using a Biased Source"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:16Z"}