21

(Von Neumann gave an algorithm that simulates a fair coin given access to identical biased coins. The algorithm potentially requires an infinite number of coins (although in expectation, finitely many suffice). This question concerns the case when the number of coin tosses allowed is bounded.)

Suppose we have $n$ identical coins with bias $\delta=P[Head]-P[Tail]$. The aim is to simulate a single coin toss while minimizing bias.

The simulation must be efficient in the following sense: An algorithm running in polynomial time looks at $n$ random bits and outputs a single bit. The bias of the algorithm is defined as $Bias(A)=|E[A=0]-E[A=1]|$ where the expectation is taken over the distribution defined by $n$ i.i.d bits ${x_1,\ldots,x_n}$ such that $Prob[x_i=1]-Prob[x_i=0]=\delta$.

Which algorithm $A$ running in polynomial time has the least bias $Bias(A)$?

This question seems very natural to me and it is very likely that it has been considered before.

What is known about this problem? Is anything known when a weaker class (in $AC_0$, etc.) of algorithms is considered?

Hrushikesh
  • 376
  • 1
  • 7

6 Answers6

15

Tossing n biased coins and taking the parity of heads gets exponentially close to $\frac{1}{2}$.

[For a proof, consider a random variable that is -1 when heads and 1 when tails, then the probability that there are an odd number of heads is just the $E\left[\frac{1}{2} + \frac{1}{2}\prod_i X_i\right] = \frac{1}{2} + \frac{1}{2}\delta^n$]

Perhaps this is also optimal for the following reason. Let $f$ be any composition function of these bits. Then, the $\text{Bias}(f) = \sum_S \hat{f}(S) \delta^{|S|}$ and the best $f$ seems to be the parity function (isn't it?).

If you are interested in composition functions of lower complexity, then perhaps a paper of Ryan O'Donnell on `Hardness amplification within NP' would be very relevant. There he uses monotone composition functions for hardness amplifications and the functions that work are characterized by their noise sensitivity.

Ramprasad
  • 2,482
  • 18
  • 18
  • Could you kindly elaborate why parity should be the best function? (Also, not that it matters much asymptotically, but shouldn't that be $delta^{|S|}$ in the Fourier expansion since $E[x_i]=\delta$?). Thanks for the pointer to the paper! – Hrushikesh Sep 27 '10 at 04:42
  • Oh I'm sorry, you are right. The expression was incorrect and have now corrected it.

    I don't have a proof of the optimality (perhaps it is not optimal) but the reason I guessed so was that it would be true if the expression was instead $\sum_S \hat{f}(S)^2 \delta^{|S|}$ since this is then a convex combination.

     – Ramprasad Sep 27 '10 at 05:37
  • Perhaps this might shed some light. By Cauchy-Schwarz, we know that $\sum_{S} \hat{f}(S) \leq \sqrt{\sum_{S:\hat{f}(S)\neq 0} \delta^{2|S|}}$. One way of optimizing would be minimize the upper-bound as much as possible and that happens when the function $f$ is the parity function and in that case the quantity we are interested in matches the upper-bound as well. However, it might be the case that the vector of fourier coefficients is completely orthogonal to the $\delta$-vector in which case the LHS is just zero! Are there special values of $\delta$ for which we know such examples? – Ramprasad Sep 27 '10 at 11:40
  • Actually, if one were to take some non-trivial monotone function $f$, then at $\delta = -1$ the expectation the probability of $f(x_1,\cdots, x_n) = 1$ is 0 and at $\delta=1$ it is $1$. Hence, for some intermediate $\delta$, it must take the value $\frac{1}{2}$. Hence it is not fair to expect that for every $\delta$, the parity function is optimal. – Ramprasad Sep 29 '10 at 05:30
  • Can you explain the last comment in more detail? Disregarding issues of f's complexity, isn't your conclusion true only if $E[f]=1/2$ for a $\delta \geq \frac{1}{2^{1/n}}$ since parity takes bias from $\delta$ to $\delta^n$? – Hrushikesh Oct 01 '10 at 19:11
  • Suppose you take the function $f$ to be the OR function. Then, if $\delta= -1$, then $E_\delta [f] = 0$ (since all bits are always zero). And if $\delta = 1$ then $E_\delta [f] = 1$. And as you slowly increase $\delta$ from -1 to 1, the expectation also increases. Therefore, there must be some $\delta$ for which $E_\delta [f] = 0$. Well, this is perhaps trivial but the reason I posted this was that I had initially thought that the parity was the best function for every delta. But, this just shows that there are deltas for which the OR function does better! – Ramprasad Oct 03 '10 at 06:33
12

You do not say if the bias is known or unknown. The magic of von Neumann's algorithm is that it works in either case.

Suppose it is known. The best answer then depends critically on number-theoretical features of the bias. Let's take p = 2/3. Toss the coin twice and map HH to 0 and TH and HT to 1, repeating the experiment if the outcome is TT. Then 0 and 1 are equally likely and the chance of a repeat is only 1/9 instead of 5/9 with von Neumann's algorithm. Or to put it in your terms, you only bias one of the outcomes by 1/9 if your iteration limit is 2.

This is all closely related to information theory and coding theory. When p is a fraction with a more complicated numerator and denominator, the best algorithm will require a longer block length than 2. You can use a Shannon-style existence argument to show that for a given bias there is a procedure which is as optimal as you want, but the block length can get very large.

Peres in his paper Iterating Von Neumann's Procedure for Extracting Random Bits proves that a version of von Neumann's algorithm can approach the Shannon limit arbitrarily well. A lot of the work in this area seems to have been done by information theorists and statisticians, so I can't think of any paper with a complexity-theoretic slant that would give you a direct answer to your question.

There is a fun related problem which asks the opposite: If you have a source of fair bits, how do you efficiently generate a uniform distribution over some non-power-of-two set? The iteration-limited version of the problem that is akin to your question asks to maximize the entropy (i.e. make the distribution as uniform as possible) with n tosses of a fair coin.

Per Vognsen
  • 2,161
  • 16
  • 25
  • 1
    It occurred to me that optimizing running time subject to no bias (what the paper does) is Lagrange dual to optimizing bias subject to running time. So, I think that paper actually answers your question! – Per Vognsen Sep 26 '10 at 13:05
5

I prefer to think of the question in the following generalized form: we have a complete binary tree of hight n, where each node is assigned a number s.t. sum of the numbers is 1. Can we partition the leaves to two sets s.t. the sums of numbers them are close?

If we have biased coin with parameter $p$ and $q=1-p$, the nodes will have values $p^i q^{n-i}$.

As noted in other answers, for most piratical purposes taking parity of the bits is good. The bias will be $\sum_{i} {\binom{n}{i} parity(x) p^i q^{n-i}} = \sum_{i} {\binom{n}{i} (-p)^i q^{n-i}} = (q-p)^n$.

In general, if we have enough computing resources (say $PSpace$ in number of random bits), we can partition the nodes in the best possible way.

EDIT "This is basically the Shannon coding problem." (Thanks to Per Vognsen.) END of EDIT

On the other hand, if we are only allowed to use $AC^0$, then it is not hard to show that we can not achieve much because of switching lemma. The circuit will be approximated exponentially well by a CNF and it is not hard to show that a CNF can not compute an answer with a good bias.

(This answer may contain errors, I have not checked the details.)

Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • 2
    "Can we partition the leaves to two sets s.t. the sums of numbers them are close?" This is basically the Shannon coding problem. The Shannon-Fano algorithm is top-down and starts with a set of probability-weighted elements and asks for an even-as-possible bipartition. Applying this recursively gives an integral prefix-free code. The Huffman algorithm is bottom-up: it starts with singleton trees and repeatedly merges pairs with closest probability. If you know about arithmetic coding, this also rightly suggests that it's better to generate multiple fair bits at once rather than one at a time. – Per Vognsen Sep 26 '10 at 11:27
4

You can also get many random bits out of biased coins, see Gabizon's paper Derandomizing algorithms under Product Distributions (http://sites.google.com/site/arielgabizon1/)

3

Related question, different site: whitening a random bit sequence

Community
  • 1
BCS
  • 151
  • 6
1

If you want an even number of coin tosses to be unbiased with a biased coin, the easy way to remove bias is reverse the result of every other toss.

Dean J
  • 111
  • 3
  • 1
    This won't of course result in a uniformly random sequence. Imagine the limiting case as the bias of the coin goes to 1 -- you just get a deterministic alternating sequence of bits. – Aaron Roth Sep 28 '10 at 00:48
  • Any strategy that bijectively remaps outcomes will preserve the entropy, so it can't change the distribution from non-maximal entropy (biased) to maximal entropy (unbiased). – Per Vognsen Sep 28 '10 at 01:10