I am studying Chernoff bounds lately but I am not clear how this is better than cumulative distribution function for binomial distribution.

For example, let's say that p = 0.3 and n = 3. I am interested in finding $Pr(X \geq 2)$.

If I do cumulative distribution, this will be P(X = 2) + P(X = 3), and the answer comes out to be 0.21.

But when I apply Chernoff bound for $Pr(X \geq 2)$, I get an upper bound of 0.6. How is Chernoff bound any useful then? Why not just use cumulative distribution always as it seems to give better bounds. What am I missing?

(I used this to find the Chernoff bound)

  • $\begingroup$ Suppose $n=1000$ and you want to find $\Pr(X>650)$ The cumulative distribution gives the exact value, but the Chernoff bound is a lot easier to compute. $\endgroup$ – saulspatz Apr 28 at 2:57
  • $\begingroup$ @saulspatz so, you are saying Chernoff is only useful if value of $n$ is large, otherwise we better do just CDF? $\endgroup$ – pranavk Apr 28 at 2:59
  • $\begingroup$ Yes, if it's easy to compute the exact value, why would you want to approximate it? $\endgroup$ – saulspatz Apr 28 at 11:52

Your Answer

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

Browse other questions tagged or ask your own question.