3

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]$?

Martin Thoma
  • 9,821
  • So, do you have an algorithm $\mathcal{A}_p$ only for $p=\frac{1}{2}$? – Stefan Hansen Feb 20 '13 at 11:33
  • No, I have an algorithm $\mathbb{A}p$ for $p \in (0,1)$, but I don't know $p$. (I've updated that.) But you can get $\mathcal{A}{0.5}$ as described with any $p \in (0,1)$ – Martin Thoma Feb 20 '13 at 11:36
  • You can generalize your algorithm to $1/n$ by having $n$ variables $x_1$, $x_2$, ..., $x_n$. Return 1 if $x_1$ =1 and all other $x_i$ = 0. Return 0 if , $x_1$ = 0, one $x_i$ = 1 and all other $x_j$ = 0, otherwise loop. – Djaian Feb 20 '13 at 12:01
  • A starting point is Fast Simulation of New Coins From Old by S. Nacu and Y. Peres, Annals of Applied Probability 15, no. 1A (2005). – Did Feb 20 '13 at 12:41
  • As discussed below, the answer in the case of real numbers is intimately related to the algorithm's underlying computational model. – cubic lettuce Feb 20 '13 at 13:05

4 Answers4

3

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.

André Nicolas
  • 507,029
  • Interesting... this is in contradiction to what I say below. Maybe the point is that $r$ must be a computable number to have an algorithm which gives the digits of the binary expansion? – Emanuele Paolini Feb 20 '13 at 12:06
  • 1
    I had an early typo, a $0$ where there should have been a $1$. The number $r$ does not need to be computable. To see that the informal "there are only countably many algorithms" does not work, note that the simulation of the fair coin can produce, in principle, any of the uncountably many sequences of $0$'s and $1$'s. – André Nicolas Feb 20 '13 at 12:12
  • I don't agree. I think that the number must be computable, but that this hypothesys is so obvious that should not even be mentioned... Or maybe that since $r$ is an input, one must assume that there is a black box which gives the digits of $r$. – Emanuele Paolini Feb 20 '13 at 12:17
  • This algorithm needs the $k$'th bit of $r$ to decide whether to proceed or not, thus, $r$ must be accessible up to arbitrary precision. Since an algorithm's description can only use finite space, we are limited to such $r$'s that can be approximated up to arbitrary precision by a finite space algorithm, i.e., $r$ must be computable. There are just countable many computable numbers, while 'most' real numbers are not. Things would be different using a Turing machine with an oracle that can be asked for the $k$'th bit of $r$ without having to compute it itself. Really an interesting difference! – cubic lettuce Feb 20 '13 at 12:23
  • Certainly $r$ must be "given." – André Nicolas Feb 20 '13 at 12:27
  • But you cannot input a non-computable $r$ with infinite precision by using just finite space. Thus, the computational model that you assume is more powerful than a Turing machine (and thus, more powerful than any computer from real world), since the latter requires its input to be finite. – cubic lettuce Feb 20 '13 at 12:34
  • For any fixed $r$, we have a more or less ordinary (two tape) Turing machine, except that $r$ is printed on one of the tapes. Certainly one must have access to $r$. If it is to be a classical TM, then the input has to be an integer that encodes $r$, and we are limited to computable $r$. – André Nicolas Feb 20 '13 at 12:48
0

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;
  }   
}
Emanuele Paolini
  • 21,447
  • How would you adapt the algorithm for any 1/n? Could you please explain it for 1/3? – Martin Thoma Feb 20 '13 at 11:57
  • 1
    So there's a differnce between giving an individual algorithm for each $r$ and giving a single algorithm that works, given $r$. – Hagen von Eitzen Feb 20 '13 at 12:31
  • I've only asked if such an algorithm $\mathcal{A}_r$ exists for any $r \in \mathbb{R} \cap [0,1]$, not for a single algorithm that works for any $r$. I can see the pattern here, so it's fine. But I also like André Nicolas solution. – Martin Thoma Feb 20 '13 at 12:36
0

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

Elmar Zander
  • 1,625
0

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;
    }
  }
}
mjqxxxx
  • 41,358