\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 10   *
%**************


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} Let random variables $X$ and $Y$ be the
outcomes of two dice rolls.  Assume that the dice are fair, 6-sided,
and independent.  Each problem part below lists two random variables
derived from $X$ and $Y$.  State whether or not these two random
variables are independent and briefly sketch a justification for your
answer.

\begin{problemparts}
\problempart $X$ and $Y ^ 2$

\solution{
These random variables are independent.  For all $x$, $y$,

\begin{eqnarray*}
\Pr(X = x \cap Y^2 = y)
	& = &	\Pr(X = x \cap Y = \sqrt{y}) \\
	& = &	\Pr(X = x) \cdot \Pr(Y = \sqrt{y}) \\
	& = &	\Pr(X = x) \cdot \Pr(Y^2 = y)
\end{eqnarray*}

The second equation uses the independence of $X$ and $Y$.
}

\problempart $X + Y$ and $X - Y$

\solution{
These random variables are not independent.  For example:

\begin{eqnarray*}
\Pr(X + Y = 2)	& = &	\frac{1}{36} \\
\Pr(X - Y = 0)	& = &	\frac{1}{6} \\
\Pr(X + Y = 2 \cap X - Y = 0)
		& = &	\frac{1}{36} \\
		& \neq &	\frac{1}{36} \cdot \frac{1}{6}
\end{eqnarray*}
}

\problempart $\lfloor\frac{X-1}{2}\rfloor +
\lfloor\frac{Y-1}{2}\rfloor$ and $(X \bmod 2) + (Y \bmod 2)$

\solution{These random variables are independent.  The quantities
$\lfloor\frac{X-1}{2}\rfloor$ and $(X \bmod 2)$ are independent, and
so are the analogous expressions involving $Y$.

\begin{eqnarray*}
\Pr\left(\left\lfloor\frac{X-1}{2}\right\rfloor = a\right)
	& = &	\frac{1}{3} \quad \quad a \in \{0, 1, 2\} \\
\Pr\left(X \bmod 2 = b\right)	& = &	\frac{1}{2}
	\quad \quad b \in \{0, 1 \} \\
\Pr\left(\left\lfloor\frac{X-1}{2}\right\rfloor = a
		\ \cap \ X \bmod 2 = b\right)
	& = &	\frac{1}{6} \quad \quad a \in \{0, 1, 2\}, b \in \{0, 1 \} \\
	& = &	\frac{1}{3} \cdot \frac{1}{2}
\end{eqnarray*}


Thus, the above expressions involve four mutually independent random
variables; two are summed in the first expression and two are summed
in the second.  Consequently, the two expressions are independent.
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} Let $S$ and $T$ be independent random
variables with a countable range $R$.  Let $g$ be a function with
domain and range $R$.  Prove that $S$ and $g(T)$ are independent.

\solution{
We must prove that for all $x, y \in R$,

\begin{eqnarray*}
\Pr(S = x \cap g(T) = y)
	& = &	\Pr(S = x) \cdot \Pr(g(T) = y).
\end{eqnarray*}

Let $g^{-1}(y)$ be the set of all values that the function $g$ maps to
$y$.  Then the event that $g(T) = y$ is identical to the event that $T
\in g^{-1}(y)$.

\begin{eqnarray*}
\Pr\left(S = x \ \cap \ g(T) = y\right)
	& = &	\Pr\left(S = x \ \cap \ T \in g^{-1}(y)\right) \\
	& = &	\Pr\left(S = x \ \cap \ 
			\left(\bigcup_{z \in g^{-1}(y)} T = z \right)\right) \\
	& = &	\Pr\left(\bigcup_{z \in g^{-1}(y)} \left(
			S = x \ \cap \ T = z \right) \right) \\
	& = &	\sum_{z \in g^{-1}(y)} \Pr\left(S = x \ \cap \ T = z \right) \\
	& = &	\sum_{z \in g^{-1}(y)} \Pr(S = x) \cdot \Pr(T = z) \\
	& = &	\Pr(S = x) \cdot \sum_{z \in g^{-1}(y)} \Pr(T = z) \\
	& = &	\Pr(S = x) \cdot \Pr(T \in g^{-1}(y)) \\
	& = &	\Pr(S = x) \cdot \Pr(g(T) = y)
\end{eqnarray*}

The third step uses the fact that set intersection distributes over
set union.  The independence of $S$ and $T$ is used in the fifth
step.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (20 points)} In this problem, we consider various
approaches to preserving and magnifying randomness.

A {\em random bit} is a random variable taking on only the values 0
and 1.  An {\em unbiased random bit} takes on the values 0 and 1 with
equal probability.  Let $x$ and $y$ be bits.  The expression $x \xor
y$ is called the {\em exclusive-or} of $x$ and $y$.  This expression
is equal to 0 if $x = y$ and equal to $1$ if $x \neq y$.

\begin{problemparts}

\problempart Prove that the $\xor$ of an unbiased random bit and an
arbitrarily biased random bit is an unbiased random bit.  Assume that
the two bits are independent.

\solution{Let $x$ be an unbiased random bit, and let $y$ be random bit
that is equal to 0 with probability $p$.

\begin{eqnarray*}
\Pr(x \xor y = 0)
	& = &	\Pr(x = 0 \cap y = 0) + \Pr(x = 1 \cap y = 1) \\
	& = &	\Pr(x = 0) \cdot \Pr(y = 0) +
		\Pr(x = 1) \cdot \Pr(y = 1) \\
	& = &	\frac{1}{2} \cdot p + \frac{1}{2} \cdot (1 - p) \\
	& = &	\frac{1}{2}
\end{eqnarray*}
}

\problempart Prove that there is no function mapping two unbiased,
independent random bits to three unbiased, mutually-independent random
bits.

\solution{Assume for the purpose of contradiction that such a function
exists.  The event that both input bits are equal to zero occurs with
probability $\frac{1}{4}$.  In this event, the three output bits take
on some values.  This implies that the three output bits take on these
values with probability at least $\frac{1}{4}$ and not $\frac{1}{8}$,
which contradicts the assumption that the three output bits are
unbiased and mutually independent.}

\problempart Describe a function mapping two unbiased, independent
random bits to three unbiased, pairwise-independent random bits.  No
proof is necessary.

\solution{Let $a$ and $b$ be unbiased, independent bits.  Then $x = a$,
$y = b$, and $z = a \xor b$ are unbiased, pairwise-independent bits.}

%\problempart Describe a function mapping $n$ unbiased, mutually
%independent random bits to $2^n-1$ unbiased, pairwise-independent
%random bits.  No proof is necessary.
%
%\solution{The $2^n-1$ pairwise-independent bits are obtained by taking
%the $\xor$ of each non-empy subset of the $n$ mutually-independent
%bits.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (5 points)} Let the random variable $R$ be equal to the
number of heads that come up when four mutually independent, fair
coins are flipped.

\begin{problemparts}
\problempart Compute the probability distribution function for $R$.
That is, determine $\Pr(R = k)$ for all $k$.

\solution{
\begin{eqnarray*}
\Pr(R = 0)	& = &	\frac{1}{16} \\
\Pr(R = 1)	& = &	\frac{4}{16} \\
\Pr(R = 2)	& = &	\frac{6}{16} \\
\Pr(R = 3)	& = &	\frac{4}{16} \\
\Pr(R = 4)	& = &	\frac{1}{16}
\end{eqnarray*}
}

\problempart Compute the cumulative distribution function for $R$.
That is, find $\Pr(R \leq k)$ for all $k$.

\solution{
\begin{eqnarray*}
\Pr(R \leq 0)	& = &	\frac{1}{16} \\
\Pr(R \leq 1)	& = &	\frac{5}{16} \\
\Pr(R \leq 2)	& = &	\frac{11}{16} \\
\Pr(R \leq 3)	& = &	\frac{15}{16} \\
\Pr(R \leq 4)	& = &	\frac{16}{16}
\end{eqnarray*}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%%%%%% S99 ps10



\problem{\bf (12 points)}

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\cup B$.

\solution{The statement is false.  For example let $A$ and $B$ be
unbiased independent bits, and let $C = A \oplus B$.  Then $C$ is
independent from both $A$ and $B$, but it is not independent from $A
\cup B = A\, {\sf or}\, B$}

\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{
It is true.  To prove it, observe by the Sum Rule that
\begin{eqnarray*}
\lefteqn{\prob{x\in(C\cap(A\cup B))}}\\
& = &  \prob{x\in(C\cap(A- B))} +\prob{x\in(C\cap(B- A))} + \prob{x\in(C\cap(A\cap B))},
\end{eqnarray*}
and then that 
\[
\prob{x\in(C\cap(A - B))} + \prob{x\in(C\cap (A \cap B))}
= \prob{x \in (C\cap A)}
\]
also by the Sum rule.  Then use the fact that $C$ is independent of
both $A$ and $A \cap B$ to get that $C$ is independent from $A - B$.  And
similarly that it is independent from $B - A$.

}
\eparts


\problem {\bf (12 points)} 

Let random variables $X$ and $Y$ be the outcomes of two dice rolls.
Assume that the dice are fair, 6-sided, and independent.  Each problem
part below lists two random variables derived from $X$ and $Y$.  State
whether or not these two random variables are independent and justify
your answer.

\bparts
\ppart  $(X \bmod 3) + (Y \bmod 3)$ and $(X \bmod 2) + (Y \bmod 2)$

\solution{Independent.  $X \bmod 3$ and $X \bmod 2$ are independent,
which you can see by drawing a 3x2 table of values of $X \bmod 3$
versus values of $X \bmod 2$.  Obviously, $Y\bmod 3$ and $Y \bmod 2$
are independent as well.  Furthermore, it is true in general that if
$A$ is independent of $B$ and $A'$ is independent of $B'$ then
$f(A,B)$ is independent of $g(A',B')$ for any functions $f$ and $g$.
Here the two functions are addition over integers.}


\ppart $((X+Y)\bmod{2})$ and $((X*Y)\bmod{2})$

\solution{ These random variables are not independent.  $(X+Y\bmod 2)
= 1$ iff $X$ and $Y$ have different parity.  $(X*Y\bmod 2) =1$ iff
both $X$ and $Y$ have odd parity.  Therefore, if $(X*Y\bmod 2) =1$
then $(X+Y\bmod2)=0$, and hence the two events depend on each other.}

\eparts


\problem{\bf (12 points)}

Given a biased coin that comes up heads $2/3$ of the time and tails
$1/3$ of the time, simulate a fair coin by applying repeated flips of
the unfair coin.  In other words, design a procedure involving tosses
of the unfair coin which has two outputs, ``tail'' and ``head'', and
which outputs them with equal probability.  Your procedure should
return ``head'' or ``tail'' with probability at least
$1-(\frac{1}{2})^n$, using $O(n)$ tosses of the unfair coin, which
means that your procedure can have a tiny probability of not returning
any answer after using reasonably many tosses of the unfair coin.


\solution{ The procedure is this: Flip the unfair coin twice.  If you
get HT then output ``tail'' and if TH then output ``head''.  Otherwise
repeat.  Probability of outputting ``tail'' is equal to probability of
outputting ``head''.  Furthermore, probability of failure to output
anything at all after using $2k$ tosses is
$(\frac{2}{3}*\frac{2}{3}+\frac{1}{3}*\frac{1}{3})^k = (\frac{5}{9})^k
= (\frac{1}{2})^{ck}$ for some small $c=(\ln \frac{5}{9}/\ln
\frac{1}{2}) \approx 0.85$.}




\problem {\bf (15 points)} 

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.

\bparts

\ppart 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 (xor of two
bits is $0$ if the bits are the same and $1$ if they are different.)

\solution{``only if'' direction is immediate.  ``if'' direction is
true because if xor is unbiased than probability of that $(X,Y)$ is
$(0,0)$ or $(1,1)$ is $1/2$.  And because $X$ is unbiased, this means
that probability of each one is $1/4$.  Similarly, you get that
probability of both $(0,1)$ and $(1,0)$ is $1/4$, and hence $X$ and
$Y$ are independent.}

\ppart 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$.
Argue your answers to the following questions:

\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: all easy to check}

\ppart 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\neq(00...0)$, define
$Y_{b_1b_2...b_n}= \oplus_{b_i=1}X_i$.  It is easy to argue that each
$Y$ is a random unbiased bit, and then 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.}

\ppart 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$.
%
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.  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.}

\eparts

\noindent
{\bf Question for the curious (not graded):} Can you create $2^n$
pair-wise independent fair bits from $n$ mutually independent fair
bits?  Can you see the answer for $n=2$?

\solution{
For $n=2$, a bit variable derived from two bits is 
a function from $\{0,1\}\times\{0,1\}$ to $\{0,1\}$.
There are $2^4=16$ such functions.  Now, only $6$, i.e.
($4$ choose $2$) of them give an unbiased bit.  In fact
we can list them.  If the inputs bits are $X$ and $Y$
then the $6$ possible ``derived'' random bits are the
following:
\[
X, Y, \neg X, \neg Y, X \oplus Y, \neg(X \oplus Y)
\]
You can quickly see that no four of these can be
mutually independent.

However, I don't see how to generalize this fact to
all $n$, or even to $n=3$.
}

\problem{(\bf 15 points)}

Consider the process of tossing a sequence of $n$ independent fair
coins $X_1,X_2,\ldots,X_n$.  Let $V$ be the first time two consecutive
heads occur in the sequence, i.e. $(X_{V-1},X_V)=(H,H)$ and
$(X_{i-1},X_i)\neq (H,H)$ for all $2\leq i<V$.  If the sequence of $n$
coin tosses does not contain two consecutive heads, then we assign
$V=n+1$.

Prove that $V$ has distribution
\[\Pr(V=k) = \frac{\Fib(k-2)}{ 2^k} \ \ \ \ (2\leq k\leq n) \]
where $\Fib(k)$ is the $k$-th Fibonacci number (assume 
$\Fib(0)=\Fib(1)=1$.)

\solution{
% This problem is taken from spring 96, problem 10
%
Let's count the sequences of coin tosses of length $k$ such that the
only pair {\em HH} that occurs in the sequence is at the end. Let
$H(k)$ be the number of such sequences that start with $H$, and let
$T(k)$ be the number of such sequences that start with $T$.  Observe
that $H(2) = 1$ and $T(2) = 0$. Similarly, $H(3) = 0$ and $T(3) =
1$. Given a valid sequence {\em HS} of length $k$ that starts with
$H$, the sequence {\em THS} is also valid and starts with $T$.  Given
a valid sequence {\em TS} of length $k$ that starts with $T$, the
sequences {\em HTS} and {\em TTS} are also valid and start with $H$
and $T$ respectively. From this we deduce the recurrence relations
\begin{eqnarray*}
H(k+1) &=& T(k)\\
T(k+1) &=& H(k) + T(k){.}
\end{eqnarray*}
The total number of valid sequences of length $k$ is $T(k)+H(k)$,
hence it satisfies the following recurrence
\begin{eqnarray*}
T(k+1)+ H(k+1) &=& (T(k) + H(k)) + T(k)\\
&=& (T(k) + H(k)) + (T(k-1) + H(k-1)){.}
\end{eqnarray*}
This is the same recurrence relation that defines the Fibonacci
numbers, and with the given initial conditions we can conclude that
the total number of valid sequences of length $k$ is $\Fib(k-2)$.

Now the total number of sequences of length $n$ such that the first
pair of heads occurs after $k$-th toss is $\Fib(k-2)2^{n-k}$, since we
don't care what the coin tosses are in the last $n-k$ places.

The sample space in this problem is the set of all sequences of coin
tosses of length $n$, so its size is $2^n$. Therefore the probability
\[
P(V=k) = \frac{\Fib(k-2)2^{n-k}}{ 2^n} = \frac{\Fib(k-2)}{ 2^k}{,}
\]
as desired.
}

\noindent {\bf Question for the curious (not graded):} What is the
cumulative distribution function for $V$?  It is a similar expression
involving $\Fib(k+c_1)$ and ${2^{k+c_2}}$ for some small $c_1,c_2$.

\solution{ The equation is $\prob{V \leq k}=1-\frac{\Fib(k+1)}{2^k}$, and
you can show it by induction: The base case: $\prob{V\leq{2}}=1/4=1-3/4=
1-\frac{\Fib(3)}{2^2}$.  And the inductive case holds too.}


%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



