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

%\newcommand{\solution}[1]{}
%\pset{10}{November 17, 1998}{Start of class on November 24, 1998}

\newcommand{\solution}[1]{\bigskip #1}
\psol{10}{December 4, 1998}

\newcommand{\xor}{\text{\ XOR\ }}

% \centerline{\bf Read sections 4.4 and 4.5 in Rosen.}

\begin{problems}

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

\problem {\bf (15 points)} Compute the probabilities of the following
three events and determine which one is most likely.  Assume that the
dice are fair, 6-sided, and mutually independent.

\begin{problemparts}
\problempart Rolling at least one 6 when six dice are rolled.

\solution{The probability of rolling a 6 on a particular die is
$\frac{1}{6}$.  The probability of not rolling a 6 on a particular die
is $\frac{5}{6}$, since this is the complementary event.  The
probability of not rolling a 6 on any of six dice is
$(\frac{5}{6})^6$, since the numbers rolled are mutually independent.
The probability of rolling a 6 on some die is therefore $1 -
(\frac{5}{6})^6 = 0.665\ldots$.  }

\problempart Rolling at least two 6's when twelve dice are rolled.

\solution{The probability of rolling two or more 6's is 1 minus the
probability of rolling zero or one 6's.  The probability of rolling
zero 6's is $(\frac{5}{6})^{12}$, arguing as before.  The probablity
of rolling exactly one 6 is

\[
12 \cdot \frac{1}{6} \cdot \left(\frac{5}{6}\right)^{11}
\]

since there are 12 ways to choose the die that comes up 6, the
probability of this die coming up 6 is $\frac{1}{6}$, and the
probability of the remaining dice all coming up in the range 1 to 5 is
$(\frac{5}{6})^{11}$.

Overall, the probability of rolling two or more sixes is therefore

\begin{eqnarray*}
1 - \left(\frac{5}{6}\right)^{12} -
	12 \cdot \frac{1}{6} \cdot \left(\frac{5}{6}\right)^{11}
		& = &	0.618\ldots.
\end{eqnarray*}
}

\problempart Rolling at least three 6's when eighteen dice are rolled.

\solution{
Arguing as before, the probability of rolling at least three 6's is

\begin{eqnarray*}
1	- \left(\frac{5}{6}\right)^{18}
	- 18 \cdot \frac{1}{6} \cdot \left(\frac{5}{6}\right)^{17}
	- \binom{18}{2} \cdot \left(\frac{1}{6}\right)^2 \cdot
		\left(\frac{5}{6}\right)^{16}
	& = &	0.597\ldots.
\end{eqnarray*}
}

\end{problemparts}

\solution{The first event is most likely.}

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

\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}

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

\problem {\bf (20 points)} 6.042 TA Alex Duran is teaching Theory Pig
a fun new game.  Theory Pig is very excited because he finally has a
friend who will ``play nice''.  Here is how the game works.  Alex
repeatedly flips a fair coin.  If the sequence $HTT$ comes up on three
consecutive throws, then the game is over and Theory Pig wins.
However, if the sequence $HHT$ comes up on three consecutive throws,
then the game is over and Alex wins.  Though the game seems completely
fair, Theory Pig is still a slightly suspicious of Alex because of an
earlier duct tape incident.

Find the probability that Theory Pig wins the game; that is, find the
probability that the sequence $HTT$ appears before the sequence $HHT$
in a sequence of fair coin tosses.

\solution{Let $p$ be the probability that $HTT$ appears before $HHT$.
For the first two flips, the sequences $HH$, $HT$, $TH$, and $TT$ are
equally likely.  Let $p_{xy}$ be the probability that the sequence
$HTT$ appears before the sequence $HHT$, given that the two most
recent flips were $x$ and $y$.  Therefore, we have:

\begin{eqnarray*}
p	& = &	\frac{1}{4}(p_{HH} + p_{HT} + p_{TH} + p_{TT})
\end{eqnarray*}

We can interrelate the four variable on the right side of this
equation by considering the outcome of the next flip.  For example,
suppose the last two flips were $HT$.  With probability $\frac{1}{2}$,
the next flip is a $T$.  Conditioned on this sequence of flips, $HTT$
appears before $HHT$ with probability 1.  On the other hand, with
probability $\frac{1}{2}$, the next flip is $H$.  In this case, $HTT$
appears before $HHT$ with probability $p_{TH}$, since the last two
flips were $TH$.  This reasoning gives the equation $p_{HT} =
\frac{1}{2} + \frac{1}{2} p_{TH}$.  By similar arguments, we obtain
the following system of linear equations.

\begin{eqnarray*}
p_{HH}	& = &	\frac{1}{2} \cdot 0 + \frac{1}{2} \cdot p_{HH} \\
p_{HT}	& = &	\frac{1}{2} \cdot 1 + \frac{1}{2} \cdot p_{TH} \\
p_{TH}	& = &	\frac{1}{2} \cdot p_{HT} + \frac{1}{2} \cdot p_{HH} \\
p_{TT}	& = &	\frac{1}{2} \cdot p_{TT} + \frac{1}{2} \cdot p_{TH}
\end{eqnarray*}

The solution to this system is $p_{HH} = 0$, $p_{TH} = \frac{2}{3}$,
$p_{TH} = \frac{1}{3}$, and $p_{TT} = \frac{2}{3}$.  Substituting
these four values into the first equation gives $p = \frac{1}{3}$ for
Theory Pig's chance of winning the game.

There are at least two alternative approaches.  First, one could find
the set of all winning outcomes for one player and sum the
probabilites of these outcomes.  Second, one could find the sets of
winning outcomes for both players and show that one has twice the
probability of the other.
}

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

\problem {\bf (10 points)} The 6.042 staff received the following
comment about the midterm exam.

\begin{verbatim}
From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: midterm exam

Thank you for announcing our state military secrets on your midterm
exam.

Well, you might as well know that each of our ferocious Tostitomatics
has a million components.  True, each component has a 50% chance of
failing during the arduous flight from Xoros 19 to Earth.  However,
failures occur mutually independently, and only 51% of the components
must remain functional for a Tostitomatic to survive the journey.

Clearly the number of component failures on a typical Tostitomatic
will be right around 50%--- maybe a bit more, maybe a little less.
Since the number of compoments that must remain functional is also
very close to 50%, obviously about half of our massively armed
Tostitomatics will entering earth orbit shortly.  Won't that be fun!

\Grzzwk
\end{verbatim}

Give a good estimate of the probability that a Tostitomatic survives
the journey.

\solution{A Tostitomatic survives the journey if at most 49\% of the
components fail.  This is equal to $F_{1000000, \frac{1}{2}}(0.49n)$, where
$F$ is the cumulative distribution function for the binomial
distribution.  We use the following bound and approximation:

\begin{eqnarray*}
F_{n, p}(\alpha n)
	& \leq &	\frac{1 - \alpha}{1 - \frac{\alpha}{p}}
				\cdot f_{n, p}(\alpha n)
\\
f_{n, p}(\alpha n)	& \approx &
\frac{2^{\left(
	\alpha \log_2\left(\frac{p}{\alpha}\right) +
	(1 - \alpha) \log_2 \left(\frac{1-p}{1-\alpha}\right)
	\right) \cdot n}}
	{\sqrt{2 \pi \alpha (1 - \alpha) n}}
\end{eqnarray*}

By substitution, the probability that a Tostitomatic survives the
journey is about $2.78 \cdot 10^{-89}$.}

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

\end{problems} \end{document}
