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:
[latex]Pr\left(A\cup B\right) = Pr\left(A\right)+Pr\left(B\right)-Pr\left(A\cap B\right)[/latex]
Solution: First, note that the sets [latex]A\cup B[/latex] and [latex]B[/latex] can be rewritten as
[latex]A\cup B=\{A\cup B\}\cap\{\overline{B}\cup B\}=\{A\cap\overline{B}\}\cup B[/latex]
[latex]B=B\cap\{A\cup\overline{A}\}=\{A\cap B\}\cup\{\overline{A}\cap B\}.[/latex]
Hence, [latex]A\cup B[/latex] can be expressed as the union of three mutually exclusive sets.
[latex]A\cup B=\{\overline{B}\cap A\}\cup\{A\cap B\}\cup\{\overline{A}\cap B\}[/latex]
Next, rewrite [latex]\overline{B}\cap A[/latex] as
[latex] \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}\}[/latex]
Likewise, [latex]\overline{A}\cap B=B\cap\{\overline{A\cap B}\}[/latex]. Therefore [latex]A\cup B[/latex] can be rewritten as the following union of three mutually exclusive sets:
[latex]A\cup B=\{A\cap(\overline{A\cap B})\}\cup\{A\cap B\}\cup\{B\cap(\overline{A\cap B})\}[/latex]
Hence
[latex]\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*}[/latex]
Next, write A as the union of the following two mutually exclusive sets
[latex]A=\{A\cap\{\overline{A\cap B}\}\}\cup\{A\cap B\}[/latex]
Hence,
[latex]Pr\left(A\right)=Pr\left(A\cap\{\overline{A\cap B}\}\right)+Pr\left(A\cap B\right)[/latex]
and
[latex]Pr\left(A\cap\{\overline{A\cap B}\}\right)=Pr\left(A\right)-Pr\left(A\cap B\right).[/latex]
Likewise,
[latex]Pr\left(B\cap\{\overline{A\cap B}\}\right)=Pr\left(B\right)-Pr\left(A\cap B\right).[/latex]
Finally,
[latex]\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*}[/latex]
Problem-2: Show that the Problem-1 can be generalized upto three events:
[latex] 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) [/latex]
Solution:
[latex]\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*}[/latex]
Problem-3: Prove that if [latex]A \subset B \; \text{then} \; Pr(A) \leq Pr(B)[/latex]
Solution: Since [latex]A\subset B[/latex] and [latex]A\cap B=A[/latex], [latex]B=A\cup\{B\cap\overline{A}\}[/latex].
Since [latex]A[/latex] and [latex]B\cap\overline{A}[/latex] are mutually exclusive, we have
[latex] \begin{eqnarray}
Pr(B)=Pr(A)+Pr(B\cap\overline{A})\ .\label{eq1}
\end{eqnarray} [/latex]
Hence by (\eqref{eq1}) and considering [latex]Pr(B\cap\overline{A})\ge0[/latex], [latex]Pr(A)\le Pr(B)[/latex].
Problem-4: Prove the union bound which states that for any events [latex] A_1,A_2,\ldots,A_M [/latex] (not necessarily mutually exclusive),
[latex] Pr\left(\bigcup_{i=1}^{M}\right)\leq\sum_{i=1}^{M}Pr(A_{i}) [/latex]
Solution: We shall prove this by induction. For [latex]k=1[/latex] this reduces to
[latex]Pr(A_{1})\leq Pr(A_{1})[/latex]
which is obviously true.For [latex]k=2[/latex] we have
[latex] Pr(A_{1}\cup A_{2})=Pr(A_{1})+Pr(A_{2})-Pr(A_{1}\cap A_{2})[/latex]
by the axioms of probability.
[latex] \Rightarrow Pr(A_{1}\cup A_{2})\leq Pr(A_{1})+Pr(A_{2}) [/latex]
The equality holding when the events are mutually exclusive. Assume that the propostion is true for [latex]M=k[/latex]. Then we have
[latex] Pr\left(\bigcup_{i=1}^{k}A_{i}\right)\leq\sum_{i=1}^{k}Pr(A_{i}) [/latex]
We shall prove that this is true for [latex]M=k+1[/latex]. Let [latex]B=\bigcup_{i=1}^{k}A_{i}[/latex]
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 [latex]M=2[/latex]
\begin{eqnarray}
Pr(B\cup A_{k+1})\leq Pr(B)+Pr(A_{k+1})\label{eqP4_2}
\end{eqnarray}
Using [latex] (\eqref{eqP4_1}) [/latex] in ([latex] \eqref{eqP4_2} [/latex]) we have
[latex]Pr(B\cup A_{k+1})\leq\sum_{i=1}^{k}Pr(A_{i})+Pr(A_{k+1})[/latex]
[latex]Pr(\bigcup_{i=1}^{k+1}A_{i})\leq\sum_{i=1}^{k}Pr(A_{i})+Pr(A_{k+1})[/latex]
[latex]Pr(\bigcup_{i=1}^{k+1}A_{i})\leq\sum_{i=1}^{k+1}Pr(A_{i})[/latex]
Thus the proposition is true for [latex]M=k+1[/latex] and by the principle of induction it is true for all finite [latex]M[/latex].