How to adjust the distribution of values in a random data stream?

Question

Given a infinite stream of random 0's and 1's that is from a biased (e.g. 1's are more common than 0's by a know factor) but otherwise ideal random number generator, I want to convert it into a (shorter) infinite stream that is just as ideal but also unbiased.

Looking up the definition of entropy finds this graph showing how many bits of output I should, in theory, be able to get from each bit of input.

The question: Is there any practical way to actually implement a converter that is nearly ideally efficient?

Answer 1

There is a well-known device due to Von Neumann for turning an unfair coin into a fair coin. We can use this device to solve our problem here.

Repeatedly draw two bits from your biased source until you obtain a pair for which the bits are different. Now return the first bit, discarding the second. This produces an unbiased source. The reason this works is because regardless of the source, the probability of a 01 is the same as a probability of a 10. Therefore the probability of a 0 conditional on 01 or 10 is 1/2 and the probability of a 1 conditional on 01 or 10 is 1/2.

Answer 2

Please see

• http://en.wikipedia.org/wiki/Randomness_extractor

• http://en.wikipedia.org/wiki/Whitening_transform

• http://en.wikipedia.org/wiki/Decorrelation

Answer 3

Hoffman encode the input.

Given that the input is of a known bias, you can compute a probability distribution for check sums of each n bit segment. From that construct a Hoffman code and then just encode the sequence.

I'm not sure but one potential problem is that this might introduce some correlation between sequential bits.