In Systems Security class, the professor presented us with an interesting homework problem involving random numbers which I thought some of you might enjoy.<\/p>\n
To begin with, a perfect random number generator<\/em> is a mythical device which spits out bits of either 0 or 1 completely randomly, with a 50% chance of spitting out either a 0 or a 1 at any time regardless of what bits it’s output in the past. Of course, such a generator is impossible to create in deterministic machines (computers), so programmers use pseudo-random number generators<\/a> instead.<\/p>\n Now, the problem: Assume you have a biased-random number generator – that is, you have a magical random number generator which is completely non-deterministic, but the probability of outputting one bit-state is higher than the other. For example, it could output a "1" with 60% probability and a "0" with 40% probability, or perhaps output a "1" with 0.01% probability and a "0" with 99.99% probability. The only thing known about the probability of outputting a 0\/1 is that it’s fixed and greater than 0%. In Systems Security class, the professor presented us with an interesting homework problem involving random numbers which I thought some of you might enjoy. To begin with, a perfect random number generator is a mythical device which spits out bits of either 0 or 1 completely randomly, with a 50% chance of spitting out either […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/posts\/152"}],"collection":[{"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/comments?post=152"}],"version-history":[{"count":1,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/posts\/152\/revisions"}],"predecessor-version":[{"id":153,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/posts\/152\/revisions\/153"}],"wp:attachment":[{"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/media?parent=152"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/categories?post=152"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blueraja.com\/blog\/wp-json\/wp\/v2\/tags?post=152"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n Given only a computer which can read bits from this biased-random number generator, can you create a perfect random number generator? (and if so, how?)<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"