3
$\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$
2
  • 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
    Commented Nov 25, 2013 at 9:41
  • $\begingroup$ Yeah, how to apply. Why it can be applied to this problem? $\endgroup$ Commented Nov 25, 2013 at 14:12

1 Answer 1

8
$\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$
5
  • $\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$ Commented Nov 25, 2013 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
    Commented Nov 25, 2013 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$ Commented Nov 25, 2013 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$ Commented Nov 25, 2013 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
    Commented Nov 25, 2013 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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