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

\askaboutsolutions

\begin{document}

\ifshowsolutions
  \prsol{12}{November 28, 2001}{\stamp}
\else
  \prprob{12}{November 26, 2001}{Wednesday, Nov. 28}{\stamp}
\fi

\reading \href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l13.pdf}
{Lecture Notes 13}, sections 3.3-3.4 of
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l12.pdf}
{Lecture Notes 12}

\ifshowsolutions{}\else
By 9am on the due date, send email to
\begin{center}
\href{mailto:6042-probs@theory.lcs.mit.edu?subject=Required\%20Reading\%20Comments\%20Week\%209}
{6042-probs@theory.lcs.mit.edu}
\end{center}
indicating in at most three sentences one or more of the following:
the passage in the reading---\emph{including its page number}---you
\begin{itemize}
\item found most difficult,
\item found most surprising,
\item would like to have discussed in the next Lecture.
\end{itemize}
\fi

\begin{problems}
\problem %source: spring00 ps10-5
One hundred twenty students take the 6.042 final exam.  The mean on the exam is
$90$.  You have no other information about the
students and the exam, e.g., you should not assume that the final is worth
100 points.
% and the lowest score was 30

\bparts

\ppart State the best possible upper bound on the number of students who
scored at least $180$.  

\solnospace{Let $R$ be the score of a student chosen at random.  
Apply Markov's Bound to $R$:
\[
\Pr(R \geq 180)\leq \frac{\expect{R}}{180} 
        = \frac{90}{180} = \frac{1}{2}.
\]
So at most $\frac{1}{2} \cdot 120 = 60$ students scored 
greater than or equal to $180$.}

\ppart Suppose you're now told that the lowest score on the exam was
30.  Compute a new best possible upper bound on the number of students
who scored at least 180.

\solnospace{We can apply Markov's Bound to $R-30$ instead of $R$:
\[
\Pr(R \geq 180) = \Pr(R-30 \geq 150) 
        \leq \frac{\expect{R-30}}{150} 
        = \frac{60}{150} = \frac{2}{5}.
\]
So at most $\frac{2}{5} \cdot 120 = 48$ students scored 
greater than or equal to $180$.}

\iffalse
\ppart Give an example set of scores which achieve your bound.

\solnospace{Of the 120 students, 48 score 180 and 72 score 30.  
The mean is $\frac{48 \cdot 180 + 72 \cdot 30}{120} = 90$, as required.}

\ppart If the maximum score on the exam was $100$, 
give the best possible upper bound on the number of students 
who scored \emph{at most} $50$. 

\solnospace{Apply Markov's Bound to $100-R$: 
\[
\Pr(R \leq 50) = \Pr(100-R \geq 50)
        \leq \frac{\expect{100-R}}{50}
        = \frac{10}{50}
        = \frac{1}{5}.
\]
So at most $\frac{1}{5} \cdot 120 = 24$ students scored $50$ or less.} 

\fi

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem11 spring98; from fall 96 pset12 problem8
\problem


Suppose you flip a fair coin 100 times.  The coin flips are all mutually independent.  
\begin{problemparts}

\problempart
What is an upper bound on the probability
that the number of heads is at least 70 according to Markov's Inequality?

\solnospace{
The expected number of heads of $50$.  So the probability that the
number of heads is at least $70$ is at most $50/70 = 0.71$.
}

\problempart
What is an upper bound on the probability
that the number of heads lies between 30 and 70 according to
Chebyshev's Inequality? 

\solnospace{
Let $X_i$ be the random variable whose value is $1$ if the $i$th coin
flip is heads.  Then $\Var[X_i] =  1/2 - (1/2)^2 = 1/4$.  So $\Var[X_1
+ \cdots + X_{100}] = 100/4 = 25$.

 The variance of the number of heads is $100/4 = 25$, so the standard
deviation is $5$.  So $|30-50|=|70-50|=20$ is four times the standard
deviation from the mean.  The
probability is at most $\frac{1}{4^2} = \frac{1}{16}$.

%So $70$ is four times the standard deviation from
%the mean.  Since the distribution is symmetric, the
%probability is at most $\frac{1}{2} \cdot \frac{1}{4^2} = \frac{1}{32}$
}
\end{problemparts}


%Came up with this in another class --Ashish

\problem
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$.  Then which of the following are true:
\begin{problemparts}
\problempart
$\expect{X}=0$
\solnospace{True}
\problempart
$\expect{Y}=0$
\solnospace{False}
\problempart
$\expect{Y}>\expect{X}$
\solnospace{True}
\problempart
$\expect{X+Y}=\expect{X}+\expect{Y}$
\solnospace{True}
\problempart
$\expect{XY}=\expect{X}\expect{Y}$
\solnospace{True}
\problempart
$X, Y$ are independent variables.
\solnospace{False}
\problempart
$\variance{X}=0$
\solnospace{False}
\problempart
$\variance{Y}=0$
\solnospace{False}

\iffalse
\problempart
$\variance{Y}>\variance{X}$
\solnospace{True}
\problempart
$\variance{X+Y}=\variance{X}+\variance{Y}$
\solnospace{False}
\problempart
$\variance{XY}=\variance{X}\variance{Y}$
\solnospace{False}
\fi

\end{problemparts}

\problem 
Suppose we roll a fair, 6-sided dice and get a number $t$. Then we flip
an unbiased coin $t$ times. What is the expected number of heads?

\solnospace{
$$
3.5\cdot 0.5=1.75
$$
}


%%%REMAINDER ARE NOT USED
%%%


\iffalse
%pset10 problem9 spring98 (not used)
\problem

We want to determine the percentage $r$ of people who intend to watch
the {\em Harry Potter} movie. Our polling method is the same as
that discussed in lecture: we sample the opinion of $n$ people chosen
uniformly and at random, with replacement.

How many people should be polled so that $r$ is within 3 points of the
true percentage, with probability at least .96?

\solnospace{
$\epsilon = .03, \delta = .04$

\begin{eqnarray*}
\delta \geq 2 F_{1/2}((1/2- \epsilon)n) & \Rightarrow &
.05 \geq 2  F_{1/2}(0.49n)\\
& \Rightarrow & 0.025 \geq {0.51 \over 0.02}f_{1/2}(0.49n)\\
& \Rightarrow & 0.025 \geq {25.5 \over\sqrt{2n\pi (.49)(.51)}}2^{(H(.49)-1)n}\\
& \Rightarrow & 0.0012285 \geq {2^{(H(.49)-1)n} \over \sqrt{n}}\\
& \Rightarrow & 0.0012285 \geq {2^{-0.000288574n} \over \sqrt{n}}\\
& \Rightarrow & 0.0012285 \geq {(.9998)^n \over \sqrt{n}}\\
\end{eqnarray*}

Choosing $n=10388$ will do it.
}

\problem
(Pick some small $n$, like $n=6$).\\
Suppose I flip $n$ unbiased independent coins.  Assume $n$ is even.
We know that 
the mean number of heads is $n/2$.  What is the {\em expected 
  deviation from the mean}?  That is, if the number of heads is a
random variable $X$, what is
\[
E[|X-n/2|]?
\]
\solnospace{
\iffalse
\begin{eqnarray*}
E(|X - n/2|) & = &2^{-n}\left[ {\displaystyle \sum_{k=0}^n {n\choose k} |k - \frac{n}{2}|} \right]  \\
 & = &2^{-n}\left[2  {\displaystyle \sum_{k=0}^{\frac{n}{2}-1} {n\choose k} (\frac{n}{2} - k) } \right]  \\
 & = &2^{-n}\left[n{\displaystyle \sum_{k=0}^{\frac{n}{2}-1} {n\choose k} }\right] + 2^{-n}\left[2{\displaystyle \sum_{k=0}^{\frac{n}{2}-1} {n\choose k}k} \right]  \\
 & = &2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}}) \right] + 2^{-n}\left[2{\displaystyle \sum_{k=1}^{\frac{n}{2}-1} {n-1\choose k-1}(\frac{n}{k})k} \right]  \\
 & = &2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}}) \right] + 2^{-n}\left[2n{\displaystyle \sum_{k=0}^{\frac{n}{2}-2} {n-1\choose k}} \right]  \\
 & = &2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}}) \right] + 2^{-n}\left[2n(2^{n-2} - {n-1\choose \frac{n}{2} - 1}) \right]  \\
 & = &2^{-n}\left[n(2^{n-1} - (\frac{1}{2}){n\choose \frac{n}{2}})  + 2n(2^{n-2} - {n-1\choose \frac{n}{2} - 1}) \right]  \\
 & = &2^{-n}{n\choose \frac{n}{2}}(\frac{n}{2})
\end{eqnarray*}
\fi
$2^{-n}{n\choose \frac{n}{2}}(\frac{n}{2})$
}

\iffalse
\problem
A man has a set of $n$ keys, one of which fits the door
to his apartment.  He tries the keys until he
finds the correct one.  Give the expected number and variance
for the number of trials until success if

\bparts

\ppart he tries the keys at random (possibly repeating a key tried
       earlier)


\solnospace{This problem can be modeled by the Polya Urn Scheme:
Consider an urn with $n-1$ wrong keys and $1$ right key. Each time the
man chooses a key, he tries it and then places it back in the urn. We
want to compute the waiting time, $T$, to pick the right key.

The probability of picking the right key on the first trial is $1/n$,
and the probability of picking the wrong key is $(n-1)/n$.  The
probability stays the same on all subsequent trials since the picked
key is always returned to the urn. Thus
\[
P(T=k) = \left({n-1 \over n}\right)^{k-1}{1\over n}{.}
\]
Note: this is the same as the waiting time for the first head in the
Bernouli process with a biased coin. Let $p=1/n$ and let $q=1-p$.
Then, the expectation of $T$ is
\[
E(T) = \sum_{k=1}^\infty{k q^{k-1}p}
= p\sum_{k=1}^\infty{k q^{k-1}}
= p{1\over (1-q)^2} = {1\over p} = n
\]

The variance of $T$ can be computed directly from the formula,
\[
\variance{T} = E(T^2) - E^2(T){.}
\]
Again, by definition we have
\[
E(T^2) = \sum_{k=1}^\infty{k^2 pq^{k-1}}{.}
\]
How do we evaluate this sum? We use the following trick. We know that
\[
\sum_{k=1}^\infty{kq^k} = q\sum_{k=1}^\infty{kq^{k-1}} = {q\over (1-q)^2}{.}
\]
Moreover,
\begin{eqnarray*}
\sum_{k=1}^\infty{k^2 q^{k-1}} &=& \sum_{k=1}^\infty{{d\over dq}k q^k}\\
 &=& {d\over dq}\sum_{k=1}^\infty{k q^k}\\
 &=& {d\over dq}{q\over (1-q)^2}\\
 &=& {1\over(1-q)^2} + {2q \over (1-q)^3} = {1\over p^2} + {2q\over p^3}{.}
\end{eqnarray*}
Finally, the expectation $E(T^2)$ is
\[
E(T^2) = p \left({1\over p^2} + {2q\over p^3}\right) = {1\over p} + {2q\over p^2} {,}
\]
and the variance is
\[
\variance{T} = {1\over p} + {2q\over p^2} - {1\over p^2} = {q\over p^2} = n(n-1){.}
\]
}

\ppart he chooses keys randomly from among those he has not
       yet tried.

\solnospace{
Again we look at this as a Polya Urn Process, but
without replacement. The event that the waiting time for the right
key, $T$, is $k$ is the event that we pick the wrong key on the first
trial, and we pick the wrong key on the second trial, etc, and we pick
the right key on the $k$-th trial. Let $K_i$ be the indicator random
variable for the $i$-th trial, i.e. $K_i=1$ if we pick the right key
on the $i$-th trial, and $0$ otherwise. Then
\[
P(T=k) = P((K_1=0) \& (K_2=0) \&\cdots\& (K_{k-1}=0) \& (K_k=1)){.}
\]
By the Multiplication Theorem we can compute
\begin{eqnarray*}
P(T=k) &=& P(K_1=0)P(K_2=0|K_1=0)P(K_3=0|K_1=0,K_2=0)\cdots\\
 & &\hspace{2in}\cdots P(K_k=1|K_1=0,\dots,K_{k-1}=0)\\
 &=& {n-1 \over n}\ {n-2 \over n-1}\ {n-3 \over n-2}\ \cdots\ {n-k+1\over n-k+2}\ {1\over n-k+1}\\
 &=& {1\over n}{.}
\end{eqnarray*}
The expectation and variance are now easy to compute from the definitions.
\[
E(T) = \sum_{k=1}^n{kP(T=k)} = {1\over n}\sum_{k=1}^n{k} = {n+1\over 2}{.}
\]
\begin{eqnarray*}
\variance{T} &=& E(T^2) - E^2(T)\\
 &=& \sum_{k=1}^n{k^2 P(T=k)} - \left({n+1\over 2}\right)^2\\
 &=& {1\over n}\sum_{k=1}^n{k^2} - \left({n+1\over 2}\right)^2\\
 &=& {1\over n}\ {n(n+1)(2n+1)\over 6} - \left({n+1\over 2}\right)^2\\
 &=& {n^2-1\over 12}{.}
\end{eqnarray*}
}

\eparts
\fi

\problem
(To make this multiple choice)\\
Let $R:S\rightarrow \nats$ be a random variable.
\begin{problemparts}
\problempart
Let $R'=cR$ for some positive constant~$c$.
If $\sigma_R = s$, what is $\sigma_{R'}$?
\problempart
If $\expect{R}=1$, how large can $\variance{R}$ be?
\problempart
If $R$ is always positive (nonzero), how large can $\expect{1/R}$ be?
\end{problemparts}

\fi


\end{problems}

\end{document}

