Hoeffding's inequality for sums of weakly dependent random variables

By Christos Pelekis, J. Ramon. 2015

9 citations recorded by the source corpus.

We provide a systematic approach to deal with the following problem. Let $X_1,\ldots,X_n$ 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, $X_1,\ldots,X_n$, that satisfy the following condition: there exist constants $\gamma \in (0,1)$ and $\delta\in (0,1]$ such that for every subset $A\subseteq \{1,\ldots,n\}$ we have $\mathbb{E}\left[\prod_{i\in A} X_i \prod_{i\notin A}(1-X_i) \right]\leq \gamma^{|A|} \delta^{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.

Subfields: Computer Networks and Communications, Discrete Mathematics and Combinatorics, Geometry and Topology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

  1. Rong Ge
  2. Sanjeev Arora
  3. Yi Zhang
  4. Behnam Neyshabur

In Discrete Mathematics and Combinatorics

  1. Rong Ge
  2. Sanjeev Arora
  3. Yi Zhang
  4. Behnam Neyshabur

In Geometry and Topology

  1. Rong Ge
  2. Sanjeev Arora
  3. Yi Zhang
  4. Behnam Neyshabur

Citations in the corpus