Krdytkyu

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.)

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.