The usual statement of a Hoeffding bound (e.g. https://sites.math.washington.edu/~morrow/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$?


  • 1
    $\begingroup$ 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}$. $\endgroup$
    – usul
    Apr 2, 2021 at 21:36
  • $\begingroup$ I agree. I figured I'd ask in case this work has already been done :) Thank you $\endgroup$
    – zfkmz
    Apr 3, 2021 at 22:03
  • $\begingroup$ Your setting is a bit similar to Jason's inequality. Did you try that one? $\endgroup$ Apr 4, 2021 at 6:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.