Let $A_1,\ldots,A_n$ be events such that each of them is independent to all but at most $d$ of them. Let $0 < \epsilon < 1$ and assume that for $i= 1,\ldots,n$ we have $$p := \Pr[A_i] \leq \frac{\epsilon}{n}\left(1- \frac{\epsilon}{n}\right)^d.$$
I would like to show that this implies $\Pr[ \overline{A}_1 \cdots \overline{A}_n] \geq 1 - \epsilon.$
Now the form here appears to be suitable for application of the Lovász Local Lemma. Blindly assuming for a while that the condition of LLL is satisfied this would imply that
$$\Pr[ \overline{A}_1 \cdots \overline{A}_n] \geq (1-2p)^n$$ but plugging in the bound for $p$ gives a messy expression that I cannot bound to $1-\epsilon.$
Hence I am wondering
- Is there any other more direct way to show this claim.
- Is there perhaps a quick argument why $(1-2p)^n \geq (1-\epsilon)?$
For 1) you basically just have to apply De Morgan's law, i.e.
$$\Pr\left[\bigcap_{i=1}^n A_i^c\right] = 1 - \Pr\left[\bigcup_{i=1}^n A_i\right]$$
Your requested bound now follows from Boole's inequality:
$$\Pr\left[\bigcup_{i=1}^n A_i\right] \leq \sum_{i=1}^n \Pr[A_i] \leq n\frac{\varepsilon}{n} \left(1-\frac{\varepsilon}{n}\right)^d \leq \varepsilon$$