2
$\begingroup$

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?

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

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'$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – bellpeace Nov 25 '13 at 15:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Louis Nov 25 '13 at 18:30
  • $\begingroup$ 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. $\endgroup$ – bellpeace Nov 25 '13 at 18:34
  • $\begingroup$ Great, much clearer! I guess when $A$ is not a decision problem, yet, for example yes/no/maybe, things get more complicated. $\endgroup$ – bellpeace Nov 25 '13 at 20:03
  • $\begingroup$ 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! $\endgroup$ – Louis Nov 25 '13 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.