For $1\le i_1,i_2,...,i_k\le N$ denote $$p_{i_1,...,i_k}=\Pr(A_{i_1}\cap A_{i_2}\cap\dots\cap A_{i_k}),$$ $$S_k=\sum\limits_{1\le i_1\le\dots\le i_k\le N}p_{i_1,\dots,i_k}.$$

Show that the probability $P_{[m]}$ that exactly $m$ among the $N$ events $A_1,\dots,A_N$ occur simultaneously is given by $$P_{[m]}=S_m-\binom{m+1}{m}S_{m+1}+\binom{m+2}{m}S_{m+2}-\dots (-1)^{N-m}\binom{N}{m}S_{N}.$$

We've already proven the inclusion exclusion formula: $$\Pr\left(\bigcup\limits_{i=1}^NA_i\right)=S_1-S_2+S_3-\dots (-1)^{N-1}S_N,$$

but the problem is the factors $\binom{m+1}{m}...$ before $S_i$'s, I cannot really show that.


Define $B_{m,N}:=\left\{\omega,\sum_{j=1}^N\mathbf 1_{A_j}(\omega)=m\right\}$ and denote $[N]:=\{1,\dots,N\}$ and $|J|$ the cardinal of a subset of $[N]$. We first use pointwise equalities of indicator functions. We have, using at the second step the pointwise equality which leads to the inclusion exclusion formula,
\begin{align} \mathbf 1\left(B_{m,N}\right)&=\sum_{\substack{J\subset [N]\\ |J|=m}}\mathbf 1\left(\bigcap_{j\in J}A_j\right)\cdot \left(1-\mathbf 1\left(\bigcup_{j\in J^c}A_j\right)\right)\\ &=\sum_{\substack{J\subset [N]\\ |J|=m}}\mathbf 1\left(\bigcap_{j\in J}A_j\right)\cdot \left(1- \sum_{l=1}^{N-m}(-1)^{l-1}\sum_{\substack{K\subset [N]\setminus J\\ |K|=l}}\mathbf 1\left(\bigcap_{k\in K}A_k\right)\right)\\ &=\sum_{\substack{J\subset [N]\\ |J|=m}}\mathbf 1\left(\bigcap_{j\in J}A_j\right) +\sum_{l=1}^{N-m}(-1)^l\sum_{\substack{J\subset [N]\\ |J|=m}}\sum_{\substack{K\subset [N]\setminus J\\ |K|=l}}\mathbf 1\left(\bigcap_{j\in J\cup K}A_j\right). \end{align} Now, we take expectations: the first term is $S_m$. For $1\leqslant l\leqslant N-m$, notice that a subset of $l+m$ elements of $[N]$ can be written in $\binom{m+l}m$ ways as the union of two disjoint elements of cardinality $m$ and $l$ respectively, hence $$\sum_{\substack{J\subset [N]\\ |J|=m}}\sum_{\substack{K\subset [N]\setminus J\\ |K|=l}}\mathbb P\left(\bigcap_{j\in J\cup K}A_j\right)=\binom{m+l}mS_{m+l}.$$

  • 1
    $\begingroup$ How do I get the last step? I think you want to apply the Expected value on both sides. But how can the product $\chi_{A_j} \chi_{B_{m,N}}$ be simplified? Somehow the factor $\chi_{B_{m,N}}$ on the right side has to be eliminated. $\endgroup$ – user148692 Mar 15 '16 at 23:14
  • $\begingroup$ @user144697 You are right, it is not immediate. I wrote the argument in a different way. $\endgroup$ – Davide Giraudo Mar 20 '16 at 12:03
  • $\begingroup$ What is the $\left ( 1- \cup_{j \in J^c} A_j \right )$? I am having trouble understanding if that is a numeric value or a set. What is the $\cdot$ (dot) character between that and $\left ( \cap_{j \in J} A_j \right )$? Is the indicator function of these two groupings taken separately? Also, thanks very much for posting this, I'd really like to try to understand it. $\endgroup$ – Nelson Apr 19 '16 at 21:08
  • $\begingroup$ @Nelson I have edited, it was a typo. $\endgroup$ – Davide Giraudo Apr 20 '16 at 12:16
  • $\begingroup$ Thanks! I just got finished working through your proof, this is a problem in the "Probability Theory: A Concise Course" Dover book. It really had me stumped, and yours is the most approachable proof. Much appreciated. $\endgroup$ – Nelson Apr 20 '16 at 13:56

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.