Small Deviations of Sums of Independent Random Variables

2018/04/04 by Garnett, Brian · 4 citations
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1804.01529

Abstract

A well-known discovery of Feige's is the following: Let X₁, …, X_n be nonnegative independent random variables, with 𝔼[X_i] ≤ 1 ∀ i, and let X = ∑_i=1ⁿ X_i. Then for any n, Pr[X lt; 𝔼[X] + 1] ≥ αgt; 0, for some α≥ 1/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/e ≃ .368, so there is still (possibly) quite a gap left to fill.

Cited by

• Sharp small-deviation inequalities for sums of independent nonnegative random variables
• On Feige's conjecture
• A short proof of Feige's conjecture for identically distributed random variables
• An equivalent conjecture to Feige's Conjecture

Related

• Sharp small-deviation inequalities for sums of independent nonnegative random variables
• On Feige's conjecture
• Bounding probability of small deviation on sum of independent random variables: Combination of moment approach and Berry-Esseen theorem
• An equivalent conjecture to Feige's Conjecture
• On some conjectures of Samuels and Feige