Bounding probability of small deviation: A fourth moment approach

Bounding probability of small deviation: A fourth moment approach

0.00 Avg rating0 Votes
Article ID: iaor20102617
Volume: 35
Issue: 1
Start Page Number: 208
End Page Number: 232
Publication Date: Feb 2010
Journal: Mathematics of Operations Research
Authors: , ,
Keywords: random numbers
Abstract:

In this paper we study the problem of upper bounding the probability that a random variable is above its expected value by a small amount (relative to the expected value), by means of the second and the fourth (central) moments of the random variable. In this particular context, many classical inequalities yield only trivial bounds. We obtain tight upper bounds by studying the primal-dual moments-generating conic optimization problems. As an application, we demonstrate that given the new probability bounds, a substantial sharpening and simplification of a recent result and its analysis by Feige (2006) can be obtained; also, these bounds lead to new properties of the distribution of the cut values for the max-cut problem. We expect the new probability bounds to be useful in many other applications.

Reviews

Required fields are marked *. Your email address will not be published.