TY - JOUR

T1 - Bounding probability of small deviation

T2 - A fourth moment approach

AU - He, Simai

AU - Zhang, Jiawei

AU - Zhang, Shuzhong

PY - 2010/2/1

Y1 - 2010/2/1

N2 - 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 (see Feige, U. 2006. On sums of independent random variables with unbounded variances, and estimating the average degree in a graph. SIAM J. Comput. 35 964-984) 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.

AB - 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 (see Feige, U. 2006. On sums of independent random variables with unbounded variances, and estimating the average degree in a graph. SIAM J. Comput. 35 964-984) 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.

KW - Duality

KW - Moments problem

KW - Probability of small deviation

KW - Sum of random variables

UR - http://www.scopus.com/inward/record.url?scp=77949389600&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77949389600&partnerID=8YFLogxK

U2 - 10.1287/moor.1090.0438

DO - 10.1287/moor.1090.0438

M3 - Article

AN - SCOPUS:77949389600

VL - 35

SP - 208

EP - 232

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 1

ER -