An Interesting Random Number Problem

Filed under Uncategorized

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?)


Additional Reading:

One Comment

  1. eBusiness says:

    Such a good question and no one answered for the better part of 4 years.

    In any case: Read two bits, if they are identical discard them and read two new, continue to do so until they are different. Return the first bit from the final pair.

    This works because the chance of drawing the pairs [1 0] and [0 1] are identical, the absolute chance varies depending on how skewed the random function is, but the variance is completely identical.

Post a Reply to eBusiness

Your email is never published nor shared. Required fields are marked *

*
*