Boole's Inequality - Proof & Mathematical Form

# Boole's Inequality

In mathematics, the probability theory is an important branch which studies about the probabilities of the random phenomena. The probability is said to be the measurement of chances of happening an event which is an outcome of an experiment.

For Example: tossing a coin is an experiment and getting head or tail is an event. Ideally, there are 50%-50% chances, that is $\frac{1}{2}$ probability of getting either a head or a tail. There are various important concepts in probability theory. The Boole's inequality is one of them.

## Proof

We will prove the Boole’s inequality by using the method of induction:

When n = 1, the inequality is

$P (E_{1}) \leq P (E_{1})$ which is true always.

Assume that it also holds for i = k.

That is $P (\cup_{c= 1}^{k} E_{c}) \leq \sum_{c = 1}^{k} P(E_{c})$ is true.

Now, we will prove that the inequality holds for i = k + 1

When i = k + 1 we have,

$P (\cup_{j = 1}^{k + 1} E_{j})$

= $P (\cup_{j = 1}^{k} E_{j} \cup E_{k + 1})$

= $P (\cup_{j = 1}^{k} E_{j}) + P (E_{k + 1}) - P (\cup_{j = 1}^{k} E_{j} \cap E_{k +1})$

We know that $P (\cup_{j = 1}^{k} E_{j} \cap E_{k +1}) \geq 0$

$\Rightarrow P(\cup_{j = 1}^{k + 1} E_{j}) \leq P(\cup_{j = 1}^{k} E_{j}) + P (E_{k + 1})$

$\Rightarrow P(\cup_{j = 1}^{k + 1} E_{j}) \leq \sum_{j = 1}^{k} P (E_{j}) + P(E_{k + 1})$

$\Rightarrow P(\cup_{j = 1}^{k + 1} E_{j}) \leq \sum_{j = 1}^{k + 1} P (E_{j})$

We conclude that since the inequality holds for i = k +1 when it holds for i = k, so by the principle of mathematical induction, we can say that $P (\cup_{j = 1}^n E_{j}) \leq \sum_{j = 1}^{n} P (E_{j})$ for all ‘n’.

We can generalize the Boole’s inequality in case of probability of events in finite union in order to find their upper and lower bounds. We call these bounds Bonferroni inequalities.

For this we are first defining three different summations :

1)
$X_{1} = \sum_{j = 1}^{n} P(B_{i})$

2)
$X_{2}= \sum_{1 \leq i < j \leq n} P(B_{i} \cap B_{j})$

3)
$X_{k} = \sum_{1 \leq i_{1} < …. <i_{k} \leq n} P (B_{i_{1}} \cap …. \cap B_{i_{k}})$

For all natural numbers starting from 3 to n.

With these three definitions, we move ahead by following observations:

For any odd value of k in the set {1, …., n} we will have,

$P(\cup_{j = 1}^{n} B_{i}) \leq \sum_{j = 1}^{k} {-1}^{j - 1} X_{j}$ And for any even value of k in the set {2, 4, …, n} we will have,$P (\cup_{j = 1}^n {B_i}) >= \sum_{j = 1}^k {- 1}^{j – 1} {X_j}$

We can recover the original Boole’s inequality when k = 1. When k = n, then we will get the equality that holds true and then the identity that is obtained is known as the inclusion-exclusion principle.

## Mathematical Form

The other most commonly used name for Boole’s inequality is the "union bound". The Boole’s inequality is stating that if we have been given some countable events, that is, a finite set of events, then the probability of occurrence of at least one of the events is clearly less than or equal to the sum of the probabilities of the occurrences of these individual events. This can be rewritten mathematically in the following form.

Let
$E_{k}$ be a set of events and the probability that $E_{k}$ is true is $P(E_{k})$. The probability that at least any one of $E_{1}, ..., E_{n}$ is true, is denoted by $P(\cup _(i=1)^{k}E_{k})$. Then Boole's inequality is given by the following relation:

$P (\cup_{k = 1}^{n} E_{k}) \leq \sum_{k = 1}^{n} P (E_{k})$
Where $E_{k}$, for k = 1, …,n are the given set of finite or countable events.