On maximal tail probability of sums of nonnegative, independent and identically distributed random variables

2016/02/10 by Tomasz Łuczak, Łuczak, Tomasz, Katarzyna Mieczkowska +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.1602.03547

arxiv created 2016/02/10 · openalex publication_date 2016/02/10 · arxiv updated 2016/02/12 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28

Abstract

We consider the problem of finding the optimal upper bound for the tail probability of a sum of k nonnegative, independent and identically distributed random variables with given mean x. For k=1 the answer is given by Markov's inequality and for k=2 the solution was found by Hoeffding and Shrikhande in 1955. We solve the problem for k=3 as well as for general k and x≤1/(2k-1) by showing that it follows from the fractional version of an extremal graph theory problem of Erdős on matchings in hypergraphs.

Related

• Extremal distributions for tail probabilities of sums of iid random variables on [0,1]
• A general Hsu-Robbins-Erdos type estimate of tail probabilities of sums of independent identically distributed random variables
• A general Hsu-Robbins-Erdos type estimate of tail probabilities of sums of independent identically distributed random variables
• A note on sums of independent random variables
• On Asymptotically Tight Tail Bounds for Sums of Geometric and Exponential Random Variables