Proof related to Axioms of Probability


These problems and Proofs are adapted from the textbook: Probability and Random Process by Scott Miller 2ed

Problem-1: Proof that for events A and B the following holds:

\(Pr\left(A\cup B\right) = Pr\left(A\right)+Pr\left(B\right)-Pr\left(A\cap B\right)\)

Solution: First, note that the sets \(A\cup B\) and \(B\) can be rewritten as

\(A\cup B=\{A\cup B\}\cap\{\overline{B}\cup B\}=\{A\cap\overline{B}\}\cup B\)

\(B=B\cap\{A\cup\overline{A}\}=\{A\cap B\}\cup\{\overline{A}\cap B\}.\)

Hence, \(A\cup B\) can be expressed as the union of three mutually exclusive sets.

\(A\cup B=\{\overline{B}\cap A\}\cup\{A\cap B\}\cup\{\overline{A}\cap B\}\)

Next, rewrite \(\overline{B}\cap A\) as

\( \overline{B} \cap A= \{\overline{B}\cap A\}\cup\{\overline{A}\cap A\}= A\cap\{\overline{A}\cup\overline{B}\} = A\cap\{\overline{A\cap B}\}\)

Likewise, \(\overline{A}\cap B=B\cap\{\overline{A\cap B}\}\). Therefore \(A\cup B\) can be rewritten as the following union of three mutually exclusive sets:

\(A\cup B=\{A\cap(\overline{A\cap B})\}\cup\{A\cap B\}\cup\{B\cap(\overline{A\cap B})\}\)

Hence
\(\begin{eqnarray*}Pr\left(A\cup B\right)=Pr\left(A\cap(\overline{A\cap B})\right)+Pr\left(A\cap B\right)+Pr\left(B\cap(\overline{A\cap B})\right).\end{eqnarray*}\)

Next, write A as the union of the following two mutually exclusive sets

\(A=\{A\cap\{\overline{A\cap B}\}\}\cup\{A\cap B\}\)

Hence,

\(Pr\left(A\right)=Pr\left(A\cap\{\overline{A\cap B}\}\right)+Pr\left(A\cap B\right)\)

and

\(Pr\left(A\cap\{\overline{A\cap B}\}\right)=Pr\left(A\right)-Pr\left(A\cap B\right).\)

Likewise,

\(Pr\left(B\cap\{\overline{A\cap B}\}\right)=Pr\left(B\right)-Pr\left(A\cap B\right).\)

Finally,

\(\begin{eqnarray*}Pr\left(A\cup B\right) & = & Pr\left(A\cap(\overline{A\cap B})\right)+Pr\left(A\cap B\right)+Pr\left(B\cap(\overline{A\cap B})\right)\\ & = & \left(Pr\left(A\right)-Pr\left(A\cap B\right)\right)+Pr\left(A\cap B\right)+Pr\left(B\right)-Pr\left(A\cap B\right)\\ & = & Pr\left(A\right)+Pr\left(B\right)-Pr\left(A\cap B\right). \end{eqnarray*}\)

Problem-2: Show that the Problem-1 can be generalized upto three events:

\( Pr(A\cup B\cup C) = Pr(A)+Pr(B)+Pr(C)-Pr(A\cap B)-Pr(A\cap C)-Pr(B\cap C)+Pr(A\cap B\cap C) \)

Solution:

\(\begin{eqnarray*}
{Pr(A\cup B\cup C)}\\
& = & Pr((A\cup B)\cup C)\\
& = & Pr(A\cup B)+Pr(C)-Pr((A\cup B)\cap C)\\
& = & Pr(A)+Pr(B)-Pr(A\cap B)+Pr(C)-Pr((A\cap C)\cup(B\cap C))\\
& = & Pr(A)+Pr(B)+Pr(C)-Pr(A\cap B)-Pr((A\cap C)\cup(B\cap C))\\
& = & Pr(A)+Pr(B)+Pr(C)-Pr(A\cap B)\\
& – & \left(Pr((A\cap C)+Pr(B\cap C))-Pr(A\cap C\cap B\cap C)\right)\\
& = & Pr(A)+Pr(B)+Pr(C)-Pr(A\cap B)-Pr(A\cap C)-Pr(B\cap C)+Pr(A\cap B\cap C)
\end{eqnarray*}\)

Problem-3: Prove that if  \(A \subset B \; \text{then} \; Pr(A) \leq Pr(B)\)

Solution: Since \(A\subset B\) and \(A\cap B=A\), \(B=A\cup\{B\cap\overline{A}\}\).
Since \(A\) and \(B\cap\overline{A}\) are mutually exclusive, we have
\( \begin{eqnarray}
Pr(B)=Pr(A)+Pr(B\cap\overline{A})\ .\label{eq1}
\end{eqnarray} \)
Hence by (\eqref{eq1}) and considering \(Pr(B\cap\overline{A})\ge0\), \(Pr(A)\le Pr(B)\).

Problem-4: Prove the union bound which states that for any events \( A_1,A_2,\ldots,A_M \) (not necessarily mutually exclusive),

\( Pr\left(\bigcup_{i=1}^{M}\right)\leq\sum_{i=1}^{M}Pr(A_{i}) \)

Solution:  We shall prove this by induction. For \(k=1\) this reduces to
\(Pr(A_{1})\leq Pr(A_{1})\)
which is obviously true.For \(k=2\) we have
\( Pr(A_{1}\cup A_{2})=Pr(A_{1})+Pr(A_{2})-Pr(A_{1}\cap A_{2})\)
by the axioms of probability.
\( \Rightarrow Pr(A_{1}\cup A_{2})\leq Pr(A_{1})+Pr(A_{2}) \)
The equality holding when the events are mutually exclusive. Assume that the propostion is true for \(M=k\). Then we have
\( Pr\left(\bigcup_{i=1}^{k}A_{i}\right)\leq\sum_{i=1}^{k}Pr(A_{i}) \)
We shall prove that this is true for \(M=k+1\). Let  \(B=\bigcup_{i=1}^{k}A_{i}\)
Then the following holds
\begin{eqnarray}
Pr(B)\leq\sum_{i=1}^{k}Pr(A_{i})\label{eqP4_1}
\end{eqnarray}
Since the proposition is true for \(M=2\)
\begin{eqnarray}
Pr(B\cup A_{k+1})\leq Pr(B)+Pr(A_{k+1})\label{eqP4_2}
\end{eqnarray}
Using \( (\eqref{eqP4_1}) \) in (\( \eqref{eqP4_2} \)) we have
\(Pr(B\cup A_{k+1})\leq\sum_{i=1}^{k}Pr(A_{i})+Pr(A_{k+1})\)
\(Pr(\bigcup_{i=1}^{k+1}A_{i})\leq\sum_{i=1}^{k}Pr(A_{i})+Pr(A_{k+1})\)
\(Pr(\bigcup_{i=1}^{k+1}A_{i})\leq\sum_{i=1}^{k+1}Pr(A_{i})\)
Thus the proposition is true for \(M=k+1\) and by the principle of induction it is true for all finite \(M\).