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 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 instead.
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%.
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?)