2015/07/24 by Christos Pelekis, Jan Ramon, Pelekis, Christos +1 · 1 citation
Computer Science · Mathematics · #60E15 #60G50 #Cooperative Communication and Network Coding #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #math.PR #msc:60E15 #msc:60G50
paper · pdf · doi:10.48550/arxiv.1507.06871
38 pages
arxiv created 2015/07/24 · openalex publication_date 2015/07/24 · arxiv updated 2015/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We provide a systematic approach to deal with the following problem. Let X1,…,Xn be, possibly dependent, [0,1]-valued random variables. What is a sharp upper bound on the probability that their sum is significantly larger than their mean? In the case of independent random variables, a fundamental tool for bounding such probabilities is devised by Wassily Hoeffding. In this paper we consider analogues of Hoeffding's result for sums of dependent random variables for which we have certain information on their dependency structure. We prove a result that yields concentration inequalities for several notions of weak dependence between random variables. Additionally, we obtain a new concentration inequality for sums of, possibly dependent, [0,1]-valued random variables, X1,…,Xn, that satisfy the following condition: there exist constants γ∈ (0,1) and δ∈ (0,1] such that for every subset A⊆ \1,…,n\ we have 𝔼[∏i∈ A Xi ∏i∉ A(1-Xi) ]≤ γ|A| δn-|A|, where |A| denotes the cardinality of A. Our approach applies to several sums of weakly dependent random variables such as sums of martingale difference sequences, sums of k-wise independent random variables and U-statistics. Finally, we discuss some applications to the theory of random graphs.