On a Conjecture of Feige for Discrete Log-Concave Distributions

Abstract

A remarkable conjecture of Feige (2006) asserts that for any collection of $n$ independent non-negative random variables $X_1,X_2,\dots ,X_n$, each with expectation at most $1$, $$\mathbb{P}(X<\mathbb{E}[X]+1)\ge \frac{1}{e},$$ where $X={\sum }_{i=1}^n{X}_i$. In this paper, we investigate this conjecture for the class of discrete log-concave probability distributions and we prove a strengthened version. More specifically, we show that the conjectured bound $1/e$ holds when $X_i$'s are independent discrete log-concave with arbitrary expectation.

arXiv comment11 pages