So the question is that if we have a sequence $A_1,A_2,...,A_n$ of events, and let $N_k$ be the events that exactly $k$ of the $A_i$ occur. What is the probability of event $N_k$?

Prove that it is $P(N_k)=\sum_{i=0}^{n-k}(-1)^i\binom{k+i}{k}S_{k+i} $ where $S_j=\sum_{i_1<i_2<...<i_j}P(A_{i_1}\cap A_{i_2} \cap...\cap A_{i_n})$

  • 1
    $\begingroup$ It depends on how the $A_i$'s depend on one another. If there are $n$ fair coins that are each flipped and $A_i$ is the event that coin $i$ is heads, then the $A_i$'s are independent and $P(N_k) = {n \choose k}2^{-n}$. If there is a single fair coin flipped and each $A_i$ is the probability that the coin landed on heads, then $P(N_k) = 0$ for $1 \le k \le n-1$, $P(N_0) = \frac{1}{2}$, and $P(N_n) = \frac{1}{2}$. $\endgroup$ – mathworker21 Sep 21 at 0:34
  • $\begingroup$ Shouldn't it be $S_j = \sum_{1 \le i_1 < ... < i_j \le n} \mathbb P ( \bigcap_{r=1}^j A_{i_r})$? Instead of that union under $\mathbb P()$ $\endgroup$ – Dominik Kutek Sep 21 at 1:13
  • $\begingroup$ yes exactly, ill correct it $\endgroup$ – user 42493 Sep 21 at 1:17
  • $\begingroup$ @user42493 I can't fathom why you would wait until adding that edit. We're not mind readers. $\endgroup$ – mathworker21 Sep 21 at 1:52
  • $\begingroup$ :) :) :) indeed! I was just curious how you would solve it without knowing the formula! :):):) $\endgroup$ – user 42493 Sep 21 at 1:53

So, we have probability space $(\Omega, \mathcal F, \mathbb P)$, and let $A_1,...,A_n \in \mathcal F$ be arbitrary events. I'd change notation, especially $k$ with $r$ because I like to use $k$ as an index under $\sum$ sign. So let's fix any $r \in \{1, ... ,n\}$ and let $N_r \in \mathcal F$ be event : Exactly $r$ of $A_1,...,A_n$ occurs. Let $S_k(n) = \{ T \subset \{1,...,n\} : |T| = k \} $ ($k-$ element subsets of $\{1,...,n\}$. Finally for $T \subset \{1,...,n\}$ let $A_T = \bigcap_{ j \in T} A_j $

We'd like to prove (I've translated the index of sum): $$\mathbb P(N_r) = \sum_{k=r}^n (-1)^{k-r} {k \choose r} \sum_{T \in S_k(n)}\mathbb P(A_T)$$


Fix any $K \in S_r(n)$. Let $B_K$ be the event: $A_i$ occur if and only if $i \in K$ ( that is exactly $r$ of $A_1 ,... ,A_n$ occured and only those with indices from $K$). Now, for $j \notin K$ let $C_j = A_K \cap A_j$. We're interested in $\mathbb P(B_K)$. Note that we can now use Inclusion-Exclusion formula, because $\mathbb P(B_K) = \mathbb P( \bigcap_{j \notin K} (A_K \setminus C_j)) $. To remind, set $K$ is fixed, and there is exactly $n-r$ indices in $L = [n]\setminus K$, where $[n] = \{1,...,n\}$ And again let $C_T = \bigcap_{j \in T} C_j$, where $T \subset [n]$

Using Inclusion-Exclusion, we have:

$$ \mathbb P(B_K) = \sum_{k=0}^{n-r} (-1)^k \sum_{T \in S_k(L)} \mathbb P(C_T) = \sum_{k=0}^{n-r} (-1)^k \sum_{T \in S_k(L)} \mathbb P( A_K \cap A_T) = \sum_{k=0}^{n-r} (-1)^k \sum_{T \in S_k(L)} \mathbb P(A_{T \cup K}) = \sum_{k=r}^n \sum_{T: K \subset T, T \in S_k(n)} (-1)^{k-r} \mathbb P(A_T) = \sum_{T: K \subset T \subset [n]} (-1)^{|T|-r} \mathbb P(A_T)$$

Now what we need to do, is to sum it for every $K \in S_r(n)$ (note $B_{K_1}, B_{K_2}$ are disjoint for any $K_1 \neq K_2$)

And we have:

$$ \mathbb P(N_r) = \mathbb P(\bigcup_{K \in S_r(n)} B_K) = \sum_{K \in S_r(n)}\mathbb P(B_K) =\sum_{K \in S_r(n)}\sum_{T: K \subset T \subset [n]} (-1)^{|T|-r} \mathbb P(A_T) = \sum_{T: |T| \ge r} \sum_{R \in S_r(T)} (-1)^{|T|-r} \mathbb P(A_T) = \sum_{T: |T| \ge r} {|T| \choose r} (-1)^{|T| - r} \mathbb P(A_T) = \sum_{k=r}^n \sum_{T \in S_k(n)} {k \choose r} (-1)^{k-r} \mathbb P(A_T) = \sum_{k=r}^n (-1)^{k-r} {k \choose r} \sum_{T \in S_k(n)} \mathbb P(A_T) $$

Which is exactly what we wanted to prove.

  • $\begingroup$ The proof isn't my own, I've just recall and modify a little bit proof I've seen once, about combinatorial identity. The most "tricky" part for me is to come up with these disjoint events $B_K$. $\endgroup$ – Dominik Kutek Sep 21 at 2:05
  • 1
    $\begingroup$ I know in my gut that there is a natural, intuitive, motivated proof, but I'm too lazy to figure it out $\endgroup$ – mathworker21 Sep 21 at 12:02
  • $\begingroup$ I hope so, too :D $\endgroup$ – Dominik Kutek Sep 21 at 12:22

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.