Small deviations of sums of independent random variables

DOI10.1016/J.JCTA.2019.105119zbMATH Open1427.60037arXiv1804.01529OpenAlexW2963941954MaRDI QIDQ2010615FDOQ2010615

Authors: Brian Garnett 

Publication date: 27 November 2019

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: A well-known discovery of Feige's is the following: Let $X_1,ldots,X_n$ be nonnegative independent random variables, with $mathbbE[X_i]leq1;foralli$, and let $X=su{m}_{i=1}^n{X}_i$. Then for any $n$, [Pr[X < mathbb{E}[X] + 1] geq alpha > 0,] for some $alphageq1/13$. This bound was later improved to $1/8$ by He, Zhang, and Zhang. By a finer consideration of the first four moments, we further improve the bound to approximately $.14$. The conjectured true bound is $1/esimeq.368$, so there is still (possibly) quite a gap left to fill.

Full work available at URL: https://arxiv.org/abs/1804.01529

Recommendations

• scientific article; zbMATH DE number 1149759
• Small deviation probabilities for sums of independent positive random variables
• Small deviation probabilities for sums of independent positive random variables
• Small deviations of modified sums of independent random variables
• Small deviation probabilities for sums of independent positive random variables with a distribution that slowly varies at zero
• scientific article; zbMATH DE number 4078378
• scientific article; zbMATH DE number 850372
• Small deviation probabilities for sums of independent positive random variables whose density has a power decay at zero
• Small deviation probabilities for maximum of partial sums

zbMATH Keywords

linear programmingsmall deviations\(k\)-wise independencesum of random variablesfourth moment approach

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Linear programming (90C05) Inequalities; stochastic orderings (60E15)

Cites Work

• Optimal Inequalities in Probability Theory: A Convex Optimization Approach
• Closed Form Two-Sided Bounds for Probabilities that At Least r and Exactly r Out of n Events Occur
• The extrema of probability determined by generalized moments. I: Bounded random variables
• Bounding probability of small deviation: a fourth moment approach
• Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• The maximal probability that \(k\)-wise independent bits are all 1

Cited In (10)

• Choosing joint distributions so that the variance of the sum is small
• Title not available (Why is that?)
• Tight Probability Bounds with Pairwise Independence
• On a Conjecture of Feige for Discrete Log-Concave Distributions
• Small deviation probabilities for sums of independent positive random variables with a distribution that slowly varies at zero
• Bounding probability of small deviation: a fourth moment approach
• On small deviations conjecture
• On maximal tail probability of sums of nonnegative, independent and identically distributed random variables
• Small deviation probabilities of a sum of independent positive random variables, the common distribution of which decreases at zero not faster than exponential function
• Marchenko-Pastur law for a random tensor model

This page was built for publication: Small deviations of sums of independent random variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010615)