Small deviations of sums of independent random variables

DOI10.1016/J.JCTA.2019.105119MaRDI QIDQ2010615zbMATH OpenOpenAlexFDO

Authors Brian Garnett

Publication date 27 November 2019

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

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

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)

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.

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

Cites work

• Bounding probability of small deviation: a fourth moment approach
• Closed Form Two-Sided Bounds for Probabilities that At Least r and Exactly r Out of n Events Occur
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Optimal Inequalities in Probability Theory: A Convex Optimization Approach
• Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization
• The extrema of probability determined by generalized moments. I: Bounded random variables
• 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
• scientific article; zbMATH DE number 1949153 (Why is no real title available?)
• 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
• On small deviations conjecture
• Bounding probability of small deviation: a fourth moment approach
• 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)