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 perform 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}random variable (as n --> infinity). A {-1, 1} random variable has bias b if E(X(i)) = b. Fixing a bias b, we explore the rate at which the output bias \E(f(X(1), ..., X(n)))\ can tend to zero for a function f: {-1, 1}* --> {-1, 1}. This is accomplished by classifying 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 sequences to suit our problem, we then explore the case where b is irrational. We prove a new metrical theorem concerning multidimensional Diophantine approximation type from which we show that for (Lebesgue) almost all biases b, Theta(b) = 0. Finally, we show that algebraic biases exhibit curious "boundary" behavior, falling into two classes. Class 1. Those algebraics b for which Theta(b) > 0 and, furthermore, c(1) less 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 discuss natural extensions where output distributions other than the uniform distribution on {-1, 1} are sought.
bias randomness random variables diophantine approximation type computation