10

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.

Davide Giraudo
  • 172,925
OBDA
  • 1,715

1 Answers1

9

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}.$$

Davide Giraudo
  • 172,925
  • 1
    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. – user148692 Mar 15 '16 at 23:14
  • @user144697 You are right, it is not immediate. I wrote the argument in a different way. – Davide Giraudo Mar 20 '16 at 12:03
  • 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.

     – Nelson Apr 19 '16 at 21:08
  • @Nelson I have edited, it was a typo. – Davide Giraudo Apr 20 '16 at 12:16
  • 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. – Nelson Apr 20 '16 at 13:56