[Solved]: Chernoff bounds and Monte Carlo algorithms

Let’s suppose that we have a polynomial time randomized algorithm $A$ for a decision problem $Pi$ with the property that $$ mathrm{Pr}[A text{ is right}] > 1/2 $$ for all inputs. (In particular, independent of the input length $n$.) We can use Chernoff bounds to show something stronger, namely that for any fixed $c$, there is a polynomial time, randomized algorithm for $Pi$ that is correct with probability at least $1-n^{-c}$. The algorithm is very simple: On an input of length $n$, we run $A$ a polynomial number of times $N$ (to be determined below) and then report the majority answer. Call this algorithm $A’$. What we need is a bound on $$ mathrm{Pr}[A’ text{ is wrong}] $$ in terms of the number of repetitions $N$. The hypothesis about $A$ implies that there is an $epsilon > 0$ such that $$ mathrm{Pr}[A text{ is right}] ge 1/2 + epsilon $$ Since the $N$ runs of $A$ are independent, for any $kin [N]$ we have $$ mathrm{Pr}[k text{ of } N text{ runs of } A text{ are right}]ge Pr[X = k] $$ where $X$ is a binomial random variable with parameters $N$ and $1/2+epsilon$. Since the algorithm $A’$ is wrong exactly when at most $N/2$ of the runs of $A$ are right, we obtain an upper bound on the failure probability by a “tail estimate” bounding $$ mathrm{Pr}[X le N/2] $$ This is a prototypical time to use a Chernoff bound, since a binomial r.v. is the sum of $N$ independent random variables. One instance of the Chernoff bound says that if $Y$ is the sum of $N$ independent r.v.’s with support in $[0,1]$ and $t > 0$, then $$ mathrm{Pr}[Y < E[Y] – t] le e^{-2t^2/N} $$ Thus, since $E[X] = N/2 + Nepsilon$, we take $t = Nepsilon$ to obtain $$ mathrm{Pr}[A’ text{ is wrong}]le e^{-2epsilon^2 N} $$ So we can take $N = (1/2)epsilon^{-2}clog n$, and we get the claimed error probability for $A’$.