On a Conjecture of Feige for Discrete Log-Concave Distributions

2022/08/26 by Abdulmajeed Alqasem, Alqasem, Abdulmajeed, Heshan Aravinda +5 · 5 citations
Mathematics · #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.2208.12702

Abstract

A remarkable conjecture of Feige (2006) asserts that for any collection of n independent non-negative random variables X₁, X₂, …, X_n, each with expectation at most 1, ℙ(X lt; 𝔼[X] + 1) ≥ (1)/(e), where X = ∑_i=1ⁿ 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.

Cited by

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

Related

• On Feige's conjecture
• An equivalent conjecture to Feige's Conjecture
• A note on the Littlewood-Offord problem for discrete log-concave distributions
• Notes on Feige's gumball machines problem
• Approximate Discrete Entropy Monotonicity for Log-Concave Sums