1
$\begingroup$

Let $A_1, A_2, ... , A_n$ be events and let $N_k$ be the event that exactly $k$ of the $A_i$ occur. Prove the result sometimes referred to as Waring's theorem:

$$P(N_k) = \sum_{i=0}^{n-k} (-1)^i {k+i \choose k}S_{k+i}, \text{where $S_j = \sum_{i_1 < i_2 < ... <i_j} P(A_{i_1} \cap A_{i_2}\cap ... \cap A_{i_j}).$}$$

Solution: Clearly, $$P(N_k) = \sum_{S \subseteq \{1,2, ... , n\};|S| = k} P\left(\bigcap_{i \in S} A_i \bigcap_{j \not\in S} A_j^c \right).$$ For any such given $S$, we write $A_S = \bigcap_{i\in S}A_i$. Then, \begin{equation} P\left(\bigcap_{i \in S} A_i \bigcap_{j \not\in S} A_j^c \right) = P(A_S) - \sum_{j \not\in S} P(A_{S \cup \{j\}})+ \sum_{j<k;j,k \not\in S} P(A_{S \cup \{j,k\}}) - ... \end{equation} Hence $$P(N_k) = \sum_{|S| = k} P(A_S) -\sum_{|S| = k+1}{k+1 \choose k}P(A_S)+ ... + (-1)^{n-k}{n \choose k} P(A_1 \cap ... \cap A_n)$$ where a typical summation is over all subsets $S$ of $\{1, 2, ..., n\}$ having the required cardinality.

I am not sure how the author derives the last and the second last display in the solution. I guess he uses the previous results that

$$P\left(\bigcap_{1}^n A_i \right) = \sum_i P(A_i) - \sum_{i < j} P(A_i \cup A_j) + \sum_{i < j <k} P(A_i \cup A_j \cup A_k) - ... - (-1)^n P(A_1\cup A_2 \cup ... \cup A_n).$$ or similarly, $$P\left(\bigcup_{1}^n A_i \right) = \sum_i P(A_i) - \sum_{i < j} P(A_i \cap A_j) + \sum_{i < j <k} P(A_i \cap A_j \cap A_k) - ... - (-1)^n P(A_1\cap A_2 \cap ... \cap A_n)$$ in some way, but I can't figure it out by myself. I appreciate if you give some help.

$\endgroup$
1
  • $\begingroup$ Does $P\left((\bigcap_{i \in S} A_i \bigcap_{j \not\in S} A_j^c \right)$ mean $P\left(\bigcap_{i \in S} A_i ) \bigcap (\bigcap_{j \not\in S} A_j^c \right)).$ ?? $\endgroup$
    – MathMan
    Commented Mar 14, 2021 at 15:44

1 Answer 1

2
$\begingroup$

For the second last display, write $$\begin{align} P\left(A_S\bigcap A_j^c\right) = P\left(A_S\cap\left(\bigcup A_j\right)^c\right) &\stackrel{(*)}=P(A_S)-P\left(A_S\cap \left(\bigcup A_j\right)\right)\\ &=P(A_S)-P\left(\bigcup (A_S\cap A_j)\right) \end{align} $$ and then use inclusion-exclusion on the rightmost union (which is a union over $j\not\in S$). The equality (*) is the identity $P(A\cap B^c)=P(A)-P(A\cap B)$.

For the last display, we sum every term of the previous display over all subsets $S$ with $|S|=k$. The first term that we get (the one with $|S|=k$) is obvious. For the second term, the assertion is that $$ \sum_{|S|=k}\sum_{j \not\in S} P(A_{S \cup \{j\}})=\sum_{|S|=k+1}{k+1\choose k}P(A_S). $$ The reason this is true: the LHS is selecting a subset $S$ of size $k$ and then, given $S$, selecting an element $j$ not in $S$. The RHS is selecting a subset of size $k+1$ and then choosing an element from that subset to be $j$. There are clearly $k+1\choose k$ ways to pick $j$, so the RHS achieves the same sum as the LHS. The remaining terms are argued similarly.

$\endgroup$
2
  • $\begingroup$ Does $P\left((\bigcap_{i \in S} A_i \bigcap_{j \not\in S} A_j^c \right)$ mean $P\left(\bigcap_{i \in S} A_i ) \bigcap (\bigcap_{j \not\in S} A_j^c \right)).$ ?? $\endgroup$
    – MathMan
    Commented Mar 14, 2021 at 15:41
  • $\begingroup$ Yes, the middle $\cap$ is implied between $\bigcap_{i\in S}A_i$ and $\bigcap_{j\not\in S}A_j^c$. $\endgroup$
    – grand_chat
    Commented Mar 14, 2021 at 22:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .