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

  • 1
    $\begingroup$ 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. $\endgroup$ – Todor Markov Nov 16 '18 at 11:04
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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}$. $\endgroup$ – Qidi Nov 16 '18 at 9:44
  • $\begingroup$ My bad I missed that. Thanks for the tip. $\endgroup$ – Todor Markov Nov 16 '18 at 10:17
  • $\begingroup$ You mean there are some $p$ for which there is no algorithm. For some $p$ it is possible, for instance $p=1/4$. $\endgroup$ – Michal Adamaszek Nov 16 '18 at 10:57
  • $\begingroup$ @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. $\endgroup$ – Todor Markov Nov 16 '18 at 11:02
  • $\begingroup$ Updated answer to include the case when we want an algorithm for a specific $p$. $\endgroup$ – Todor Markov Nov 16 '18 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.