1
$\begingroup$

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

$\endgroup$
5
  • 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$ Commented Sep 21, 2019 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$ Commented Sep 21, 2019 at 1:13
  • $\begingroup$ yes exactly, ill correct it $\endgroup$ Commented Sep 21, 2019 at 1:17
  • $\begingroup$ @user42493 I can't fathom why you would wait until adding that edit. We're not mind readers. $\endgroup$ Commented Sep 21, 2019 at 1:52
  • $\begingroup$ :) :) :) indeed! I was just curious how you would solve it without knowing the formula! :):):) $\endgroup$ Commented Sep 21, 2019 at 1:53

2 Answers 2

2
+50
$\begingroup$

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)$$

PROOF:

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.

$\endgroup$
6
  • 2
    $\begingroup$ I know in my gut that there is a natural, intuitive, motivated proof, but I'm too lazy to figure it out $\endgroup$ Commented Sep 21, 2019 at 12:02
  • $\begingroup$ I hope so, too :D $\endgroup$ Commented Sep 21, 2019 at 12:22
  • $\begingroup$ @DominikKutek Could you take a look at the expression $C_j = A_K \bigcap A_j$ . What does this mean? $\endgroup$
    – MathMan
    Commented Mar 14, 2021 at 15:34
  • $\begingroup$ @DominikKutek You used $K$ to denote the subset of $\{1,\cdots,n\}$. Then what does $A_K$ mean here? $\endgroup$
    – MathMan
    Commented Mar 14, 2021 at 15:46
  • 1
    $\begingroup$ when $T \subset \{1,..,n\}$ I defined $A_T = \bigcap_{j \in T} A_j$ (I defined it at the first paragraph of the answer) $\endgroup$ Commented Mar 14, 2021 at 16:40
1
$\begingroup$

Take the formula $P(N_k)=\sum_{i=0}^{n-k}(-1)^i\binom{k+i}{k}S_{k+i}$ and expand every term of form $P(A_{i_1}\cap A_{i_2} \cap \dots \cap A_{i_p})$ into a sum of probabilities of form $P(X_1 \cap X_2 \cap \dots \cap X_n)$ where $X_i = A_i$ or $X_i = \overline{A_i}$, according to the law of total probability.

Now consider some $I = \{i_1, i_2, ..., i_m\} \subset \{1, ..., n\}$ where $k \leq m \leq n$.

Let's consider probability that exactly events from $I$ have occured. What multiplier would it have in $P(N_k)$ ?

$S_{k+i}$ would contain this probability $\binom{m}{k+i}$ times.

So in $P(N_k)$ it would be equal to $\sum_{i = 0}^{n - k} (-1)^i \binom{m}{k+i} \binom{k+i}{k} = \sum_{i = 0}^{n-k} (-1)^i \binom{m}{k}\binom{m-k}{i} = \binom{m}{k} \sum_{i=0}^{n-k}(-1)^i \binom{m-k}{i}$

If $m=k$ then this equals $1$.

If $k < m \le n$ then this equals $\binom{m}{k}(1 - 1)^{m-k} = 0$

So $P(N_k)$ counts total probabilities when exactly $k$ events have occured, and counts such probabilities exactly once. QED

$\endgroup$

You must log in to answer this question.

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