<p>The usual statement of a Hoeffding bound (e.g. <a href="https://sites.math.washington.edu/%7Emorrow/335_17/ineq.pdf" rel="noreferrer">https://sites.math.washington.edu/~morrow/335_17/ineq.pdf</a>) requires independent random variables.</p>
<p>My question is: Do there exist bounds similar to Hoeffding's that apply in the case that, for Bernoulli R.V. <span class="math-container">$X_i$</span> for <span class="math-container">$i \in [n]$</span></p>
<p><span class="math-container">$\Pr\left[\bigcap_{i}X_i\right] = \left(\prod_i \Pr[X_i]\right) + \delta$</span> for <span class="math-container">$\delta &lt;&lt; 1$</span>, maybe specifically for the case that <span class="math-container">$\delta$</span> is a negligible function on <span class="math-container">$n$</span>?</p>
<p>Thanks.</p>

CC BY-SA 4.0
2021-04-02T21:36:47.493Z
I don't know of one, but you could try following the proof to see what changes...should be okay if you can show $\mathbb{E} \prod_i e^{\lambda X_i} \approx \prod_i \mathbb{E} e^{\lambda X_i}$.
usul
CC BY-SA 4.0
2021-04-03T22:03:02.250Z
I agree. I figured I'd ask in case this work has already been done :) Thank you
zfkmz
CC BY-SA 4.0
2021-04-04T06:08:01.520Z
Your setting is a bit similar to Jason's inequality. Did you try that one?
Thomas Ahle
<pr.probability><randomized-algorithms>
Are there any known Chernoff/Hoeffding bounds for the case of "almost independence"?
zfkmz
# Are there any known Chernoff/Hoeffding bounds for the case of "almost independence"?

(Asked by: username_0 on 2021-04-02)

The usual statement of a Hoeffding bound (e.g. [https://sites.math.washington.edu/~morrow/335\_17/ineq.pdf](https://sites.math.washington.edu/%7Emorrow/335_17/ineq.pdf)) requires independent random variables.

My question is: Do there exist bounds similar to Hoeffding's that apply in the case that, for Bernoulli R.V. $X\_i$ for $i \in [n]$

$\Pr\left[\bigcap\_{i}X\_i\right] = \left(\prod\_i \Pr[X\_i]\right) + \delta$ for $\delta << 1$, maybe specifically for the case that $\delta$ is a negligible function on $n$?

Thanks.

**Tags:** pr.probability, randomized-algorithms
> **Comments:**
> **username_1**: I don't know of one, but you could try following the proof to see what changes...should be okay if you can show $\mathbb{E} \prod_i e^{\lambda X_i} \approx \prod_i \mathbb{E} e^{\lambda X_i}$.  
> **username_0**: I agree. I figured I'd ask in case this work has already been done :) Thank you  
> **username_2**: Your setting is a bit similar to Jason's inequality. Did you try that one?  

---

## 0 answers

