Suppose I have the following events $A_0, A_1, ... A_N$. These events are not independent. I want to know the probability of the event $A_0 \cap A_1 \cap ... \cap A_N$ occurring. However, I don't have the information I need to do this. All I know is the probability of each individual event (i.e. $P(A_0)$, $P(A_1)$, etc). Instead, I would like to create a lower bound on the probability.

From here I found the following inequality

$$P(B \cap C) \geq max(0, P(B) + P(C) - 1)$$

Using this inequality I can write (I believe, correct me if I am wrong)

$$P(A_0 \cap A_1 \cap ... \cap A_N) \geq max(0, P(A_0) + P(A_1 \cap ... \cap A_N) - 1)$$

Observing that

$$P(A_1 \cap ... \cap A_N) \leq min(P(A_1), ... , P(A_N))$$

I then can observe that

$$P(A_0 \cap A_1 \cap ... \cap A_N) \geq max(0, P(A_0) + min(P(A_1), ... , P(A_N)) - 1)$$

WLOG, if I were to sort $A_0, A_1, ... A_N$ such that $P(A_0)$ has the highest probability and $P(A_N)$ the lowest I would then have a "decent" bound given the information I have available (I say decent since most of the time there will be strong dependencies between events, i.e. event $A_0$ can only occur if $A_1$ has occurred. However, this statement is not true in general.).

My question(s) are the following.

(1) Is my reasoning correct?

(2) Is there a better way to do what I want?


Sorry, that doesn't work. You made an algebraic error when substituting, specifically, an error in the direction of the $\ge$ sign.

First you can drop the $\max(0, *)$ part - your LHS is a probability which is always non-negative anyway. After dropping that, what you have is similar to $X \ge Y - 1$ and $Y \le Z$, but you cannot combine them to get $X \ge Z - 1$. If you have $Y \ge Z$ then you can combine them, but you only have $Y \le Z$ which is the wrong direction.

Instead, you can apply the first inequality recursively to get:

$$P(A_0 \cap ... \cap A_N) \ge \sum^N_{j=0} P(A_j) - N$$

Without more info, this inequality is tight. E.g. imagine you have $N+1$ balls labelled $j \in \{0, 1, ..., N\}$ and one is picked at random, and $A_j = $ the event that ball $j$ is NOT picked. So $P(A_j) = {N \over N+1} $ and both sides $= 0$.

Follow-up details on the recursion:

$$P(A_0 \cap ...\cap A_N) \ge (P(A_0) - 1) + P(A_1 \cap ... \cap A_N) \ge (P(A_0) -1) + (P(A_1) - 1) + P(A_2 \cap ... \cap A_N) \ge ... \ge \sum^{N-1}_{j=0} (P(A_j) - 1) + P(A_N) = ( \sum^N_{j=0} P(A_j) ) - N$$

  • $\begingroup$ As for your comment about recursively applying the first inequality, I don't follow what you are saying $\endgroup$ – HXSP1947 Feb 11 at 19:56
  • $\begingroup$ Looking at the inequality you gave closer, I'm nor sure that it makes sense at all. The summation on the right hand side can be greater than 1 which isn't useful at all. $\endgroup$ – HXSP1947 Feb 11 at 20:00
  • $\begingroup$ LHS = left hand side = $P(A_0 \cap ... \cap A_N)$ is a probability, which is always non-negative. It doesnt hurt if you say e.g. $P(...) \ge -0.3$ because that is still a true statement (albeit trivially true). It is just as trivially true as $P(...) \ge \max(0, -0.3) = 0$. $\endgroup$ – antkam Feb 11 at 20:02
  • $\begingroup$ True, however, I want to use this inequality so that the substitution is as tight as possible. Therefore it makes sense to make sure it's always non negative $\endgroup$ – HXSP1947 Feb 11 at 20:03
  • $\begingroup$ LATE EDIT: "your LHS is a probability which is always non-negative anyway", I assume you mean LHS to mean "left hand side"? if so this is not true. This could be negative so I need the max(0,*) (what if the probability of both events is zero?). "𝑋≥𝑌−1 and 𝑌≤𝑍, but you cannot combine them to get 𝑋≥𝑍−1" is not what I have at all. Using your notation I have 𝑋≥𝑌+𝑍−1 and 𝑍≤𝑊. Substituting I get 𝑋≥𝑌+𝑍−1≥𝑌+𝑊−1. Or am I missing what you are saying? All I am doing is substituting the event 𝐶 from the first inequality with the event $𝐴_1∩...∩𝐴_N$ $\endgroup$ – HXSP1947 Feb 11 at 20:04

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.