\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln10.pdf}
{Week 10 Notes}}
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%Topics: Random Variables and Distributions; no expectation

%\hidesolutions         
%\showsolutions

\begin{document}
\problemset{10}

% SOURCE:  Probability-RandomVariables.tex in problemrepository
% Prepared by Eric Ho

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
%This problem is about Independence 

\begin{problem}

Let $X$ and $Y$ be the outcomes of successive rolls of a six-sided die.
Assume that the die is fair and the two rolls are independent.  Now
define the following random variables:
\begin{itemize}
\item $A$ is the indicator random variable for the event that $X$ is even,

\item $B$ is the indicator random variable for the event that $Y$ is even,

\item $C \eqdef f(X)$, and

\item $D \eqdef f(Y)$,
\end{itemize}
where $f$ is a function on the outcome of a die:
\[
f(X) \eqdef \left\{ \begin{array}{cl}
        1 & \mbox{if $X=1$ or 2},\\
        2 & \mbox{if $X=3$ or 4}, \\
        3 & \mbox{if $X=5$ or 6}.
\end{array} \right.
\]
Equivalently,
\[
f(X) \eqdef \ceil{\frac{X}{2}}.
\] 

\begin{problemparts}

\problempart 

Prove that $A,B,C,D$ are pairwise independent. 

\solution{Since $X$ and $Y$ are independent, we immediately know that $A$
is independent of $B$, $C$ is independent of $D$, $A$ is independent of
$D$, and $B$ is independent of $C$.

To show $A$ and $C$ are independent, note that the $\pr{C=i}$ is 1/3 for
$1 \le i \le 3$.  Also, $\prcond{C=i}{A=1}$ is 1/3 because, given that
$A=1$, $X$ equals one of 2, 4, or 6 with equal probability, so $C=f(X)$ is
equally likely to be 1, 2 or 3.  So
\[
\prcond{C=i}{A=1} = \pr{C=i}.
\]
A similar argument shows that
\[
\prcond{C=i}{A=0} = \pr{C=i}.
\]
Therefore $A$ and $C$ are independent.  The same logic applies to $B$ and
$D$.}

\problempart
Prove that $A+B$ and $C+D$ are independent. (Hint: You only need to cover a few
general cases.  Do not iterate through every single case).

\solution{

Consider the case $(A+B=0, C+D=2)$.

\begin{eqnarray*}
\pr{A+B=0} & = & \pr{A=0 \land B=0}  =  \frac{1}{2} \cdot \frac{1}{2} =  \frac{1}{4},  \\
\pr{C+D=2} & = & \pr{C=1 \land D=1}  = \frac{1}{3} \cdot \frac{1}{3} = \frac{1}{9}, \\
\pr{A+B=0 \land C+D=2} & = & \pr{X=1 \land Y=1} \\
			     & = & \pr{X=1} \cdot \pr{Y=1} \\
			     & = & \frac{1}{6}\cdot\frac{1}{6}\\
		           & = & \frac{1}{36}  = (\frac{1}{4})(\frac{1}{9}). \\
\end{eqnarray*}

Therefore
\[
\pr{A+B=0 \land C+D=2} = \pr{A+B=0}\cdot\pr{C+D=2}.
\]

By similiar arguments, independence holds for other cases of $A+B$ and $C+D$.  
For example, consider the case $(A+B=1, C+D=4)$.

\begin{eqnarray*}
\pr{A+B=1} & = & \pr{A=0 \land B=1}+\pr{A=1 \land B=0} =  \frac{1}{4}+\frac{1}{4} =  \frac{1}{2},  \\
\pr{C+D=4} & = & \pr{C=1 \land D=3}+\pr{C=3 \land D=1}+\pr{C=2 \land D=2} = 3\cdot\frac{1}{9} = \frac{1}{3}, \\
\pr{A+B=1 \land C+D=4} & = & \pr{X=1 \land Y=6}+ \pr{X=5 \land Y=2}+\pr{X=3 \land Y=4} + \\
		           & = & \pr{X=2 \land Y=5}+ \pr{X=6 \land Y=1}+\pr{X=4 \land Y=3}\\
	                 & = & 6\cdot\frac{1}{36} = \frac{1}{6} = (\frac{1}{2})(\frac{1}{3}).\\
\end{eqnarray*}

Therefore
\[
\pr{A+B=1 \land C+D=4} = \pr{A+B=1}\cdot\pr{C+D=4}.
\]

In conclusion, $A+B$ is independent of $C+D$.}

\problempart 
Let $A$, $B$ be independent fair bits, let $C \eqdef A \oplus B$, and let $D
\eqdef 0$.  Verify that $A,B,C,D$ are pairwise independent but $A+B$ is not
independent of $C+D$. 

\solution{

We are given that $A$ and $B$ are independent.  $D$ is independent of $A$,$B$,$C$
because it is a constant. $A$ is independent of $C$ since $\prcond{A}{C} = \pr{A}\cdot\pr{C}
=\frac{1}{2}$.  The same logic applies to show that $B$ is independent of $C$.  
Therefore $A,B,C,D$ are pairwise independent. 

$\prcond{A+B=1}{C+D=1} = 1$ since it implies $C=1$ and $A \oplus B = 1$. 
However $\pr{A+B=1} = \frac{1}{2} \neq \prcond{A+B=1}{C+D=1}$.  Therefore 
$A+B$ is not independent of $C+D$. 
}

\end{problemparts}
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
\begin{problem}
Let $B_1,\dots, B_n$ be independent Bernoulli variables, with $\pr{B_i =
1} = 1/2$ for $1 \le i \le n$.  Let $D \eqdef B_1 \oplus \cdots \oplus
B_n$ where $\oplus$ is sum mod 2.  Prove that any set of $n$ among the
$n+1$ variables $B_1,\dots, B_n, D$ are mutually independent, but all
$n+1$ are not mutually independent.

\solution{

Note that $\pr{D=1}= 1/2$ because it is the sum of the probabilities of
$2^{n}/2$ cases of $B_{1}^{(x_1)} \oplus \cdots \oplus B_{n}^{(x_n)}$ with
an even number of $x_i$'s equal to one, where $B^{1}\eqdef B$, and
$B^{-1}\eqdef \bar{B}$.  But because the $B_i$'s are mutually independent,
each case of $B_1 \oplus \cdots \oplus B_n$ has probability $2^{-n}$, so
the sum of these probabilities is $1/2$.

Also, $B_1,\dots, B_n, D$ are not mutually independent, since whether or
not each of $B_1,\dots, B_n$ is equal to one determines whether or not $D$
is equal to one.

By symmetry among the $B_i$'s, to show $n$-way independence, we need only
show that $D,B_2,\dots, B_n$ are mutually independent.  If $B_2^{(x_2)}
\oplus \dots \oplus B_n^{(x_n)}$ for $x_i = \pm 1$ is equal to one, then we
know that $D$ equals $B_1^{(\pm 1)}$.  In either case, the conditional
probability of $D$ will be the same of that of $B_1$.  But the conditional
probability of $B_1$ remains 1/2 because it is mutually independent of
$B_2,\dots,B_n$.  Hence the conditional probability of $D$ also remains
$1/2$, proving that $D$ is independent of $B_2,\dots, B_n$.}

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
%Eric Ho's problem

\begin{problem}
Theory Pig has invented a random number generator using a bunch of red
balls, a bunch of green balls, and a bin.  This is how it works.

Initially, there is a red ball and a green ball in the bin.  Theory pig
randomly removes one ball from the bin, and then puts back into the bin
two balls of the same color as the one removed.  Theory pig repeats this
process until there are exactly $n$ balls in the bin.  Define the random
variable
\[
R_n \eqdef \text{  the number of red balls in the bin at the end.}
\]

Theory Pig observes that $R_n$ is a random variable taking integer values
between 1 and $n-1$.  He claims that $R$ has a uniform distribution.
Prove that he's right.

\solution{

By induction on $n \ge 2$, with induction hypothesis
\[
P(n) \eqdef R_n \text{ has a uniform distribution.}
\]

\textbf{Base case} ($n=2$): $R_2$ only takes the value 1, so is uniform on the
integers from 1 to $2-1$, as required.

\textbf{Inductive step}: Assume the distribution for $n$ balls is uniform.
We need to show that when we add the $(n+1)$st ball into the bin, the
distribution is still uniform.

Assume we have $j$ red balls at the end where $1 \le j \le n$.  This is
possible either when we add a green ball to a bin with $j$ red balls, or
when we add a red ball to a bin with $j-1$ red balls.  From inductive
hypothesis, each outcome in the bin with $n$ balls have a $1/(n-1)$
probability.  The chance that we add a green ball to a bin with $j$ red
balls is $(n-j)/n$, whereas the chance that we add a red ball to a bin
with $j-1$ red balls is $(j-1)/n$. The total is therefore:
\[
(\frac{1}{n-1})(\frac{n-j}{n}) + (\frac{1}{n-1})(\frac{j-1}{n}) =
(\frac{1}{n-1})(\frac{n-1}{n}) = \frac{1}{n}.
\]

Because probability of each outcome is the same, the distribution is uniform. 
}
\end{problem}

\end{document}                            


