5

Problem Statement:
Given any $n$ events $A_1,A_2, ...,A_n$, prove that the probability of exactly $m$ ($m \le n$) of them happening is $$P_m - \binom{m+1}{m}P_{m+1} + \binom{m+2}{m}P_{m+2} - \cdots \pm \binom{n}{m}P_n$$ where $P_k = \sum_{1\le i_1<i_2 \cdots <i_k \le n}\Pr(\bigcap_{r=1}^k A_{i_r})$

My thoughts:
This looks quite similar to the inclusion-exclusion principle where we had: $$\sum_{i=1}^n(-1)^{i+1}P_i$$ but here we have $$\sum_{i=m}^n(-1)^{i+m}\binom{i}{m}P_i$$ I understand that $P_k$ implies you should sum the probabilities of all the combinations of $A$ of length $k$. Since this already includes the combinations, I don't understand why we need a binomial coefficient before each term.
To find the required probability, one can add all possible probabilities of a combination of $m$ events happening, then subtract those of $m+1$ events happening (since the first one includes this).

The same question has been asked before here and here. But in the first one, the answerer uses the Indicator function (I'm aware of its basic properties, but the answerer does something which is not clear to me), and in the second, the OP themselves provide an answer (but it has a flaw (?) - they take $\Pr(M \cap N^C) = \Pr(M) - \Pr(N)$). So, I'm looking for an answer that at least clearly states how can I proceed with the proof, the reason for the binomial coefficients and uses the Indicator function as less as possible (since till now the author has not discussed it in the book).

D S
  • 4,961

1 Answers1

2

There would be no binomial coefficients, and we would be able to use the ordinary principle of inclusion-exclusion, if we worked with the following quantities:

  • $P_I$, the probability that for all $i \in I$, $A_i$ happens;
  • $Q_I$, the probability that for all $i \in I$, $A_i$ happens while for all $i \notin I$, $A_i$ does not happen.

To find $Q_I$ in terms of the probabilities $\{P_J : J \supseteq I\}$, we use inclusion-exclusion on all the events $A_i$ with $i \notin I$. We:

  • Start by adding in $P_I$.
  • Subtract off $P_{I \cup \{i\}}$ for each $i \notin I$.
  • Add back in $P_{I \cup \{i_1, i_2\}}$ for every pair $\{i_1, i_2\}$ with $i_1, i_2 \notin I$.
  • Subtract off $P_{I \cup \{i_1, i_2, i_3\}}$ and so forth.

This can be summarized as a sum over all sets $J$ containing $I$ as: $$ Q_I = \sum_{J \supseteq I} (-1)^{|J|-|I|} P_J. $$ Now, we want to go from here to expressing $Q_m$ (the probability that exactly $m$ events happen, but we don't care which ones) in terms of $P_m$. The relationship here is that $Q_m$ is a sum of $Q_I$ over all $I$ with $|I|=m$, while $P_m$ (as defined in the question) is a sum of $P_I$ over all $I$ with $|I|=m$. From our previous equation, we have $$ Q_m = \sum_{|I| = m} \sum_{J \supseteq I} (-1)^{|J|-|I|} P_J. $$ This is a double sum over all pairs $(I,J)$ with $|I|=m$ and $I \subseteq J$. Let's write the sum in a different order. First, make it a sum over all $k$ from $0$ to $n-m$; second, for each $k$, sum over all $J$ with $|J|=m+k$; third, for each $k$ and $J$, sum over all $I$ with $|I|=m$ and $I \subseteq J$. We get $$ Q_m = \sum_{k=0}^{n-m} \sum_{|J|=m+k} \sum_{I \subseteq J, |I|=m} (-1)^k P_J. $$ The expresion $(-1)^k P_J$ does not actually depend on $I$ at this point. So instead of summing over all $I$, we can just multiply by the number of terms in that inner sum. That number is $\binom{m+k}{m}$ (the number of $m$-subsets of $J$) which is where the binomial coefficients appear. We get $$ Q_m = \sum_{k=0}^{n-m} \sum_{|J|=m+k} (-1)^k \binom{m+k}{m} P_J. $$ Finally, the sum of $P_J$ over all $J$ with $|J|=m+k$ is just the definition of $P_{m+k}$, so we can write the last equation more simply as $$ Q_m = \sum_{k=0}^{n-m} (-1)^k \binom{m+k}{m} P_{m+k} $$ which was what we wanted.

Misha Lavrov
  • 142,276