\problemdata
{random variable}
{f01 ps11}

% source: Spring 1999, pset10, prob 6
\begin{problem}

A {\em fair bit} is a random variable taking only the values zero and one,
each with probability $1/2$.  It turns out that from a few \emph{mutually}
independent fair bits, we can create many more \emph{pair-wise}
independent fair bits.  However we cannot create a larger set of mutually
independent fair bits.

\begin{problemparts}

\probelmpart Prove that two fair bits $X$ and $Y$ are independent if and
only if $X\oplus Y$ (xor of $X$ and $Y$) is a fair bit. The xor of two
bits is $0$ if the bits are the same and $1$ if they are different.

\solution{``only if'' direction is immediate.  Now we show why ``if'' 
direction is true. From the fact that $X$ and $Y$ are fair bits, we have 
\begin{eqnarray*}
\prob{X=0\text{ and }Y=0}+\prob{X=1\text{ and }Y=0} & =& \prob{Y=0}\\
                                                    & =& \frac{1}{2}.
\end{eqnarray*}
Also from the condition that $X\oplus Y$ is a fair bit, we have
\begin{eqnarray*}
\prob{X=0\text{ and }Y=0}+\prob{X=1\text{ and }Y=1}  =\frac{1}{2}.
\end{eqnarray*}
It follows that $\prob{X=1\text{ and }Y=0}=\prob{X=1\text{ and }Y=1}$. Since 
\begin{eqnarray*}
\prob{X=1\text{ and }Y=0}+\prob{X=1\text{ and }Y=1} & = & \prob{X=1}\\
                                                    & = &\frac{1}{2},
\end{eqnarray*}
it must be true that 
 $\prob{X=1\text{ and }Y=0}=\prob{X=1\text{ and }Y=1}=\frac{1}{4}$. 
Using the same argument, we can show that  
       $\prob{X=0\text{ and }Y=0}=\prob{X=0\text{ and }Y=1}=\frac{1}{4}$.
From here it is easy to see that  $X$ and $Y$ are independent.
}



\problempart Consider three mutually independent fair bits $X$, $Y$, and
$Z$, and consider the following seven random variables: $X$, $Y$, $Z$,
$X \oplus Y$, $X \oplus Z$, $Y \oplus Z$, $X \oplus Y \oplus Z$.  Give
yes/no answers to the following questions (no proof required):

\begin{enumerate}
\item
Are these variables fair bits?
\item
Are they pair-wise independent?
\item
Are they mutually independent?
\end{enumerate}
\solution{yes, yes, no.}

\problempart Now, given $n$ mutually independent fair bits $X_1,...,X_n$,
construct $(2^n\!-\!1)$ pair-wise independent fair bits, and prove
that your construction works.

\solution{For every binary string $b\in\{0,1\}^n\text{ and }b\neq(00...0)$,
define $Y_{b_1b_2...b_n}= \oplus_{b_i=1}X_i$.  By induction, it is easy to show
that $Y$ is a random unbiased bit. From the fact that $X\oplus X=0\text{ and }
0\oplus X=X$, it follows that for every $b\neq{b'}$,
$Y_b \oplus Y_{b'}$ is also an unbiased random bit, and hence $Y_b$ and
$Y_{b'}$ are independent. Therefore, this construction gives $(2^n\!-\!1)$ 
pair-wise independent fair bits.}

\problempart Prove that there is no construction which given $n$ mutually
independent fair bits can create $n\!+\!1$ mutually independent fair
bits.  In other words, show that there is no function $f$ mapping $n$
mutually independent fair bits to $n\!+\!1$ mutually independent fair
bits.  \\ {\it Hint: Show it first for $n=2$ and then try to
generalize your argument.}

\solution{ 
% This was given in fall 97 with $n=2$.
%
Let us first consider the case for $n=2$. Assume that there exists such a 
 function that takes as input two independent fair bits 
 $( X,Y )$ and output three mutually independent fair bits $(U,V,W)$.
Since there are four possible values of the input $(X,Y)$, at most there are 
four values of the output $(U,V,W)$. Therefore the probablity for each 
possible output value is at least 
$\frac{1}{4}$ rather than $\frac{1}{8}$, which contradicts the 
assumption that $U$, $V$ and $W$ are mutually independent.

For any $n$, assume for the purpose of contradiction that such a function 
exists. The event that all input bits are equal to zero occurs with
probability $\frac{1}{2^n}$.  In this event, the $n+1$ output bits
take on some values.  Since there are at most $2^n$ possible values of the 
output, this implies that the $n+1$ output bits take on
these values with probability at least $\frac{1}{2^n}$ and not
$\frac{1}{2^{n+1}}$, which contradicts the assumption that the $n+1$
output bits are unbiased and mutually independent.}

\end{problemparts}
\end{problem}
