Turning a Biased Coin into an Unbiased one Deterministically

Question

Non-deterministic Exact Algorithm

There is a simple algorithm to turn a biased coin into a fair one:

1. Flip the coin twice.
2. Identify HT with H and TH with T.
3. Discard cases HH and TT.

This algorithm produces a perfectly fair coin, but it is non-deterministic.

Deterministic Approximation

I also know it is possible to approximate a fair coin with a deterministic algorithm:

Let $C_0$ be the biased coin and define $C_1$ by flipping $C_0$ twice. $C_1$ is H if $C_0$ was HH or TT, and $C_1$ is T if $C_0$ was HT or TH.

We can see that if the probability that $C_0$ was heads is $p$, then the probability that $C_1$ is heads is $p_1 = 1 - 2p(1 - p)$. This is a parabola connecting $(0,1), (.5,.5)$, and $(1,1)$ and we can see that if we assume $0<p<1$ then the function has a fixed point at $0.5$. Since $0.5 < p_1 < p$ if $p>0.5$ and $0.5<p_1<1$ if $p<0.5$, then we can see that a fixed point iteration with $0<p<1$ will always converge to $0.5$. Therefore, we can find a deterministic $C_i$ that is arbitrarily fair (defined by flipping $C_{i-1}$ twice).

My Problem

I am trying to find out if, given some biased coin with rational probability of heads $p$, we can construct an algorithm to solve this problem that is both deterministic and exact. Does anyone have any insights?

(Note that the algorithm only has to work for a fixed probability $p$, since as pointed out in the comments and answer, there are some $p$, e.g., $p = 1/3$ for which there is no such algorithm.)

Answer 1

An algorithm that works for any $p$ doesn't exist. It is possible to solve the problem for some $p$.

Let $p$ be the probability of heads.

Consider a deterministic algorithm $F$ which uses $n$ tosses. Denote $A$ the set of all possible sequences of $n$ coin tosses ($|A| = 2^n$). The $F$ is essentially a function $F: A \to \{0, 1\}$, which returns 0 (heads) for some sequences of $n$ tosses, and 1 (tails) for the rest.

Our deterministic algorithm defines two sets, $H = \{v \in A | F(v) = 0\}$ - the set of $n$-toss sequences where out algorithm decided heads, and $T = A \setminus H$, such that $\mathbb{P}[H] = \mathbb{P}[T] = 0.5$.

On the other hand, for any sequence $v \in A$ denote $h(v)$ be the number of tails in $v$. $$\mathbb{P}[H] = \sum_{v \in H}\mathbb{P}[v] = \sum_{v \in H} p^{h(v)}(1-p)^{n - h(v)} {\hspace{2cm}} [1]$$

We need to make this $\frac{1}{2}$.

Let $p = \frac{r}{q}$ when fully reduced. Then $$p^{h(v)}(1-p)^{n - h(v)} = \frac{r^{h(v)}(q-r)^{n-h(v)}}{q^n}$$

Let's count how many times each possible value of $h(v)$ appears in the sum [1]:

Denote $c_k = |\{v | v \in H \text{ and } h(v)=k \}|$. Then [1] becomes

$$\mathbb{P}[H] = \sum_{k=0}^n c_k \frac{r^{k}(q-r)^{n-k}}{q^n} = \frac{\sum_{k=0}^n c_k r^{k}(q-r)^{n-k}}{q^n} = \frac{1}{2}$$

An algorithm that works for all $p$ doesn't exist, because if $q$ is odd, there is no way to introduce a factor of $2$ in the denominator of this expression. The best we can do is, given a $p$, try to find an algorithm that works for that specific $p$, or determine that such doesn't exist.

Since there are $n \choose k$ sequences of coin tosses with length $n$ and $k$ heads, we also need $c_k \leq {n \choose k}$.

If $q$ is even, and we have a solution to the following equation, satisfying the bounds on $c_k$ $$\sum_{k=0}^n c_k r^{k}(q-r)^{n-k} = \frac{q^n}{2}$$

Then we can simply include $c_k$ sequences containing $k$ heads in $H$ for each $k$ to get our algorithm.

Note that this equation has finitely many potential solutions, so we can simply try them all.