Efficient Techniques for Unbiasing a Bernoulli Generator,

Consider the problem of operating on a sequence of i.i.d. Bernoulli variables with unknown mean p to produce a sequence of symmetric Bernoulli variables. Define the efficiency of any proposed method to be the average number of output digits per input digit. The following results are proved A No method exists having efficiency greater than -p log of p to the base 2 - q log of q to the base 2, where q is identically equal to 1 - p. B Methods do exist with efficiency arbitrarily close to the bound just given. Examples are given, and compared with other methods in the literature. A technique for finding the methods of B is given. Author