By Inclusion-Exclusion Principle, we know that if $A_1,\ldots,A_n$ are $n$ sets, then $$\left|\bigcup_{i=1}^nA_i\right|=\sum_{k=1}^n(-1)^{k+1}\left(\sum_{1\leq i_1<\cdots<i_k\leq n}|A_{i_1}\cap\cdots\cap A_{i_k}|\right).$$

I wonder, what if we cut the outer sum on the right to just $\sum_{k=1}^r$ for some $r\leq n$? Will we guarantee inequality in one way or the other?

For $r=1$, it is obvious by Boole's Inequality that the left-hand side is $\leq$ the right-hand side.

I think that the same should hold for $r$ odd, and the reverse inequality should hold for $r$ even. Any proof/counterexamples for that?


Aren't these the Bonferroni inequalities, which are in the same Wikipedia article that you linked to in your question? This old question asked "How to prove Bonferroni inequalities"; Did's answer gives some hints:

A proof is there. The main idea is that this is the integrated version of analogous pointwise inequalities and that, for every $k$, $$ S_k=\mathbb E\left({T\choose k}\right),\qquad T=\sum_{i=1}^n\mathbf 1_{A_i}. $$ Hence the result follows from the stronger inequalities asserting that, for every positive integer $N$, $$ \sum_{i=0}^k(-1)^ia_i,\qquad a_i={N\choose i}, $$ is nonnegative when $k$ is even and nonpositive when $k$ is odd. In turn, this fact follows from the properties that the sequence $(a_i)_{0\leqslant i\leqslant N}$ is unimodal and that $\sum\limits_{i=0}^N(-1)^ia_i=0$.

  • $\begingroup$ No reason to downvote; better to see whether OP can discuss relation of Bonferroni to the question at hand. $\endgroup$ – Gerry Myerson Oct 4 '13 at 13:04
  • $\begingroup$ I think it's just the same as the Bonferroni you linked to, just the count replaced by probability. How do you prove Bonferroni though? $\endgroup$ – PJ Miller Oct 4 '13 at 13:14
  • $\begingroup$ The link in my answer is resurrected (and I took the liberty to modify your answer accordingly). $\endgroup$ – Did Oct 4 '13 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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