Flip a coin. It either lands heads or tails. Given a "normal" coin, you would expect that the coin is just as likely to land heads as it is to land tails. That is, after flipping the coin many times, you would expect to get heads about 50% of the time. We would then say that for a normal coin the probability of getting heads is 0.5 (which, in turn, means that the probability of getting tails is a corresponding 1 - 0.5 = 0.5). Such a coin is unbiased, that is, the probability of getting heads equals the probability of getting tails.
Consider now a biased coin. When tossed, this coin is more (or less) likely to land heads than tails. The probability is no longer 50%/50% - it may be something like 20%/80% instead.
The Puzzle:
Your task is to devise a method to generate random unbiased bits (0 or 1) by flipping a biased coin.
Given a probability p of your coin landing heads and using your method, how many times will you need to flip your coin on average to write 10 bits? 20 bits? n bits?
From a problem set in Jim Fix's class on Complexity Theory.
|
|
Think you got the answer? Send it to me and earn eternal (ephemeral?) fame --> 
|
|
|