\documentclass[12pt]{article}   
\usepackage{latex-macros/course}% !! Use the macros

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
\hidesolutions                  % !! use to force no solutions & skip
                                % query 


\renewcommand{\reading}{        % !! Redefine this week's reading
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l12.pdf}
{Week 12 Notes}.  Rosen \S 4.5.}


\begin{document}
\problemset{11}                 % !! Start the problem set with its number




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




\begin{problem}                 % !! use the ``problem'' environment 
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?
\end{problem} 

\solution{                      % !! use \solution
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:
$$
\text{bla}
$$
Thus, regardless of the size of the party, the expected number of
couples seated together is always close to 1.
}






% source: Spring 99 pset11, prob8
\begin{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.
\begin{problemparts}            % !! Use the problemparts environment

\problempart                    % !! problempart is the item here
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?

\solution{
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*}
}

\problempart 
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*}
}
\end{problemparts}
\end{problem} 







% source: Spring 00, Tutorial 1, prob1
\begin{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?
\end{problem} 

\solution{
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
t hat 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=629$. Therefore, if the sample size is $n >
629$ we get the desired property.  }







% source: Fall 1999, pset12, prob3
\begin{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
 = 1 - 1/2 + 1/3 - 1/4 + \cdots \pm 1/n.
\]
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.
\end{problem} 

\solution{
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:?????

\begin{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}.
\]
\begin{problemparts}

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

\solution{
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*}
}

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

\solution{
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*}
}

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

\solution{
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.}
\end{problemparts}
\end{problem} 








% source: Spring 1999, pset10, prob 6
\begin{problem}  \label{pnum}
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.
\begin{problemparts}

\problempart \label{ppnum}
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.

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

\problempart \label{ppnum2}
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}

\problempart 
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.
\ref{pnum}, \ref{ppnum}, \ref{ppnum2}
\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.}

\problempart 
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.}
\end{problemparts}
\end{problem} 




\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$.
}
%end of problems by Nikos

 
\end{document}                            
