A constructive proof of a concentration bound for real-valued random variables

DOI10.1016/J.IPL.2020.105942MaRDI QIDQ2308463zbMATH OpenOpenAlexFDO

Authors Wolfgang Mulzer, Natalia Shenkman

Publication date 3 April 2020

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.01172

zbMATH Keywords

concentration boundgeneralized Chernoff-Hoeffding boundrandomized algorithms

Mathematics Subject Classification ID

Computational methods for problems pertaining to probability theory (60-08) Inequalities; stochastic orderings (60E15) Randomized algorithms (68W20)

Abstract: Almost 10 years ago, Impagliazzo and Kabanets (2010) gave a new combinatorial proof of Chernoff's bound for sums of bounded independent random variables. Unlike previous methods, their proof is constructive. This means that it provides an efficient randomized algorithm for the following task: given a set of Boolean random variables whose sum is not concentrated around its expectation, find a subset of statistically dependent variables. However, the algorithm of Impagliazzo and Kabanets (2010) is given only for the Boolean case. On the other hand, the general proof technique works also for real-valued random variables, even though for this case, Impagliazzo and Kabanets (2010) obtain a concentration bound that is slightly suboptimal. Herein, we revisit both these issues and show that it is relatively easy to extend the Impagliazzo-Kabanets algorithm to real-valued random variables and to improve the corresponding concentration bound by a constant factor.

Recommendations

• Constructive proofs of concentration bounds
• Bounds for the concentration functions of random sums under relaxed moment conditions
• A refined randomized concentration inequality
• Concentration inequalities and limit theorems for randomized sums
• On Concentration of Distributions of Sums of Independent Random Vectors on Bounded Sets
• The concentration inequalities of functions of independent random variables
• Concentration bounds for stochastic approximations
• On concentration functions of random variables
• Concentration and Gaussian Approximation for Randomized Sums

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Complex graphs and networks
• Constructive proofs of concentration bounds
• Hoeffding's inequality for sums of dependent random variables
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 7075945 (Why is no real title available?)
• Probability Inequalities for Sums of Bounded Random Variables
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(1)

• Constructive proofs of concentration bounds

This page was built for publication: A constructive proof of a concentration bound for real-valued random variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2308463)