3
$\begingroup$

I'm a bit confused about the definition of BPP. The way BPP is defined in typical text books (Arora/Barak for example) is that if M(x) is a Probabilistic Turing Machine (PTM) that recognizes a language $L(x)$, then $Pr[M(x)=L(x)]> 2/3$. My question is, what is the probability taken over? Arora/Barak remark (7.2) that the probability is taken over internal coin tosses of $M(x)$, i.e., fix a value of $x$, and run all possible $2^{T(|x|)}$ experiments of internal coin tosses, and compute the majority of accept state. But if this is true, then Amplification theorem cannot hold because by definition if the probability is computed by executing all $2^{T(|x|)}$ possible coin-flips, then no matter how many times I run the algorithm, the probability is not going to change. (For example, if I have a bag with 2 red balls and 1 blue ball, then no matter how many times I pick a ball from the bag (and return it), the probability of picking a red ball is going to remain 2/3.)

Basically, a PTM is a random process in two variables: The input string $x \in \{0,1\}^*$ and random coin tosses $ r \in \{0,1\}^{T(|x|)}$. For the amplification theorem to hold, I think one needs to fix a value of $r$ and run the machine on all values of $x$, and compute $Pr[M(x) = L(x)]$. Then for a fixed $x$, running $M(x)$ multiple times will have amplification effect, but if the probability is computed over internal coin tosses, then the Amplification theorem cannot hold.

What am I misunderstanding here?

$\endgroup$

migrated from cstheory.stackexchange.com Apr 7 '13 at 23:37

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 3
    $\begingroup$ frankly your second paragraph doesn't make any sense to me. what you are missing is that for amplification you run $M(x)$ many times and and take the majority vote of all the runs - this changes the probability of success. with your analogy: pick a ball a 1000 times, what is the probability that more than half the balls are blue? $\endgroup$ – Sasho Nikolov Apr 7 '13 at 5:19
  • 2
    $\begingroup$ Each time you run the algorithm, you must use fresh random bits. $\endgroup$ – MCH Apr 7 '13 at 14:08
  • $\begingroup$ Concrete understanding of difference between PP and BPP definitions is a related question. $\endgroup$ – adrianN Apr 9 '13 at 11:59
6
$\begingroup$

Repeating what MCH said, every time you run the algorithm, you use fresh random bits.

As an example, here is a BPP algorithm that computes the number $1$:

Toss a biased coin (heads w.p. 2/3, tails w.p. 1/3). If heads, output 1, else output 0.

The algorithm "succeeds" with probability $2/3$. The amplification procedure amounts to tossing $n$ biased coins, outputting $1$ if the majority of them were heads, and $0$ otherwise. Since we expect roughly $(2/3)n > n/2$ of the coins to be heads, it is very likely that the amplified algorithm is successful (outputs $1$).

In other words, when you run your algorithm $n$ times, each time you run it, you re-toss all the coins. So the amplified algorithm tosses $n$ times as many coins, and the probability is taken over all these coin tosses.

$\endgroup$
  • $\begingroup$ that is a nice example. $\endgroup$ – Kaveh Apr 8 '13 at 5:36
  • 3
    $\begingroup$ Now I really want to write a library function One() that implements that algorithm. $\endgroup$ – Luke Mathieson Apr 8 '13 at 10:37

Your Answer

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