Extraction of optimally unbiased bits from a biased source

We explore the problem of transforming n independent and identically biased {-1, 1}-valued random variables X-1, ..., X-n into a single {-1, 1} random 'iariable f(X-1, ..., X-n), so that this result is as unbiased as possible . In general, no function f produces a completely unbiased result. We perfo rm the first study of the relationship between the bias b of these X-i and the rate at which f(X-1, ..., X-n) can converge to an unbiased {-1, 1}rando m variable (as n --> infinity). A {-1, 1} random variable has bias b if E(X-i) = b. Fixing a bias b, we exp lore the rate at which the output bias \E(f(X-1, ..., X-n))\ can tend to ze ro for a function f: {-1, 1}* --> {-1, 1}. This is accomplished by classify ing the behavior of the natural normalized quantity [GRAPHICS] this infimum taken over all such f. We show that for rational b, Theta(b) = (1/s), where (1 + b/2) (r/s) (r and s relatively prime). Developing the theory of uniform distribution of sequ ences to suit our problem, we then explore the case where b is irrational. We prove a new metrical theorem concerning multidimensional Diophantine app roximation type from which we show that for (Lebesgue) almost all biases b, Theta(b) = 0. Finally, we show that algebraic biases exhibit curious "boun dary" behavior, falling into two classes. Class 1. Those algebraics b for which Theta(b) > 0 and, furthermore, c(1) l ess than or equal to Theta(b) less than or equal to c(2) where c(1) and c(2 ) are positive constants depending only on b's algebraic characteristics. Class 2. Those algebraics b for which there exist n > 0 and f : {-1, 1}(n) --> {-1, 1) SO that E(f(X-1, ..., X-n)) = 0. Notice that this classification excludes the possibility that (n)root\E(f(x(1), ..., x(n)))\ limits to zero (for algebraics). For rational and algebraic biases, we also study the computational problem by restricting f to be a polynomial time computable function. Finally, we d iscuss natural extensions where output distributions other than the uniform distribution on {-1, 1} are sought.