Given a coin with unknown bias, generate variates from a fair coin efficiently

Question

Given a coin with unknown bias $p$, how can I generate variates — as efficiently as possible — that are Bernoulli-distributed with probability 0.5? That is, using the minimum number of flips per generated variate.

Answer 1

This is a well-known problem with several nice solutions which have been discussed here and in stackoverflow (it seems like I cannot post more than one link but a quick google search gives you some interesting entries). Have a look at the wikipedia entry

http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin

Answer 2

This is a classic problem, I believe attributed originally to von Neumann. One solution is to keep tossing the coin in pairs until the pairs are different, and then defer to the outcome of the first coin in the pair.

Explicitely let $(X_i,Y_i)$ be the outcome of toss $i$, with $X_i$ being the first coin, and $Y_i$ being the second coin. Each coin has probability $p$ of heads. Then $P(X_i=H|X_i\neq Y_i)=P(X_i=T|X_i\neq Y_i)$ due to symmetry, which implies $P(X_i=H|X_i\neq Y_i)=1/2$. To explitely see this symmetry note that $X_i\neq Y_i$ implies the outcomes are $(H,T)$ or $(T,H)$, both of which are equally likely due to independence.

Empirically, the waiting time until such an unequal pair is

$$1/P(X\neq Y)=\frac{1}{1-p^2-(1-p)^2}=\frac{1}{2p(1-p)},$$

which blows up as $p$ gets closer to 0 or 1 (which makes sense).

Answer 3

I'm not sure how to sum up the terms efficiently, but we can stop whenever the total number of rolls $n$ and the total number of successes $t$ are such that $\binom{n}{t}$ is even since we can partition the different orderings that we could have achieved $n$ and $t$ into two groups of equal probability each corresponding to a different outputted label. We need to be careful that we haven't already stopped for these elements, i.e., that no element has a prefix of length $n'$ with $t'$ successes such that $\binom{n'}{t'}$ is even. I'm not sure how to turn this into an expected number of flips.

To illustrate:

We can stop at TH or HT since these have equal probability. Moving down Pascal's triangle, the next even terms are in the fourth row: 4, 6, 4. Meaning that we can stop after rolls if one heads has come up since we can create a bipartite matching: HHHT with HHTH, and technically HTHH with THHH although we would already have stopped for those. Similarly, $\binom42$ yields the matching HHTT with TTHH (the rest, we would already have stopped before reaching them).

For $\binom52$, all of the sequences have stopped prefixes. It gets a bit more interesting at $\binom83$ where we match FFFFTTFT with FFFFTTTF.

For $p=\frac12$ after 8 rolls, the chance of not having stopped is $\frac1{128}$ with an expected number of rolls if we have stopped of $\frac{53}{16}$. For the solution where we keep rolling pairs until they differ, the chance of not having stopped is $\frac{1}{16}$ with an expected number of rolls if we have stopped of 4. By recursion, an upper bound on the expected flips for the algorithm presented is $\frac{128}{127} \cdot \frac{53}{16} = \frac{424}{127} < 4$.

I wrote a Python program to print out the stopping points:

import scipy.misc
from collections import defaultdict


bins = defaultdict(list)


def go(depth, seq=[], k=0):
    n = len(seq)
    if scipy.misc.comb(n, k, True) % 2 == 0:
        bins[(n,k)].append("".join("T" if x else "F"
                                   for x in seq))
        return
    if n < depth:
        for i in range(2):
            seq.append(i)
            go(depth, seq, k+i)
            seq.pop()

go(8)

for key, value in sorted(bins.items()):
    for i, v in enumerate(value):
        print(v, "->", "F" if i < len(value) // 2 else "T")
    print()

prints:

FT -> F
TF -> T

FFFT -> F
FFTF -> T

FFTT -> F
TTFF -> T

TTFT -> F
TTTF -> T

FFFFFT -> F
FFFFTF -> T

TTTTFT -> F
TTTTTF -> T

FFFFFFFT -> F
FFFFFFTF -> T

FFFFFFTT -> F
FFFFTTFF -> T

FFFFTTFT -> F
FFFFTTTF -> T

FFFFTTTT -> F
TTTTFFFF -> T

TTTTFFFT -> F
TTTTFFTF -> T

TTTTFFTT -> F
TTTTTTFF -> T

TTTTTTFT -> F
TTTTTTTF -> T