I have a set of Bernoulli random variables $X_1,X_2,\ldots, X_n$ and I would want to bound the joint probability $P(X_1=0,X_2=0,\ldots, X_n=0)$ using the norm $\lvert \lvert \mathbf{p}\rvert \rvert$, where $$\mathbf{p}:=[P(X_1=1)\quad P(X_2=1)\ldots P(X_n=1)]^\top$$

For the lower bound, I use Bonferroni's inequality: $P(\cap A_i)\ge \sum P(A_i)-N+1$ for events $\{A_i\}$. Defining $A_i:=\{X_i=0\}$,

\begin{align} P(X_1=0,X_2=0,\ldots, X_n=0)&\ge \sum P(X_i=0)-N+1\\ 1-P(X_1=0,X_2=0,\ldots, X_n=0)&\le N-\sum P(X_i=0)\\ &=\sum P(X_i=1)\\ &=\mathbf{1}^\top \mathbf{p}\\ &\le \sqrt{N}\lvert\lvert \mathbf{p}\rvert\rvert \end{align}

I wish to derive a similar bound on the other side, but I end up with trivial inequalities. Using $P(\cap A_i)\le \sum P(A_i)$ for events $\{A_i\}$,

\begin{align} P(X_1=0,X_2=0,\ldots, X_n=0)&\le \sum P(X_i=0)\\ 1-P(X_1=0,X_2=0,\ldots, X_n=0)&\ge 1-\sum P(X_i=0)\\ &=1-N+\sum P(X_i=1)\\ &=1-N+\lvert\lvert \mathbf{p}\rvert\rvert_1\\ &\ge 1-N+\lvert\lvert \mathbf{p}\rvert\rvert_2\\ \end{align}

Unfortunately the last bound is pretty trivial for probabilities. Can someone help me get a tight lower bound for $1-P(X_1=0,X_2=0,\ldots, X_n=0)$? Thanks!


1 Answer 1


$\mathsf{P}\{X_1 = 0, \dots, X_n = 0\} \le \min_i \mathsf{P} \{X_i = 0\} = 1 - \max_i p_i \le 1 - N^{-1/2} \Vert p \Vert_2$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.