I am attempting to work through an example of how to select an error bound, and then determine the number of simulations necessary by the amplification lemma to obtain the desired error bound. I have probabilistic Turing machine $M$ with an error probability of $.5$. I'd like an error bound of $.25$, so I will bound the error probability by $2^{-t}$, where $t=2$. According to my textbook, I need to choose a $k$ such that $k \ge t/f$, where $f=-log_2(4e(1-e))$, where $e$ is the error probability. As $M$ has an error probability of $.5$, $e=.5$. Substituting into the equation gives: $-log_2 (2(.5))=-log_2(1)=0$. The problem is when I go to select a $k$ such that $k \ge t/f$, I get $0$ as a divisor. Are there other restrictions on the calculation? Or, am I just doing something wrong?
1 Answer
If the Turing machine has an error probability of $1/2$, the Turing machine is useless and you cannot amplify to reduce the error bound.
Consider: if you just ignore the input and flip a coin and use that to decide whether to accept or reject, you get an error probability of $1/2$ -- yet that is an obviously useless procedure. A Turing machine with an error probability of $1/2$ is no better than that.
Here's another way to see why it's hopeless. One standard method of amplification is to run the Turing machine multiple times and take a majority vote. Suppose we run the Turing machine 3 times, and take a majority vote. What is the probability that the outcome of the majority vote is correct? It's not hard to see that this probability is $1/2$ -- no better than running the machine once. (Why? Each time you run the Turing machine, it is either correct or incorrect. Since you run it 8 times, there are 8 cases: CCC, CCI, CIC, CII, ICC, ICI, IIC, III, where C = correct and I = incorrect. If the Turing machine's error probability is $1/2$, all 8 of those cases are equally likely. The majority vote after 3 runs will be correct in the cases CCC, CCI, CIC, and ICC; thus, the majority vote is correct with probability $4/8 = 1/2$.) The same thing happens no matter how many times you run the Turing machine.
To get amplification, you need the error probability to be strictly less than $1/2$.
