Generalized Chebyshev Bounds via Semidefinite Programming

SIAM Review, 49(1):52-64, March 2007.

• SIAM Review paper: prob_bnds.pdf

• rocond_cheb.pdf

• talk given at MSRI: msri.pdf

A sharp lower bound on the probability of a set defined by quadratic inequalities, given the first two moments of the distribution, can be efficiently computed using convex optimization. This result generalizes Chebyshev's inequality for univariate random variables. Two semidefinite programming formulations are presented, with a constructive proof based on convex optimization duality and elementary linear algebra.