<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>Peres in his paper <a href="http://www.stat.berkeley.edu/~peres/mine/vn.pdf" rel="nofollow">Iterating Von Neumann's Procedure for Extracting Random Bits</a> 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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-26T13:05:40.830Z
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
CC BY-SA 2.5
2010-09-26T07:59:48.653Z
2010-09-26T08:43:34.463Z
2010-09-26T08:43:34.463Z
Per Vognsen
<p>Tossing n biased coins and taking the parity of heads gets exponentially close to $\frac{1}{2}$. </p>

<p>[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$]</p>

<p>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?). </p>

<p>If you are interested in composition functions of lower complexity, then perhaps a paper of Ryan O'Donnell on <a href="http://www.cs.cmu.edu/~odonnell/papers/hardness.pdf" rel="nofollow">`Hardness amplification within NP'</a> would be very relevant. There he uses monotone composition functions for hardness amplifications and the functions that work are characterized by their noise sensitivity. </p>

CC BY-SA 2.5
2010-09-27T04:42:49.763Z
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
CC BY-SA 2.5
2010-09-27T05:37:38.643Z
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
CC BY-SA 2.5
2010-09-27T11:40:29.680Z
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
CC BY-SA 2.5
2010-09-29T05:30:51.443Z
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
CC BY-SA 2.5
2010-10-01T19:11:32.797Z
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
CC BY-SA 2.5
2010-10-03T06:33:48.547Z
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
CC BY-SA 2.5
2010-09-26T07:41:40.457Z
2010-09-27T05:38:12.167Z
2010-09-27T05:38:12.167Z
Ramprasad
<p>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?</p>

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

<p>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$.</p>

<p>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. </p>

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

<p>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.</p>

<p>(This answer may contain errors, I have not checked the details.)</p>

CC BY-SA 2.5
2010-09-26T11:27:03.593Z
"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
CC BY-SA 2.5
2010-09-26T11:15:39.523Z
2010-09-26T11:34:48.907Z
2010-09-26T11:34:48.907Z
Kaveh
<p>Related question, different site: <a href="https://mathoverflow.net/questions/29545/whitening-a-random-bit-sequence">whitening a random bit sequence</a></p>

CC BY-SA 2.5
2010-09-26T16:36:57.920Z
2010-09-26T16:36:57.920Z
2017-04-13T12:57:54.777Z
BCS
<p>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.</p>

CC BY-SA 2.5
2010-09-28T00:48:41.580Z
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
CC BY-SA 2.5
2010-09-28T01:10:04.227Z
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
CC BY-SA 2.5
2010-09-27T17:54:22.913Z
2010-09-27T17:54:22.913Z
Dean J
<p>(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.)</p>

<p>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. </p>

<p>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$.</p>

<blockquote>
  <p>Which algorithm $A$ running in polynomial time has the least bias $Bias(A)$?</p>
</blockquote>

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

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

<cc.complexity-theory><circuit-complexity><pr.probability>
What is the best way to get a close-to-fair coin toss from identical biased coins?
Hrushikesh
# What is the best way to get a close-to-fair coin toss from identical biased coins?

(Asked by: username_0 on 2010-09-26)

(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?

**Tags:** cc.complexity-theory, circuit-complexity, pr.probability


---

## 5 answers

### Answer by username_2 on 2010-09-26. Score: 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'](http://www.cs.cmu.edu/~odonnell/papers/hardness.pdf) would be very relevant. There he uses monotone composition functions for hardness amplifications and the functions that work are characterized by their noise sensitivity.

> **Comments:**
> **username_0**: 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!  
> **username_2**: 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.  
> **username_2**: 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?  
> **username_2**: 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.  
> **username_0**: 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$?  
> **username_2**: 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!  

---

### Answer by username_1 on 2010-09-26. Score: 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](http://www.stat.berkeley.edu/~peres/mine/vn.pdf) 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.

> **Comments:**
> **username_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!  

---

### Answer by username_3 on 2010-09-26. Score: 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 username_1.)
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.)

> **Comments:**
> **username_1**: "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.  

---

### Answer by username_4 on 2010-09-26. Score: 3

Related question, different site: [whitening a random bit sequence](https://mathoverflow.net/questions/29545/whitening-a-random-bit-sequence)


---

### Answer by username_5 on 2010-09-27. Score: 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.

> **Comments:**
> **username_6**: 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.  
> **username_1**: 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).  

---

