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 ...