# Turning a Biased Coin into an Unbiased one Deterministically

## 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 then the function has a fixed point at $$0.5$$. Since $$0.5 < p_1 < p$$ if $$p>0.5$$ and $$0.5 if $$p<0.5$$, then we can see that a fixed point iteration with $$0 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.)

• Do we know $p$ beforehand? Can the algorithm depend on $p$? There is no algorithm that works for all $p$, but for some values of $p$, such as $\frac{1}{4}$ it is possible to have a deterministic algorithm. – Todor Markov Nov 16 '18 at 11:04
• Yes, we know $p$ beforehand, so we can take as much time as we need to pre-compute, say, a decision tree. I'll update this in the question. – helper Nov 16 '18 at 14:44

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.

• The problem says $p$ is rational. I think you can modify your arguments to $\mathbb{P}[H]$ has denominator of the form $q^m$, which is an odd number, where $p = \frac{q'}{q}$, so there is a solution only when $p=\frac{1}{2}$. – Qidi Nov 16 '18 at 9:44
• My bad I missed that. Thanks for the tip. – Todor Markov Nov 16 '18 at 10:17
• You mean there are some $p$ for which there is no algorithm. For some $p$ it is possible, for instance $p=1/4$. – Michal Adamaszek Nov 16 '18 at 10:57
• @Michael Adamaszek Yes. The way I understand the problem, you don't actually know $p$ beforehand to be able to tune your algorithm to it. Indeed, both example algorithms shown in the first post work for any $p$ unaltered. But it is worth clarifying that. – Todor Markov Nov 16 '18 at 11:02
• Updated answer to include the case when we want an algorithm for a specific $p$. – Todor Markov Nov 16 '18 at 11:44