<p>Besides the von Neumann procedure given in other answers, there is a whole family of techniques, called <em>randomness extraction</em> (also known as <em>debiasing</em>, <em>deskewing</em>, or <em>whitening</em>), that serve to produce unbiased random bits from random numbers of unknown bias. They include Peres's (1992) iterated von Neumann procedure, as well as an &quot;extractor tree&quot; by Zhou and Bruck (2012). Both methods (and several others) are <em>asymptotically optimal</em>, that is, their efficiency (in terms of output bits per input) approaches the optimal limit as the number of inputs gets large (Pae 2018).</p>
<p>For example, the Peres extractor takes a list of bits (zeros and ones with the same bias) as input and is described as follows:</p>
<ol>
<li>Create two empty lists named U and V. Then, while two or more bits remain in the input:
<ul>
<li>If the next two bits are 0/0, append 0 to U and 0 to V.</li>
<li>Otherwise, if those bits are 0/1, append 1 to U, then write a 0.</li>
<li>Otherwise, if those bits are 1/0, append 1 to U, then write a 1.</li>
<li>Otherwise, if those bits are 1/1, append 0 to U and 1 to V.</li>
</ul>
</li>
<li>Run this algorithm recursively, reading from the bits placed in U.</li>
<li>Run this algorithm recursively, reading from the bits placed in V.</li>
</ol>
<p>This is not to mention procedures that produce unbiased random bits from biased <em>dice</em> or other biased random numbers (not just biased bits); see, e.g., Camion (1974).</p>
<p>I discuss more on randomness extractors in a <a href="https://peteroupc.github.io/randextract.html" rel="nofollow noreferrer">note on randomness extraction</a>.</p>
<p>REFERENCES:</p>
<ul>
<li>Peres, Y., &quot;Iterating von Neumann's procedure for extracting random bits&quot;, Annals of Statistics 1992,20,1, p. 590-597.</li>
<li>Zhou, H. And Bruck, J., &quot;<a href="https://arxiv.org/abs/1209.0730" rel="nofollow noreferrer">Streaming algorithms for optimal generation of random bits</a>&quot;, arXiv:1209.0730 [cs.IT], 2012.</li>
<li>S. Pae, &quot;<a href="https://arxiv.org/abs/1602.06058v2" rel="nofollow noreferrer">Binarization Trees and Random Number Generation</a>&quot;, arXiv:1602.06058v2 [cs.DS].</li>
<li>Camion, Paul, &quot;Unbiased die rolling with a biased die&quot;, North Carolina State University. Dept. Of Statistics, 1974.</li>
</ul>
Unbiased random number generator using a biased one
<p>You have a biased random number generator that produces a 1 with a probability p and 0 with a probability (1-p). You do not know the value of p. Using this make an unbiased random number generator which produces 1 with a probability 0.5 and 0 with a probability 0.5.</p>

<p><strong>Note</strong>: this problem is an exercise problem from Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein.(clrs)</p>