How to combine $n$ 'less random' bits to generate one 'more random' bit? Suppose we have a random number generator badrand() generating 1 with probability $0.9$ and 0 with probability $0.1$.
How can we combine $n$ bits from badrand() to get one bit of betterrand()? What will be its probability of giving a 0 or 1?
I assume that this is possible since the entropy of the combined output increases with each call to badrand(). Please guide me if I am wrong.
If the outputs of badrand are independent and identically distributed you can use a randomness extractor function with $m=1$ and $k=-n\lg 0.9$.
If you're prepared to have a non-deterministic waiting time for an output, the von Neumann extractor is good way to get probability exactly 0.5 out of i.i.d. bit outputs. Sample pairs of bits until you get a pair with precisely one zero; if your pair is 01 return 0 and if it is 10 return 1. The i.i.d property means that the probability of these two events is equal (in your example both have probability 0.09 and resampling has probability 0.82, leading you to expect around 100/9 badrand outputs to produce one betterrand output).