\documentclass[12pt]{article}
\input{macros-course}

\newcommand{\Fib}{{\sf Fib}}

\askaboutsolutions

\begin{document}

\ifshowsolutions
  \psetsol{11}{November 30, 2001}{\stamp}
\else
  \pset{11}{November 19, 2001}{Wednesday November 28, beginning of lecture}{\stamp}
  \collaborationnote
\fi

\reading
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l12.pdf}
{Week 12 Notes}.  Rosen \S 4.5.

\begin{problems}

%source: Fall 2000 pset11,prob1
% \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)$

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

% \solnospace{ 
% 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 The faculty holds a dinner party for $n \geq 2$ couples.  The
hostess chooses a seating arrangement for the $2n$ people around a
circular table uniformly at random. What is the expected number of
couples such that the husband and wife are sitting next to each other?

\solnospace{
Let $I_k$ be an indicator variable for the event that couple
$k$ is sitting together.  Then the number of couples sitting together
is $I_1 + I_2 + \ldots + I_n$.  The probability that a couple is
seated together is $2 / (2n-1)$, since a wife is equally likely to
occupy each of the $2n-1$ positions relative to her husband and there
are 2 positions right next to him.  Consequently, $\Pr(I_k = 1) = 2 /
(2n-1)$, and we can reason as follows:

\begin{eqnarray*}
\Ex(\text{couples sitting together})
	& = &	\Ex\left(\sum_{k=1}^n I_k\right) \\
	& = &	\sum_{k=1}^n \Ex(I_k) \\
	& = &	\sum_{k=1}^n \Pr(I_k = 1) \\
	& = &	\sum_{k=1}^n \frac{2}{2n-1} \\
	& = &	\frac{2n}{2n-1}
\end{eqnarray*}
%Thus, regardless of the size of the party, the expected number of
%couples seated together is always close to 1.
Thus, as $n$ increases, the expected number of couples seated together converges to 1.
}

% source: Spring 99 pset11, prob8
\problem Each bag of Doritos contains a cool sticker. There are $n$
different types of stickers and if I collect at least one sticker of
each type I will win a big screen TV. Assume that all sticker types
are equally likely and stickers are placed in bags independently.

\bparts \ppart Suppose that I have already collected $k$ types of
stickers.  What is the expected number of additional bags of Doritos
that I must eat to collect one additional type of sticker?

\solnospace{
The probability that I must eat $i$ or more bags is:
\begin{eqnarray*}
\lefteqn{\expect{\text{number of bags to get new type}}}\\
        & = &   \sum_{i=0}^{\infty} \prob{\text{number of bags to get new type} > i} \\
        & = &   \sum_{i=0}^{\infty} \prob{\text{number of old types in first $i$ bags}} \\
        & = &   \sum_{i=0}^{\infty} \left(\frac{k}{n} \right)^i \\
        & = &   \frac{n}{n-k}
\end{eqnarray*}
}

\ppart What is the expected number of bags of Doritos that I
must eat to collect at least one sticker of each type?

\solution{We sum the expected number of bags to get the first type,
the expected number to get the second type, and so forth.
\begin{eqnarray*}
\lefteqn{\expect{\text{number of bags to get all types}}}\\
        & = &   \sum_{k=0}^{n-1} \frac{n}{n-k} \ = \   n \cdot
        \sum_{k=0}^{n-1} \frac{1}{n-k} \\
        & = &  n \cdot \sum_{j=1}^{n} \frac{1}{j} 
        \ = \   n H_n.
\end{eqnarray*}
}

\eparts


\problem

% modifed from spring 97 Pset 13, 3

There are $n$ MIT students who are taking 6.042 and 6.003 this term.  To
make it easier on themselves, the professors in charge of these classes
have decided to randomly permute their class lists and then assign
students grades based on their rank in the permutation\footnote{\dots just
as many students have suspected \texttt{:-)}}.  Assume all permutations
are equally likely and that the ranking in each class is independent of
the other.

\bparts

\ppart
What is the expected number of students that have a higher rank
in 6.042 than 6.003?

\solution{

Let $X_i$ be random variable whose value is 1 if student i has higher rank
in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$ for
6.042 than the probability that student $i$ has higher rank on 6.042,
given that the student has rank $r$ in 6.042, is $(r-1)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the
probability that student $i$ has higher rank in 6.042 is
\[
\sum_{1\leq r \leq n}  \frac{1}{n} \frac{r-1}{n} = \frac{n-1}{2n}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x} = \expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{n-1}{2}.
\]

Another way to solve this problem is to observe that students with higher
rank in one class have lower rank in the other class, so by symmetry, the
expected number of higher- and lower-ranked students in either class is
the same.  The expected number of students with the same rank equals 1 by
linearity of expectation, since probability student ranked the same in
both classes is $1/n$.  These observations now yield same answer as above.

}

\ppart
What is the expected number of students that have a ranking at
least $k$ higher in 6.042 than in 6.003?

\solution{

This part can be done in the same way as the previous one.  Let $X_i$ be
the random variable whose value is 1 if student $i$ is ranked at least $k$
higher in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$
$(r>k)$ for 6.042 than the probability that student $i$ has at least $k$
higher rank in 6.042 given student ranked $r$ in 6.042 is $(r-k)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the probability
that student $i$ has at least $k$ higher rank in 6.042 is
\[
\sum_{k+1\leq r\leq n} \frac{1}{n} \frac{r-k}{n} = \frac{(n-k)(n-k+1)}{2n^2}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x}=\expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{(n-k)(n-k+1)}{2n}.
\]

}

\eparts

% % source: Spring 00, Tutorial 1, prob1
% \problem

% Suppose you are heading a scientific polling organization. Candidate
% Al Gore wants you poll a group of voters in Florida to determine his
% popularity. Furthermore, he would like a margin of error of $2\%$. How
% large a sample size do you need to be able to tell him with $95$
% percent confidence that the error attributable to sampling and other
% random effects is within plus or minus $2$ percentage points?

% \solnospace{

% Let $p$ be the probability that a person will vote for Al Gore,
% $\epsilon$ be the margin of error and let $\delta$ be the probability
% that our result lies outside this margin. Therefore we have
% $\epsilon=0.02$ and $\delta=0.05$. Since we get the maximum value of
% $\delta$ when $p=0.5$

% \begin{eqnarray*}
% \delta
%         & \leq &  F_{n,\frac{1}{2}}((\frac{1}{2}-\epsilon)n) +
%                   F_{n,1-\frac{1}{2}}((1-\frac{1}{2}-\epsilon)n)\\
%         & = &     2F_{n,\frac{1}{2}}((\frac{1}{2}-\epsilon)n)\\
%         & = &     2F_{n,\frac{1}{2}}((\frac{1}{2}-0.02)n)\\
%         & = &     2F_{n,\frac{1}{2}}(0.48n)\\
%         & \leq &  2\frac{1-0.48}{1-\frac{0.48}{0.5}}f_{n,\frac{1}{2}}(0.48n)\\
%         & = &     26 f_{n,\frac{1}{2}}(0.48n)
% \end{eqnarray*}

% Solving for $n$, we get $n=2616$. Therefore, if the sample size is $n >
% 2616$ we get the desired property.  }

% % source: Fall 1999, pset12, prob3
% \problem

% Ben Bitdiddle is asked to analyze a game in which a fair coin is tossed
% until the first time a head turns up.  If this head occurs on the $n$th
% toss, and $n$ is odd, then he wins $\$2^n/n$, but if $n$ is even, he loses
% $\$2^n/n$.  Ben observes that the expected dollar win from this game is
% the value of the series:
% \[
% (1/2) \cdot 2 - (1/4) \cdot 2 + (1/8) \cdot 8/3 + \cdots \pm (1/2^n)
%  \cdot 2^n/n + \cdots
%  = 1 - 1/2 + 1/3 - 1/4 + \cdots \pm 1/n \cdots
% \]
% This is the \emph{alternating harmonic series}---a series which is known
% to converge to a definite real number $r>0$.  Ben concludes that since $r
% >0$, it's to his advantage to play this game.  As usual, Ben's
% shoot-from-the-hip analysis is off the mark.  Explain.

% \solnospace{

% This series is convergent, but not \emph{absolutely} convergent.  The
% definition of expectation requires absolute convergence, so the
% expectation in this case is not defined.  The fact that the expectation is
% undefined is no mere formality.  The number $r$ is not relevant to the
% behavior of the game.  Indeed, we showed in a tutorial problem that by
% reordering its terms, the series can be made to converge to any real value
% or diverge to $\pm\infty$.\\

% % Solution Modified in Fall 01 (tong)

% {\bf An alternative solution:}\\
% Let $R_n$ be the indicator for the outcome $\text{T}^{(n-1)}\text{H}$ of this game. That is, $R_n=1$ if the outcome is $\text{T}^{(n-1)}\text{H}$, and $R_n=0$ if the outcome is other case. The payoff of this game is the linear combination of these indicators:
% \[
% P=\sum_{i=1}^{\infty}(-1)^{(i+1)}\frac{2^i}{i}R_i.
% \]
% Therefore,
% \[
% \expect{P}=\expect{\sum_{i=1}^{\infty}(-1)^{(i+1)}\frac{2^i}{i}R_i}.
% \]
% Note that $1 - 1/2 + 1/3 - 1/4 + \cdots \pm 1/n+\cdots$ is convergent, but not \emph{absolutely} convergent. We can not conclude that 
% \[
% \expect{P}=1 - 1/2 + 1/3 - 1/4 + \cdots \pm 1/n+\cdots=r.
% \]

% }

%% source:?????

\problem Suppose that $R$ is a random variable.  Let
$C$ be an event.  The {\em conditional expectation} of $R$ given that
event $C$ occurs is denoted $\expect{R \mid C}$ and is defined to be
\[
\expect{R \mid C}  ::= \sum_{x \in \text{range}(R)} x \cdot \prob{R = x \mid C}.
\]

\bparts

\ppart Compute the expected value of the number rolled on a
fair, six-sided die, given that the outcome is even.

\solnospace{Let the random variable $R$ be the number rolled, and let
$C$ be the event that the number rolled is even.
\begin{eqnarray*}
\expect{R \mid C}       & = &   \sum_{x=1}^{6} x \cdot \prob{R = x \mid C} \\
                & = &   1 \cdot 0 + 2 \cdot \frac{1}{3} + 
                        3 \cdot 0 + 4 \cdot \frac{1}{3} + 
                        5 \cdot 0 + 6 \cdot \frac{1}{3} \\
                & = &   4
\end{eqnarray*}
}

\ppart Compute the expected value of the number rolled on a
fair, six-sided die, given that the outcome is odd.

\solnospace{Define $R$ and $C$ as before.
\begin{eqnarray*}
\expect{R \mid \overline{C}}
        & = &   \sum_{x=1}^{6} x \cdot \prob{R = x \mid \overline{C}} \\
        & = &   1 \cdot \frac{1}{3} + 2 \cdot 0 + 
                3 \cdot \frac{1}{3} + 4 \cdot 0 + 
                5 \cdot \frac{1}{3} + 6 \cdot 0 \\
        & = &   3
\end{eqnarray*}
}

\ppart Prove the following identity, assuming that all
expectations exist.
\begin{eqnarray*}
\expect{R}      & = &   \prob{C} \cdot \expect{R \mid C} +
                        \prob{\overline{C}} \cdot \expect{R \mid \overline{C}}
\end{eqnarray*}

\solnospace{We transform the right side into the left side.  All
summations are over $x \in \text{Range}(R)$.
\begin{eqnarray*}
\lefteqn{\prob{C} \cdot \expect{R \mid C} +
        \prob{\overline{C}} \cdot \expect{R \mid \overline{C}}} \\
        & = &   \prob{C} \cdot ( \sum_{x}
                        x \cdot \prob{R = x \mid C} )
                + \prob{\overline{C}} \cdot  ( \sum_{x}
                        x \cdot \prob{R = x \mid \overline{C}} ) \\
        & = &   \prob{C} \cdot ( \sum_{x}
                        x \cdot \frac{\prob{[R = x] \cap C}}{\prob{C}} )
                + \prob{\overline{C}} \cdot  ( \sum_{x}
                        x \cdot \frac{\prob{[R = x] \cap \overline{C}}}
                        {\prob{\overline{C}}} ) \\
        & = &   \sum_{x} x \cdot (
                        \prob{[R = x] \cap C} + \prob{[R = x] \cap \overline{C}}
                        ) \\
        & = &   \sum_{x} x \cdot (
                        \prob{([R = x] \cap C) \cup ([R = x] \cap \overline{C})}
                        ) \\
        & = &   \sum_{x} x \cdot \prob{R = x} \\
        & = &   \expect{R}
\end{eqnarray*}

The first step uses the definition of conditional expectation.  The
second step uses the definition of conditional probability.  The third
step is simplification.  The fourth step uses the fact that the
probability of a disjoint union of events is equal to the sum of the
event probabilities.  The fifth step is simplification, and the final
step uses the definition of expected value.}

\eparts

% source: Spring 1999, pset10, prob 6
\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$.
}
%end of problems by Nikos

\end{problems}
 
\end{document}                            
