Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is probably not a very smart question, more of a confusion I guess.

For example, if $X \sim Geometric(1-p)$, i.e. $p$ being the probability of failure, the exact tail bound is $$ \mathbf{P}(X>s) = \sum_{k=s+1}^{\infty}p^k(1-p) = p^{s+1} $$ At the same time, using Markov inequality: $$ \mathbf{P}(X>s) < \frac{EX}{s} = \frac{p}{(1-p)s} $$

which is of course worse than the one in the first expression.

So my confusion is, can Markov or Chernoff bounds be sharper than that the tail bound (first expression)? If not, then what is the main point of using them if the tail expression can be found analytically?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

A bound can't be sharper than the exact value. The point of using a bound is that you can use it in cases where it is impossible or inconvenient to obtain the exact value.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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