# Improving success probability for one sided error algorithms

Suppose I have a probabilistic Turing machine for a language such that $$x \in A \implies \Pr(M \text{ accepts } x) \ge \frac{1}{n}$$ $$x \notin A \implies \Pr(M \text{ accepts } x) = 0$$
I want to show that the above language is in $\mathsf{RP}$. In particular, I need a probabilistic Turing machine $N$ such that $$x \in A \implies \Pr(N \text{ accepts } x) \ge 1 - \frac{1}{2^n}$$ where $n = |x|$.

I tried to construct $N$ such that it runs $M$ multiple times (say $t$ times) and accepts if at least one of the runs accepts. This preserves the one-sided error but I'm not sure if it runs in polynomial time.

I showed that $x \in A \implies \Pr(N \text{ accepts } x) \ge 1 - (1 - \frac{1}{n})^t$.

Now, to show that it is in $\mathsf{RP}$,

$$1 - (1 - \frac{1}{n})^t \ge 1 - \frac{1}{2^n}$$ $$(1-\frac{1}{n})^t \le \frac{1}{2^n}$$

I am basically stuck at this point and unable to show an upper bound for $t$. I know that it suffices to show that $t$ is polynomial in $n$ but I am not able to prove it. How do I show that $N$ is indeed a polynomial time machine? Or maybe this is not the right approach?

• Solve for t. ​ ​ – user12859 Feb 11 '17 at 16:09
• @RickyDemer I tried doing that by taking log on both sides, but that is giving me a lower bound for t. – skankhunt42 Feb 11 '17 at 16:11
• You don't need an upper bound on what t suffice, you just need an upper bound on what t are necessary. ​ ​ – user12859 Feb 11 '17 at 16:15
• @RickyDemer Could you please expand on that? I don't understand. – skankhunt42 Feb 11 '17 at 16:19
• You could also use a quadratic with a sufficiently-large coefficient. ​ ​ – user12859 Feb 11 '17 at 16:27