# Bounding the probability of a set of non independent events

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

• As for your comment about recursively applying the first inequality, I don't follow what you are saying – HXSP1947 Feb 11 at 19:56
• 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. – HXSP1947 Feb 11 at 20:00
• 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$. – antkam Feb 11 at 20:02
• 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 – HXSP1947 Feb 11 at 20:03
• 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$ – HXSP1947 Feb 11 at 20:04