7.4 Chebyshev and Chernoff bounds

In this section we consider two types of classical bounds on the probability of a set, and show that generalizations of each can be cast as convex optimization problems. The original classical bounds correspond to simple convex optimization problems with analytical solutions; the convex optimization formulation of the general cases allow us to compute better bounds, or bounds for more complex situations.

7.4.1 Chebyshev bounds

Chebyshev bounds give an upper bound on the probability of a set based on known expected values of certain functions (e.g., mean and variance). The simplest example is Markov’s inequality: If X is a random variable on R_{+} with E X = μ, then we have (X ≥ 1) ≤ μ, no matter what the distribution ...

Start Free Trial

No credit card required