Is there a version, or modification, of this theorem for weakly dependent random variables? Or perhaps at least one for the special case involving Bernoulli random variables (that are now weakly dependent)? I can't seem to find anything formal on the subject.

I've stated Hoeffding's theorem below for when we have iid random variables.

Theorem (Hoeffding's Inequality). For iid random variables $X_1, \dots, X_n$ satisfying

$$a_i \leq X_i \leq b_i~\text{a.s.}, \\ \gamma_i = b_i - a_i, \\ \gamma_i \leq \Gamma_i,$$

Hoeffding's inequality says

$$\mathbb{P}\left[|S_n - \mathbb{E}[S_n]| > t\right] < 2\exp\left\{-\frac{2t^2}{\sum_{i=1}^n \gamma_i^2}\right\} < 2\exp\left\{-\frac{2t^2}{n\Gamma^2}\right\},$$ where $S_n := X_1 + \dots + X_n$.


Weak Dependence. We can think of weakly dependent random variables in a time sense. That is, suppose we are given a time dependent sequence of random variables $\{X_t\}_{t=1}^{\infty}$. If we fix a $t$ and let $s \in \mathbb{N}$, then for any $X_t$ and $X_{t + s}$ as $s$ increases the $\text{Cov}(X_t, X_{t+s})$ decreases to $0$ asymptotically (e.g. exponential decay).

  • $\begingroup$ just small covariance isn't enough to give a Hoeffding-like inequality; even pairwise independence (zero covariance) is not enough $\endgroup$
    – user125932
    Oct 25, 2020 at 2:33
  • $\begingroup$ Are there any such concentration bounds we can work with when we don’t have strict independence? $\endgroup$
    – EzioBosso
    Oct 26, 2020 at 2:56
  • 1
    $\begingroup$ You can get the same bound if your variables are negatively associated, Proposition 5 in Dubhashi-Ranjan paper brics.dk/RS/96/25/BRICS-RS-96-25.pdf $\endgroup$
    – Max
    Oct 26, 2020 at 10:00


You must log in to answer this question.

Browse other questions tagged .