1
$\begingroup$

I am facing this problem while writing a code.

Assume that we have the following sets:

$$S_1= \{P_1, P_2, P_3, P_9\}$$ $$S_2= \{P_2, P_4, P_6, P_9\}$$ $$S_3= \{P_6, P_7, P_8, P_9\}$$ $$S_4= \{P_3, P_5, P_7, P_9\}$$

Let $T$ be a set that contains some $P_i$ where $1 \le i \le 9$ such that the probability of $P_i$ being in $T$ is $K_i$ (in my case, $K_i \in \{0, 0.2\}$ but let's just say $K_i$). What is the probability $A$ that $T$ contains at least an element from each $S_i$?

I couldn't find a simple formula to solve this. I am not sure if it is easier to approach this if we try to find $1 - A$ first.

$\endgroup$
1
$\begingroup$

Let $L_i=1-K_i$.
Let $M_i$ be the event that $S_i$ is entirely missing.
Then, using Inclusion-Exclusion, $$A = 1...\\-Pr(M_1)-Pr(M_2)-Pr(M_3)-Pr(M_4)\\+Pr(M_1\cap M_2)+Pr(M_1\cap M_3)+...\\ -Pr(M_1\cap M_2\cap M_3)-Pr(M_1\cap M_2\cap M_4)-...\\ +Pr(M_1\cap M_2\cap M_3\cap M_4)\\ =1-L_1L_2L_3L_9-L_2L_4L_6L_9-L_6L_7L_8L_9-L_3L_5L_7L_9\\ +L_1L_2L_3L_4L_6L_9+L_1L_2L_3L_6L_7L_8L_9+...\\ -L_1L_2L_3L_4L_6L_7L_8L_9-...\\ +L_1L_2L_3L_4L_5L_6L_7L_8L_9 $$ There will be four terms with one $M_i$, six terms with two $M_i$, four terms with three $M_i$ and one with all four $M_i$. That makes 16 terms including the initial $1$.

$\endgroup$
1
$\begingroup$

As a first approach, one can examine all $2^9$ possible outcomes. Each outcome is like $o_t =(0,0,1,0,1,0,0,1,0)$ where $t=1,\dots,2^9$. The probability of $o_t$ is always $P(o_t)=\prod_i K_i^{o_{t,i}}(1-K_i)^{1-o_{t,i}}$. For each $o_t$ you can automatically check whether it satisfies the condition, i.e. $o_t\in A$. Since all elementary events are independent, you can sum it as $$P(A)=\sum_{o_t\in A} P(o_t)$$.

I know this is not an elegant closed form, but I think that it is implementable easily.

$\endgroup$

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.