Can you simulate any probability with biased coin throws?

Question

What you're given:

$p \in (0,1)$, but you don't know the value of $p$.

You have an algorithm $\mathcal{A}_p$ that returns $1$ with a probability of $p$ and $0$ with a probability of $(1-p)$. You can think of this as a biased coin throw. You may throw the coin as often as you want and the bias doesn't change.

What I've concluded:

You can get an algorithm $\mathcal{A}_\frac{1}{2}$ that returns 1 with a probability of $0.5$ and $0$ with a probability of $0.5$:

A_0.5() {
    int x = 0, y = 0;
    while (x == y) {
        x = A_p();
        y = A_p();
    }
    return x;
}

It is obvious that you can get any algorithm $\mathcal{A}_\frac{1}{2^n}$ by executing $\mathcal{A}_\frac{1}{2}$ $n$ times in a row.

The corner cases $\mathcal{A}_1$ and $\mathcal{A}_0$ are easy:

A_1() {
    return 1;
}

A_0() {
    return 0;
}

The question:

Can you get any algorithm $\mathcal{A}_q$ with $q \in \mathbb{Q} \cap [0,1]$?

Can you get any algorithm $\mathcal{A}_r$ with $r \in \mathbb{R} \cap [0,1]$?

Answer 1

You have shown how to simulate a fair coin. We now deal with the general case. There is no problem if $r=0$ and $r=1$. Let $r$ be a real number strictly between $0$ and $1$. Then $r$ has a binary expansion. To be precise, sometimes it has two. If relevant, use the expansion that is ultimately all $0$'s rather than the one which is ultimately all $1$'s.

Let random variable $X$ be uniformly distributed on $(0,1)$, and let $E$ be the event $X\l r$. Then $\Pr(E)=r$.

Record the results of "tossing the fair coin," $0$ for head and $1$ for tail. As long as the sequence coin tosses agree with the binary expansion of $r$, keep tossing. Terminate the first time that the bit $a$ obtained from the "coin" differs from the corresponding bit $b$ of $r$.

If $a=0$ and $b=1$, the algorithm declare that $E$ has happened, since now for sure the number our sequence of tosses generates is $\lt r$. If $a=1$, and $b=0$, declare that the event $\lnot E$ has happened.

Note that one can only say that the algorithm terminates with probability $1$. This was already the case for the simulating the fair coin part.

Answer 2

It cannot be possible for any $r\in \mathbb R$ since these are more than countable, while the algorithms are countable.

It is simple to adapt your algorithm for every rational of the form $1/n$ and hence should be possible for every rational $m/n$.

code for $1/3$

A_iii() {
  while (1) {
     x = A_p();
     y = A_p();
     z = A_p();
     if (x==1 && y==0 && z==0) return 1;
     if (x==0 && y==1 && z==0) return 0;
     if (x==0 && y==0 && z==1) return 0;
  }   
}

Answer 3

Referring to your question on Emanuele Paolini's answer: an algorithm for $A_n$ in Python might look like

 def A(n):
    while(True):
        x = [Ap() for i in range(n)]
        if sum(x)==1: return x[0]

The idea is the following sum(x) is one if exactly one x[i] is non-zero. Each of these cases has the same probability namely $p_i=p (1-p)^n$, so the probability of the algorithm to return 1 is the conditional probability $p(x_0=1|\sum_i x_i=1)=p (1-p)^n / (n p (1-p)^n)=1/n$.

(Since I'm only building this up on answers already given here, I marked this as community wiki).

Answer 4

Here is an algorithm that takes $r \in [0,1]\cap\mathbb{R}$ as a parameter and returns $1$ with probability $r$ and $0$ with probability $1-r$.

A(real r)
{
  while (true)
  {
    int b = random_bit();
    if (r>=0.5)
    { 
      if (b==0) return 1;
      else r=r*2.0-1.0;
    }
    else
    {
      if (b==1) return 0;
      else r=r*2.0;
    }
  }
}