1
$\begingroup$

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?

1 Answers 1

4

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.