
\problemdata     
{S01-PS9-5}           
{probability-independence}              
{} 		
{F00-PS10, S01-PS9}
{S01 Karger}


\begin{problem}




Let $A,B,C$ be events of some experiment.  For each of the following
statements, prove it if it is true or give a counterexample if it is
false:

\bparts

\ppart If $C$ is independent of $A$, and $C$ is independent of $B$, then
$C$ is independent of $A \union B$.

\solution{
\medskip\textbf{Solution:}

The statement is false.  For example, let $A$ and $B$ be unbiased
independent bits, \ie $A$ and~$B$ are independent events such that
$\Pr(A) = \Pr(B) = 1/2$ and let $C = A \oplus B$, \ie an event which
occurs iff exactly one of $A$ and~$B$ occurs. Then $C$ is independent
from both $A$ and $B$, but it is not independent from $A \cup B$, the
latter being an event occurring when either $A$ or~$B$ occurs. For,
\begin{gather*}
  \Pr(C \mid A) = \frac{\Pr(C \intersect A)}{\Pr(A)}
  = \frac{1/4}{1/2} = \frac{1}{2}\,, \\
  \Pr(C \mid B) = \frac{\Pr(C \intersect B)}{\Pr(B)}
  = \frac{1/4}{1/2} = \frac{1}{2}\,.
\end{gather*}
However,
\begin{displaymath}
  \Pr(C \mid (A \union B))
  = \frac{\Pr(C \intersect (A \union B))}{\Pr(A \union B)}\,.
\end{displaymath}
Obviously, $\Pr(A \union B) = 1 - \Pr(\bar{A} \intersect \bar{B}) =
3/4$. Furthermore
\begin{displaymath}
  \Pr(C \intersect (A \union B))
  =
  \Pr((C \intersect A) \union (C \intersect B))
  =
  \Pr(C \intersect A) + \Pr(C \intersect B) - 
  \Pr(A \intersect B \intersect C)
  =
  \frac{1}{4} + \frac{1}{4} - 0
  =
  \frac{1}{2}\,,
\end{displaymath}
which implies that
\begin{displaymath}
  \Pr(C \mid (A \union B)) = \frac{1/2}{3/4} = \frac{2}{3}\,.
\end{displaymath}
For a more pictorial description, consider Figure \ref{counterexample}.

\graphicspath{{/toc/a/class/6.042/spring02/freshRepository/figures/}}

\begin{figure}
  \begin{center}
    \includegraphics[height=4cm,keepaspectratio=true]{ps9-counterexample}
    \caption{A counterexample for 5a}
    \label{counterexample}
  \end{center}
\end{figure}

}

\ppart If $C$ is independent of $A$, and $C$ is independent of $B$, and
$C$ is independent of $A\cap{B}$, then $C$ is independent of $A\cup{B}$.

\solution{ 
The statement is true. Now let's prove it.
From what we are given, we know that \[
\Pr[C]=\Pr[C|A]=\Pr[C|B]=\Pr[C|A\intersect B]=\frac{\Pr[C\intersect A]}{\Pr[A]}=\frac{\Pr[C\intersect B]}{\Pr[B]}=\frac{\Pr[C\intersect(A\intersect B)]}{\Pr[A\intersect B]}
\]

We want to prove that $C$ is independent of $A\cup{B}$, that is
\[
\Pr[C]=\Pr[C|A\union B]=\frac{\Pr[C\intersect(A\union B)]}{\Pr[A\union B]}
\]
We observe that the denominator $\Pr[A\union B]$ looks suspiciously ``related'' to the denominators of the last 3 fractions above. We recall from high school that if $\frac{a}{b}=\frac{c}{d}=\frac{e}{f}\ldots$ then $\frac{a}{b}=\frac{c}{d}=\frac{e}{f}\ldots =\frac{a+c+e+\ldots}{b+d+f+\ldots}$. In other words, if we have a bunch of equal fractions, we can add all the numerators together and all the denominators together, and we still get the same fraction. Applying this to the first relation above we get:
\[
\Pr[C]=\frac{\Pr[C\intersect A]}{\Pr[A]}=\frac{\Pr[C\intersect B]}{\Pr[B]}=\frac{-\Pr[C\intersect(A\intersect B)]}{-\Pr[A\intersect B]}=\frac{\Pr[C\intersect A]+\Pr[C\intersect B]-\Pr[C\intersect(A\intersect B)]}{\Pr[A]+\Pr[B]-\Pr[A\intersect B]}
\]
Well, we observe that the denominator is just $\Pr[A\union B]$, and the numerator, after some manipulation, is indeed $C\intersect(A\union B)$. Therefore, we have just proven that
\[
\Pr[C]=\frac{\Pr[C\intersect A]+\Pr[C\intersect B]-\Pr[C\intersect(A\intersect B)]}{\Pr[A]+\Pr[B]-\Pr[A\intersect B]}=\frac{\Pr[C\intersect(A\union B)]}{\Pr[A\union B]}=\Pr[C|A\union B]
\]
Therefore, $C$ is independent of $A\cup{B}$.


}
\eparts

\end{problem}
