\documentclass[12pt,twoside]{article}
%\usepackage{amsmath}
%\usepackage{graphics}
\input{macros-course}

\begin{document}
\pset{10}{April 22, 1999}{Thursday, April 29}
%\psol{10}{March 10, 1999}

\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\newcommand{\Fib}{{\sf Fib}}
\newcommand{\ignore}[1]{}

\reading Sections 4.4 and 4.5 in Rosen and Fall 97 lectures 20, 21.

\begin{problems}


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


\problem{\bf (10 points)} 

Roll five ordinary unbiased dice.  On the first two, consider the
numbers modulo $3$, and on the other three, consider the numbers
modulo $2$.  Denote by $T$ the sum of these five numbers.

Compute the probability distribution function and the cumulative
distribution function for this random variable.

\solution{The possible values of $T$ are $0,1,2,3,4,5,6,7$, the the
distribution is 
\\
$\frac{1}{72}, \frac{5}{72}, \frac{12}{72},
\frac{18}{72}, \frac{18}{72}, \frac{12}{72}, \frac{5}{72},
\frac{1}{72}$ 
\\ 
and the cumulative distribution is 
\\
$\frac{1}{72},
\frac{6}{72}, \frac{18}{72}, \frac{36}{72}, \frac{54}{72},
\frac{66}{72}, \frac{71}{72}, \frac{72}{72}$
}


\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 you have to write out
\[
Pr[x\in(C\cap(A\cup B))] =  Pr[x\in(C\cap(A- B))]
+Pr[x\in(C\cap(B- A))] + Pr[x\in(C\cap(A\cap B))]
\]
and then note that 
\[
Pr[x\in(C\cap(A- B))] + Pr[x\in(C\cap(A\cap B))]
= Pr[x\in(C\cap A)]
\]
and then you 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 an unfair 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 (12 points)} 

A Dungeons and Dragons player rolls several dice and sums the results
to determine how many points of damage his warrior does to a
fire-breathing dragon.  If the warrior does $20$ or more points of
damage, then the dragon is slain.  If the warrior does fewer than $20$
points of damage, then the dragon survives and makes a nice pot-roast
out of the warrior.  What is the probability that the warrior survives
if:

\bparts
\ppart The player rolls two 12-sided dice.
\solution{${15}/{12^2} = 0.104$}
\ppart The player rolls three 8-sided dice.
\solution{$35/8^3 = 0.068$}
\ppart The player rolls four 6-sided dice.
\solution{$70/6^4=0.054$}
\eparts

\ignore{
Consider a variation of Dungeons and Dragons where you can choose
between different sets of dice before rolling them to determine the
points your character gets to attack some creature.  Say that you are
facing a certain $20$-point-resistant dragon, which means that to
survive this encounter you need to roll at least $20$ points of
``dragon damage'' with the set of dice you pick.  Treat this matter
seriously because if you roll less then $20$ points, the dragon
breathes fire on you and you die!
\bparts 
\ppart What is the probability of defeating the dragon using two
$12$-sided dice?
\ppart
How about using three $8$-sided dice?  
\ppart
How about four $6$-sided dice?
\eparts
}

\ignore{
\ppart Consider the following: 
\begin{itemize}
\item
If you roll the first set of dice you will get
$2*(\frac{12-1}{2}+1)=13$ points on the average.  
\item
Using the second set you will get $3*(\frac{8-1}{2}+1)=13.5$ points on
the average.  
\item
Using the third set you will get $4*(\frac{6-1}{2}+1)=14$ points.
\end{itemize}
Considering the above and your answers to parts (a)-(c), what can you
infer about the distribution of points given by these three sets of
dice?
\solution{ The mean gets slightly higher but the variance gets
smaller, and therefore there is lesser chance of hitting some fixed
upper part of the distribution.}
}


\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) = {\Fib(k-2)\over 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) = {\Fib(k-2)2^{n-k}\over 2^n} = {\Fib(k-2)\over 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 Pr$[V\leq{k}]=1-{\Fib(k+1)\over{2^k}}$, and
you can show it by induction: The base case: Pr$[V\leq{2}]=1/4=1-3/4=
1-{\Fib(3)\over{2^2}}$.  And the inductive case holds too.}


\problem{\bf (12 points)}

Lockheed-Martin is currently in the process of designing the new space
shuttle, the ``Venture Star''.  Suppose that it has $100,000$ parts
and the probability that each part will fail is $1/1000$.  Redundancy
has been designed into the spacecraft so that it will fly as long as
no more than $125$ parts fail.  The failure of each part is
independent of the failure of any other part.  Prove that the
probability that Venture Star will fly successfully is at least
$99\%$.

\solution{You have to upper bound the probability that less than
$100,000-125=99,875$ parts will be OK.  This upper bound turns out to
be slightly less than $1%$.  You take $n=100,000$,
$\alpha=99,875/100,000=.99875$ and $p=1-1/1000=.999$ (then
$\alpha<p$), and compute an upper bound for $F_{n,p}(\alpha n)$ using
Theorem 3.1 from Lecture 21 in the lecture notes.  First you should
get that $f_{n,p}(\alpha n)\approx{0.001972}.  Then $F_{n,p}(\alpha n)
\leq \frac{1-\alpha}{1-\frac{p}{\alpha}}f_{n,p}(\alpha n) \approx
4.995 * 0.001972 \approx 0.0098$.
}



\end{problems}

\end{document}
