  The Markov, Chebyshev, and Chernoff inequalities are some of the most widely
used methods for bounding the tail probabilities of random variables. In all
three cases, the bounds are tight in the sense that there exists easy examples
where the inequalities become equality. Here we will show that through a simple
smoothing using auxiliary randomness, that each of the three bounds can be cut
in half. In many common cases, the halving can be achieved without the need for
the auxiliary randomness.
