Otdfbt

Given two numbers $p,qin(0,1)$, we say that $p$ can simulate $q$ if, given a biased coin with probability $p$, we can toss it a bounded number of times and use the results to simuate a biased coin with probability $q$.

In this math.SE question the following results were proved:

• No rational number except $1/2$ can simulate $1/2$;


• Some irrational numbers can simulate $1/2$, for example: $1/2 pm 1/sqrt12$, or $1/2^1/n$ for any integer $n$.

Q1. What is the set of all numbers $pin (0,1)$ which can simulate $1/2$?

Q2. What is the set of all numbers $pin (0,1)$ which can simulate $1/3$?

Depends on what kind of "description" you want, but consider the question of the probabilities $p$ that can simulate $1/2$ with exactly $n$ flips. The events you have are:

• One event with probability $p^n$
  


• 
  $n$ events with probability $p^n-1(1-p)$
  


• 
  $binomn2$ events with probability $p^n-2(1-p)^2$
  


• ...


• One event with probability $(1-p)^n$
  

So if you pick any integers $a_0, a_1, ldots a_n$ with $0 leq a_i leq binomni$ then you get a polynomial that $p$ has to satisfy. Of course such a polynomial may or may not have a root on $(0, 1)$, but we can at least enumerate the solutions in this manner.

Clearly transcendental values for $p$ are right out. Moreover we have an explicit description of what the minimal polynomial of a solution has to look like, and any number $p in (0, 1)$ satisfying such a polynomial is indeed a solution.

In some sense that could be considered a complete answer, although maybe we want to know which potential minimal polynomials correspond to actual solutions.

Notice that if we have two symmetries here. First, a biased coin that comes up heads with probability $p$ is just as good as a biased coin that comes up heads with probability $1 - p$; we can just relabel "heads" and "tails" on the coin. Second, a scheme that assigns a set of outcomes to "heads" and the complement to "tails" is just as good as the scheme making the opposite assignment. In terms of the choices of $a_i$ this amounts to (1) replacing $a_i$ with $binomni - a_i$ or (2) replacing $a_i$ with $a_n-i$.

We can also rule out any case where swapping the roles of $p$ and $1-p$ results in larger coefficients across the board. For instance, if we have $n = 2$ then clearly we can't have $HT$ having an equal probability to $HH, TH, TT$ since $p(HT) = p(TH)$.

Let's do the first few values of $n$. For $n = 0$ there are of course no solutions and for $n = 1$ there is only the solution $p = 1/2$. For $n = 2$ there are the solutions $p = sqrt2/2$ as well as $p = 1/2$ again.

Okay, now let's try $n = 3$. If I've enumerated right, the possible equivalence classes are:

• (1, 0, 0, 0); (0, 3, 3, 1); (0, 0, 0, 1); (1, 3, 3, 0)


• (0, 2, 0, 0); (1, 1, 3, 1); (0, 0, 2, 0); (1, 3, 1, 1)


• (1, 2, 0, 0); (0, 1, 3, 1); (0, 0, 1, 2); (1, 3, 1, 0)


• (0, 3, 0, 0); (1, 0, 3, 1); (0, 0, 3, 0); (1, 3, 0, 1)


• (1, 3, 0, 0); (0, 0, 3, 1)


• (1, 0, 1, 0); (0, 3, 2, 1); (0, 1, 0, 1); (1, 2, 3, 0)


• (1, 1, 1, 0); (0, 2, 2, 1); (0, 1, 1, 1); (1, 2, 2, 0)


• (0, 2, 1, 0); (1, 1, 2, 1); (0, 1, 2, 0); (1, 2, 1, 1)


• (1, 2, 1, 0); (0, 1, 2, 1);


• (0, 3, 1, 0); (1, 0, 2, 0); (0, 1, 3, 0); (0, 2, 0, 1)


• (1, 0, 2, 0); (0, 3, 1, 1); (0, 2, 0, 1); (1, 1, 3, 0)


• (1, 1, 2, 0); (0, 2, 1, 1)


• (0, 2, 2, 0); (1, 1, 1, 1)


• (0, 3, 2, 0); (1, 0, 1, 1); (0, 2, 3, 0); (1, 1, 0, 1)


• (1, 0, 3, 0); (0, 3, 0, 1)

Let's try one representative from each class.

• 
  $p^3 = 1/2$. This gives us the solution $p = sqrt[3]4/2$
  


• 
  $2p^2(1-p) = 1/2$. The real root here is negative.


• 
  $p^3 + 2p^2(1-p) = 1/2$. This polynomial has three real roots, one of which is a valid probability.


• 
  $3p^2(1-p) = 1/2$. The real root here is negative.


• 
  $p^3 + 3p^2(1-p) = 1/2$. This has the solution $p = 1/2$, and corresponds to taking whichever of heads or tails we got more of.


• 
  $p^3 + p(1-p)^2 = 1/2$. The real solution is a valid probability.

Okay, I lied, I'm not going to try every single case. But we did come up with a couple of new solutions we didn't previously know about.

There are some things we could systematically do here, like eliminating the cases that correspond to ignoring some number of the coin flips or employing Descartes's rule of signs to skip some cases where there are no real roots. I don't know if this would reach a bijective solution or not, but it's worth a try.