Optimal inequalities in probability theory: a convex optimization approach

The authors characterize the complexity of deriving tight moment inequalities for P(XÎS), for an arbitrary set S and a multivariate random variable X that has a given collection of moments. For the univariate case, they provide an optimal inequality for P(XÎS), when the first k moments of X are known, as a solution of a semidefinite optimization problem in k + 1 dimensions. For the n-variate case, given only the means of X, they show that they can find tight bounds by solving n convex optimization problems when the set S is convex, and they provide a polynomial time algorithm when S is a union of convex sets. When moments up to second order are given, the work of Marshal and Olkin shows that they can find tight bounds by solving a single convex optimization problems if the set S is convex and W= Rn. They finally show that it is NP-hard to find tight bounds when moments of third or higher order are given, or if moments of second order are given and the domain of X is R+n.

en

application/pdf

http://flora.insead.edu/fichiersti_wp/inseadwp2000/2000-62.pdf

Copyright INSEAD. All rights reserved