Bounding this probability in this Monte Carlo algorithm

Question

Let $P$ be a YES-NO decision problem. Let $A$ be an algorithm for deciding on it such that it is correct with probability $4/5$, in both cases (YES an NO). Design an algorithm that is correct with probability at least $p$, in both cases (YES an NO).

This is my solution but I'm stuck at bounding the probability. Let be $B$ be an algorithm that runs $A$, $n$ number of times. Let $X_i$ with $1\leq i \leq n$ such that $X_i = 1$ if $A$ outputs $YES$ and, $X_i = 0$ if $A$ outputs $NO$. Without loss of generality assume that $P=YES$ then $\Pr[\text{B is correct}] = \Pr[\text{B = YES}] = \Pr[X \geq \frac{n}{2}]$. I know that in this case $E[X] = \frac{4}{5}n$, but don't know what else to do.

Answer 1

Assuming I understand this correctly...the true state is either YES or NO. You have an algorithm A that can detect the truth with probability 4/5 and fails with probability 1/5. You devise an algorithm B that just runs A $n$ times and decides that the truth is YES if B has a sufficient number of YES outcomes out of those $n$ trials. I think that works. You want to find the first values of $n$ and $x$ (with $n/2\le x\le n$) that satisfy:

$$\sum_{y=x}^n {n\choose y} (4/5)^y (1/5)^{n-y} \ge p,$$ and $$\sum_{y=0}^{x-1} {n\choose y} (1/5)^y (4/5)^{n-y} \ge p.$$

In that way, your decision rule for B - return a YES if there are at least $x$ yes outcomes in the $n$ trials - will work with probability at least $p$. If $n$ is odd then you really only need the first inequality.