Chernoff bounds and Monte Carlo algorithms

One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p > 1/2$. Basically, Chernoff bounds are used to bound the error probability of $A$ using repeated calls to $A$ and majority agreement.

I don't understand how, to be frank. It would be nice if somebody could break it down piece by piece. Moreover, does it matter whether $A$ is a decision algorithm or can return more values? How are Chernoff bounds in general used for Monte Carlo algorithms?

• Can you be more precise about what you don't understand. How to derive Chernoff bounds, or how to apply Chernoff bounds? – A.Schulz Nov 25 '13 at 9:41
• Yeah, how to apply. Why it can be applied to this problem? – bellpeace Nov 25 '13 at 14:12

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 $k\in [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 + N\epsilon$, we take $t = N\epsilon$ to obtain $$\mathrm{Pr}[A' \text{ is wrong}]\le e^{-2\epsilon^2 N}$$ So we can take $N = (1/2)\epsilon^{-2}c\log n$, and we get the claimed error probability for $A'$.

• It would help if you could add the part with Chernoff bounds, i.e., how to use it here. Moreover, does it matter whether $A$ is a decision problem or it can return more values? – bellpeace Nov 25 '13 at 15:59
• Are you unsure about how to use Chernoff bounds at all, or what a Monte Carlo algorithm is? The question is a little fuzzy about what the problem is. – Louis Nov 25 '13 at 18:30
• Yes, I am unsure how to use them. For example, imagine that I want to make sure the error probability is at most $\epsilon$. How would I go about it? Basically, this example would guide me through on how to use and appreciate Chernoff bounds. – bellpeace Nov 25 '13 at 18:34
• Great, much clearer! I guess when $A$ is not a decision problem, yet, for example yes/no/maybe, things get more complicated. – bellpeace Nov 25 '13 at 20:03
• This use of Chernoff bounds is more of an example of a general approach than a specific result. Try to formalize your specific setup and see! – Louis Nov 25 '13 at 23:12