\documentstyle[12pt,twoside]{article}

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

\begin{document}


\begin{problems}


%nikos
%PSET11 - last used Spring 99, pset 10
%LEARNING OUTCOMES:2 (evaluate elementary mathematical arguments)
%		   7 (calculate numbers of possible outcomes)
%                  8  (calculate probabilities)
%New problem added this term
\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.

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

\solnospace{``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.
}



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

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

\solnospace{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.}

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

\solnospace{ 
% 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.}

\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$?

\solnospace{
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.  If we want to use 
$\{ X, Y, \neg, \oplus\}$ to construct the new bits, then
 there are $6$, i.e.
($4$ choose $2$) ways (functions) to 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 (pair-wise) independent. 

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


%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
\problem %source: spring00 ps10
\problem %
% (Bounding tails of binomial dist)

A new fault-tolerant computer network contains 100,000 computer nodes,
and is designed to function adequately when no more than 5000
computers are down.
Suppose that the probability that any particular computer is down
is 4\%; moreover, these probabilities are independent for different
computers.

\begin{problemparts}

\problempart
Estimate the probability that exactly 5000 computers are down.

\solution{
\[
f_{100000,0.04}(5000) = 1.7264 \cdot 10^{-55}
\]
}

\problempart
Estimate the probability that the network can function adequately.

\solution{ %
  Here, we must estimate the probability that more than 95000
  computers are fault free. As a rough but high approximation, we can notice
  that the expected number of computers to be down is 4000. If we assume that
  all numbers of down computers from 5001 to 100,000 are less likely to occur
  than 5000 computers being down, we can upper bound the probability that
  more than 5000 computers are down by 
  \[
  95000 \cdot \prob{95000 \text{ computers  working}} = 95000 \cdot 1.7264 \cdot 10^{-55}
   = 1.640 \cdot 10^{-50}
  \]
  which should suggest that the probability of a functioning network is extremely high,
  greater than $1 - 1.640 \cdot 10^{-50}$.

        For a more precise bound, we can find a lower bound on the probability that
        the network can function adequately:    
  \begin{equation*}
    \prob{> 95000 \text{ computers  working}} = 
      1 - \prob{\leq 95000 \text{ computers working}}
  \end{equation*}

  An upper bound for $\prob{\leq 95000 \text{ computers working}}$ is given by:
  \begin{eqnarray*}
    F_{100000,0.96}\left(0.95 \cdot 100000\right)
    & \leq &
    \frac{1-\alpha}{1 - \frac{\alpha}{p}} f_{n,p}(\alpha \cdot n) \\
    & = &
    \frac{1-\alpha}{1 - \frac{\alpha}{p}} f_{n,(1-p)}((1-\alpha) \cdot n) \\
    & \approx & 4.8 \cdot f_{n,(1-p)}((1-\alpha) \cdot n)
%     \frac{2^{(\alpha \log_2(\frac{p}{\alpha}) + (1-\alpha)
%         \log_2(\frac{1-p}{1-\alpha})) \cdot n}}{\sqrt{2\pi \alpha
%         (1-\alpha) n}}
  \end{eqnarray*}
  Plugging in for $f_{n,(1-p)}((1-\alpha) \cdot n)$ from part a, we get:
  \begin{equation*}
    F_{100000,0.96}\left(0.95 \cdot 100000\right) \leq 8.2866 \cdot 10^{-55}
  \end{equation*}
  Thus, it follows that:
  \begin{equation*}
    \prob{> 95000 \text{ computers working}} \approx 1
  \end{equation*}
}
\end{problemparts}

\problem %source: spring00 ps10
% (Polling)

The Gallup polling service is conducting a poll to see what percentage
of Americans believe that 6-year-olds should be
given the legal right to decide where they should live.
They would like to be accurate (after all, this is a very serious
issue) to within a 2\% margin of error, with at least 98\% probability.
Estimate how many people they would need to poll to be able to make
this claim of reliability. (As in lecture, assume that they are polling
with replacement, so they may poll the same person twice).

\solution{
We can follow the form used in lecture, using the bounds shown there.
(Note that this does not tell us the \emph{minimum} number of people
we need to poll to be sure enough, just a sufficient number). Using the
general formula
\[
 \delta \leq 2 F_{n,\frac{1}{2}}((\frac{1}{2}-\epsilon) n)
\]
we have $\delta = 0.02$, $\epsilon = 0.02$, so
\begin{eqnarray*}
%%
\delta & \leq  & 2 F_{n,\frac{1}{2}}(\frac{12}{25}n)  \\
%%
 & \leq  & 
 2 \cdot \frac{1 - 0.48}{1 - \frac{0.48}{0.5}} 
   \cdot f_{n,\frac{1}{2}}(0.48n)  \\
%%
 & \leq  & 
 26 \cdot 
 \left(\frac{2^{\left( 0.48lg\left(\frac{0.5}{0.48}\right) 
         + 0.52lg\left(\frac{0.5}{0.52}\right) \right)n} }
   {\sqrt{2 \pi 0.48 \cdot 0.52 n}} 
 \right)  \\
%%
 & \leq  & 
 26 \cdot 
 \left( \frac{2^{-0.00115446 \cdot n} }
   {1.25231108 \sqrt{n}} 
 \right)  \\
\end{eqnarray*}

The easiest way to solve this is just plugging in each potential $n$
into the final equation until we find where it must be that $\delta
\leq 0.02$.  It turns out that it is sufficient to survey
approximately $3569$ people.
%
}

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

\problem %source: spring00 ps10
% (Random vars, expected value)
%[[[ New problem, from Feller Vol. 1, p. 223, prob. 8.]]]

Let $X_1$, $X_2$, and $X_3$ be three mutually independent random
variables, each having the uniform distribution, $\prob{X_i = k}$
equal to 1/3 for each of $k=1$, $k=2$, and $k=3$.
Let $M$ be another random variable giving the maximum of these three random
variables.

\begin{problemparts}
\problempart
What is the distribution of $M$?

\solution{
This can be easily hashed out by counting the possible outcomes:
\begin{eqnarray*}
M & \textrm{ is }  & 1 \textrm{ with probability } \frac{1}{27}  \\
  &  & 2 \textrm{ with probability } \frac{7}{27}  \\
  &  & 3 \textrm{ with probability } \frac{19}{27}  
\end{eqnarray*}
}

\problempart
What is the expected value of $M$?

\solution{
Directly from the above, it is:
\[
\frac{1}{27}(1) + \frac{7}{27}(2) + \frac{19}{27}(3) = \frac{8}{3}
\]
}

\problempart
Generalize to $n$ variables with possible values $1, 2, \ldots n$.

\solution{
We can solve this by examining the probabilities as follows:
\[
\prob{M \leq k} = \prob{\text{no $X_i$ is greater than $k$}}
 = \left( \frac{k}{n} \right)^n
\]
However,
\begin{eqnarray*}
\prob{M = k} & = & \prob{M \leq k} - \prob{M \leq k-1}  \\
             & = & \left( \frac{k}{n} \right)^n - \left( \frac{k-1}{n} \right)^n  \\
\end{eqnarray*}
And the expectation of $M$ becomes:
\begin{eqnarray*}
\sum_{k=1}^{n} \left[k \cdot
         \left(
             \left( \frac{k}{n} \right)^n - \left( \frac{k-1}{n} \right)^n  
         \right) \right]   & = &    
 \sum_{k=1}^{n} \left[k \cdot \left( \frac{k}{n} \right)^n \right]   -
 \sum_{k=1}^{n} \left[k \cdot \left( \frac{k-1}{n} \right)^n \right]   \\
& = &    
 \sum_{k=1}^{n} \left[k \cdot \left( \frac{k}{n} \right)^n \right]   -
 \sum_{k=0}^{n-1} \left[(k+1) \cdot \left( \frac{k}{n} \right)^n \right]   \\
& = &    
 \sum_{k=1}^{n} \left[k \cdot \left( \frac{k}{n} \right)^n \right]   -
 \sum_{k=0}^{n-1} \left[k \cdot \left( \frac{k}{n} \right)^n \right]   -
 \sum_{k=0}^{n-1} \left( \frac{k}{n} \right)^n    \\
& = &    
 n - \sum_{k=0}^{n-1} \left( \frac{k}{n} \right)^n    
\end{eqnarray*}
}
\end{problemparts}



%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)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset10 problem1 spring98
\problem{\bf [8 points]}

Show that if two positive random variables $R$ and $T$ are
independent, then $2R$ and $e^T$ are also independent.

\solution{
{\bf Solution}

\begin{eqnarray*}
\Pr((2R=r)\wedge (e^T=t)) &=& \Pr((R=r/2 )\wedge( T=\ln t))\\
&=& \Pr(R=r/2)Pr(T=\ln t)\\
&=& \Pr(2R=r)Pr(e^T=t)
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset10 problem2 spring98
\problem{\bf [12 points]}

\bparts

\ppart{\bf [6 points]}
Let $R_1$ and $R_2$ be two independent random variables.
$R_1$ takes the values $0,1$ with equal probability.
$R_2$ has the following distribution.

$\Pr(R_2=1) = 1/2$\\
$\Pr(R_2=2) = 1/4$\\
$\Pr(R_2=4) = 1/4$

Compute the distribution of $2 ^{R_1} R_2$.

\solution{
{\bf Solution}

Let $X = 2 ^{R_1} R_2$. 

$\Pr(X = 1) = \Pr(R_1 = 0 \wedge R_2 = 1) = 1/4$.\\
$\Pr(X = 2) = \Pr((R_1 = 0 \wedge R_2 = 2)
  \vee (R_1 = 1 \wedge R_2 = 1) = 3/8$.\\
$\Pr(X = 4) = \Pr((R_1 = 0 \wedge R_2 = 4)\vee(R_1 \wedge R_2=2))=1/4$.\\
$\Pr(X = 8) = \Pr(R_1=1 \wedge R_2=4) = 1/8$.\\
}

\ppart{\bf [6 points]}
Now suppose that $R_1$ and $R_2$ are no longer independent.
In particular, $R_1 = 0$ if $R_2$ is 1, and $R_1 =1$ when $R_2$ is 2 or 4.
$R_2$ has the same distribution as in part (a).

Compute the distribution of $2^{R_1} R_2$.

\solution{
{\bf Solution}

$\Pr(X = 1) = \Pr(R_2 = 1) = 1/2$.\\
$\Pr(X = 4) = \Pr(R_2 = 2) = 1/4$.\\
$\Pr(X = 8) = \Pr(R_2 = 4) = 1/4$.\\
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem3 spring98; from pset11 problem4 fall97
\problem


\bparts

\ppart Let $X$ be a random variable whose value is an observation drawn
uniformly at random from the $\set{i\in\nats \mid -n \le i \le n}$.  Let
$Y = X^2$.  Show that $X$ and $Y$ are {\em not} independent, but that
$\E[XY] = \E[X] \E[Y]$.

\textbf{Solution}:

Since $Y$ is determined by $X$, there are many cases indicating where $X$
and $Y$ are not independent, e.g., 
\[\pr{Y = 0} = 1/(2n+1),\mbox{  but } \pr{Y=0 \mid X= 0} = 1.\]

To see that $\E[XY] = \E[X] \E[Y]$, note that $\E[X] = 0$ and $\E[XY]
= \E[X^3] = 0$ since $X$ and $X^3$ are both symmetrical.

\ppart 
Show that in general for any two random variables $X$ and $Y$
that if $\E[XY] = \E[X] \E[Y]$ then $\vari{X+Y} =
\vari{X} + \vari{Y}$.  In particular, this shows that it is possible
for nonindependent variables to have variances that exhibit
linearity.

\textbf{Solution}:

We have that $\vari{X + Y} = \E[(X+Y)^2] - (\E[X+Y])^2 = \E[X^2 + 2XY +
Y^2] - (\E[X]+ \E[Y])^2 = \E[X^2] - (\E[X])^2 + \E[Y^2] - (\E[Y])^2 +
2\E[XY] - 2\E[X]\E[Y] = \vari{X} + \vari{Y}$. 

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem10 spring98; from fall 96 pset12 problem7
%\problem
%
%
%\bparts
%\ppart Let $X$ be a random variable whose value is an observation
%drawn uniformly at random from the set
%$\{-n,-n+1,\ldots,-2,-1,0,1,2,\ldots,n-1,n\}$.
%Let $Y = X^2$. Show that $X$ and $Y$ are {\em not} independent, but
%that
%$\Ex{XY} = \Ex{X} \Ex{Y}$.
%\ppart Show in general for any two random variables $X$ and $Y$
%that if $\Ex{XY} = \Ex{X} \Ex{Y}$ then $\vari{X+Y} =
%\vari{X} + \vari{Y}$.  In particular, this shows that it is possible
%for non independent variables to have variances that exhibit
%linearity.
%\ppart Let $X_1, X_2, \ldots, X_n$ be $n$ {\em pairwise} independent
%random variables.  Show that $\vari{X_1 + X_2 + \cdots + X_n} =
%\vari{X_1} + \vari{X_2} + \cdots + \vari{X_n}$.
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem14 spring98; from spring 95 pset10 problem6
\problem


\bparts
\ppart Show that if random variables $X$ and $Y$ are independent then ${\rm
Cov}(X,Y)=0$

\textbf{Solution}:

First we show that if $X$ and $Y$ are independent, then $E(XY) = E(X)E(Y)$.
\begin{eqnarray*}
E(XY) & = & \sum_{x,y} xyP(X=x \mbox{ \& } Y=y) \\
      & = & \sum_x \sum_y xyP(X=x \mbox{ \& } Y=y) \\
	  & = & \sum_x \sum_y xyP(X=x)P(Y=y) \\
	  & = & \sum_x xP(X=x)\sum_y yP(Y=y) \\
	  & = & \sum_x xP(X=x)E(Y) \\
	  & = & E(Y)\sum_x xP(X=x) \\
	  & = & E(X)E(Y)
\end{eqnarray*}
Since ${\rm Cov}(X,Y) = E(XY) - E(X)E(Y)$, ${\rm Cov}(X,Y) = 0$.

\ppart Show that having ${\rm Cov}(X,Y)=0$ does not necessarily mean that
$X$ and $Y$ are independent.

\textbf{Solution}:

Let $(X,Y)$ have joint probability given by the table below:

\begin{center}
\begin{tabular}{|c|c|c|} \hline
$X$ & $Y$ & P \\ \hline
$-1$ & $1$ & $\frac{1}{3}$ \\ \hline
$0$ & $0$ & $\frac{1}{3}$ \\ \hline
$1$ & $1$ & $\frac{1}{3}$ \\ \hline
\end{tabular}
\end{center}

Note that $X$ and $Y$ are not independent.  $P(X=1 \mbox{ \& } Y=1) =
\frac{1}{3} \neq \frac{2}{9} = P(X=1)P(Y=1)$.  But $E(X) = 0$ and $E(XY) =
0$ (since $XY=X$).  Thus ${\rm Cov}(X,Y) = 0$.


%\ppart Let $X_1,\ldots,X_n$ be random variables.  Prove that
%\[
%{\rm Var}(X_1+\ldots+X_n)=\sum_{i=1}^n {\rm Var}(X_i) + 2\sum_{i<j} {\rm Cov}(X_i,X_j)
%\]
\eparts

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000  PS 11   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem 

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{
\textbf{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{ 
\textbf{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 
%%%%%%%%%%%%%%
%END   George's problems

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

%BEGIN Tina's problems
%%%%%%%%%%%%%% FAll 99 %%%%%%%%%%%%%%
% Problem Set 11
\problem  % {\bf Random Variables based on Dice experiments}

Let $R$ and $Z$ denote random variables for two independent dice
experiments. Let $M_1 = \min(R,Z)$, and $ M_2 = R+Z$.  what is the
distribution function for $M_1$?  Are $M_1$ and $M_2$ independent random
variables?  Prove it.

\solution{
For any $x\in [1, 6]$,
\begin{align*}
\prob{M_1=x} &=
\prob{\min(R,Z)=x}\\
&= \prob{R = x~ \mbox{and}~ Z > x} + \prob{R > x~ \mbox{and}~ Z
= x} + \prob{R=Z=x}\\
&= {1/6}\cdot {\frac{6-x} {6}} + \frac{6-x}{6}\cdot {1/6} +
{1/6}\cdot {1/6}\\
&= {\frac{13-2x}{36}}.
\end{align*}

$M_1$ and $M_2$ are not independent since we have, for any $x\in [1,6]$,
\begin{align*}
\prob{M_1 = x | M_2 < x} &= 0\\
&\not= \prob{M_1 = x}
\end{align*}
}

\iffalse

\problem  % \textbf{Random variables and the Binomial Distribution}

Suppose $n\in \naturals$ and $p\in [0,1]$. Let $X$ and $Y$ be independent
random variables, both with binomial distribution $f_{n,p}$. Define
random variable $Z = X+Y$.
%\begin{problemparts}
%\ppart 

%QUERY: why the ugly algebraic proof, when there is such an obvious
%combinatorial/probabilistic-process oroof?

Using the definition of the binomial distribution and
Vandermonde's identity (theorem~4.3.5 in Rosen), prove that $Z$
has distribution $f_{2n,p}$. (You may find it easier to prove this
fact separately for the three cases $\prob{Z=z}$ when
$z\not\in[0,2n]$, $0\leq z\leq n$, and $n < z \leq 2n$)

\solution{
Clearly, $\prob{Z=z} = 0 = f_{2n,p}(z)$ for any $z\not\in [0,
2n]$.

Suppose $0\leq z \leq n$. Then
\begin{align*}
\prob{Z = z} &=
\prob{X + Y = z}
\\&= \sum_{(x,y)\in [0,n]^2: x+y=z} \prob{X=x \wedge Y=y}
\\&= \sum_{(x,y)\in [0,n]^2: x+y=z} \prob{X=x} \prob{Y=y}
%      \\&= \sum_{x=0}^z \prob{X=x} \prob{Y=z-x}
\\&= \sum_{x=0}^z f_{n,p}(x) f_{n,p}(z-x)
%      \\&= \sum_{x=0}^z \binom{n}{x} p^x (1-p)^{n-x} \cdot
%      \binom{n}{z-x} p^{z-x} (1-p)^{n-(z-x)}
\\&= p^z (1-p)^{2n-z} \sum_{x=0}^z \binom{n}{x} \binom{n}{z-x}
\\&= p^z (1-p)^{2n-z} \binom{2n}{z}
\\&= f_{2n,p}(z).
\end{align*}

Now suppose $2n \geq z > n$. Let $r = 2n-z$. Then $0\leq r< n$,
and so
\begin{align*}
\prob{Z = z} &=
\sum_{(x,y)\in [0,n]^2: x+y=z} \prob{X=x} \prob{Y=y}
\\&= \sum_{x=z-n}^n f_{n,p}(x) f_{n,p}(z-x)
\\&= p^z (1-p)^{2n-z} \sum_{x=z-n}^n \binom{n}{x} \binom{n}{z-x}
\\&= p^z (1-p)^{2n-z} \sum_{x=z-n}^n \binom{n}{n-x} \binom{n}{n
- (z-x)}
%      \\&= p^z (1-p)^{2n-z} \sum_{x=z-n}^n \binom{n}{n-x} \binom{n}{r +
%        (x - n)}
\\&= p^z (1-p)^{2n-z} \sum_{x=n-r}^n \binom{n}{n-x} \binom{n}{r +
(x - n)}
\\&= p^z (1-p)^{2n-z} \sum_{k=0}^r \binom{n}{k} \binom{n}{r -
k}
\\&= p^z (1-p)^{2n-z} \binom{2n}{r}
\\&= p^z (1-p)^{2n-z} \binom{2n}{2n-z}
\\&= p^z (1-p)^{2n-z} \binom{2n}{z}
\\&= f_{2n,p}(z).
\end{align*}

We thus see that $\prob{Z=z} = f_{2n,p}(z)$ for all $z$, and so
$Z$ has distribution $f_{2n,p}$.
}


%\ppart Assume the following result:
%\begin{lemma*}
%Suppose we have $m$ independent random variables $B_1$, \ldots,
%$B_m$ with Bernoulli distribution: for each $i$,
%\begin{align*}
%\prob{B_i = 1} &= p,\\
%\prob{B_i = 0} &= 1-p.
%\end{align*}
%Then $\sum_{i=1}^m B_i$ is a random variable with distribution
%$f_{m,p}$.
%\end{lemma*}
%Now use this result to give a simpler proof that $Z$ has
%distribution $f_{2n,p}$.

%\solution{
%Let $B_1$, \ldots, $B_{2n}$ be independent Bernoulli
%random variables, with the same distribution as in the lemma.
%Let
%\begin{align*}
%X' &= \sum_{i=1}^n B_i,\\
%Y' &= \sum_{i=n+1}^{2n} B_i,\\
%Z' &= \sum_{i=1}^{2n} B_i = X + Y.
%\end{align*}
%Now, by the lemma, both $X'$ and $Y'$ have distribution
%$f_{n,p}$. Also, $X'$ and $Y'$ are independent, since all
%$B_i$'s are mutually independent.

%We can also use the lemma to see that $Z'$ has distribution
%$f_{2n,p}$. Since $Z = X' + Y'$, we see that the sum of two
%independent random variables with distribution $f_{n,p}$ has
%distribution $f_{2n,p}$.
%}
%  \end{problemparts}
\fi


\problem  % \textbf{Binomial distribution}

A highly parallel supercomputer has 65,536 processors.  The cooling system
can't always keep up, and any processor can fail during the computation,
with probability $10\%$.  Using sophisticated failure-recovery algorithms,
the software can handle the failure of up to 7,000 processors.  Use
Theorem~3.1 in Lecture Notes~21 to derive an approximate lower bound on
the probability that the computation will complete successfully, assuming
all processor failures are independent.

\solution{

Let $n = 65536$, $p = 0.9$, and $\alpha = \frac{n -
7000}{n}$.  The probability that at most $n - 7000$ processors
will be OK is $F_{n,p}(\alpha \cdot n)$. By theorem~3.1 in lecture
notes~21, we have
\begin{align*}
F_{n,p}(\alpha n) &\leq
\frac{1-\alpha}{1 - \frac{\alpha}{p}} f_{n,p}(\alpha n)
\\&\approx \frac{1-\alpha}{1 - \alpha/p} \cdot \frac{2^{(\alpha
\log_2(\frac{p}{\alpha}) + (1-\alpha)
\log_2(\frac{1-p}{1-\alpha})) \cdot n}}{\sqrt{2\pi \alpha
(1-\alpha) n}}
\\&\approx 4.56 \cdot 10^{-9}.
\end{align*}
(Note that we can use that result, since $\alpha < p$.)  We see
that the probability that $n - 7000$ or more processors will be OK
(implying that the computation will complete successfully) is at
least $1 - 4.56\cdot 10^{-9}$.

}

\problem  \textbf{The World Series}

New York and Atlanta have both made it to the World Series again in 2000.
Assume that New York wins each game with probability 2/3 independently of
the outcomes of other games\footnote{---they wish \texttt{:-)}}.  Let $R$ be the
random variable denoting the number of the 4th game won by New York, e.g.,
if NY wins the 1st, 2nd, 4th, and 6th games, then $R=6$; let $R \eqdef 0$ if
NY doesn't win four games.

Let's generalize slightly and assume the teams keep playing,
possibly forever, until NY has indeed won 4 games.  This makes $R$ a
random variable taking on all natural number values.

\bparts

\ppart For $n>0$, give a simple closed form expression for $\prob{R = n}$.

\solution{

For $0<n<3$, we have $\prob{R=n} = 0$. For $4\leq n$, we have
\[
\prob{R=n} = \binom{n-1}{3} \cdot (2/3)^4  \cdot \frac{1}{3^{n-4}}=
\frac{8(n-1)(n-2)(n-3)}{3^{n+1}}.
\]
}


\ppart What is the most likely value of $R$?

\solution{5}

\ppart What is the probability that NY never wins 4 games, i.e., that $R=0$?

\solution{0}

\ppart What is the probability that New York really wins the 7 game
Series?

\solution{
\[
\prob{4 \leq R\leq 7}= \prob{R=4}+\prob{R=5}+\prob{R=6}+\prob{R=7} = 0.8267
%\frac{?}{?}.
\]
}

\eparts

%END   Tina's problems


\end{problems}

\end{document}



