\documentstyle[12pt]{article}

\input{/a/class/6.042/spring94/handouts/macros-course}
\newcommand\npage{\vspace{.5in}}
%\newcommand\npage{\newpage}
\newcommand\tfitem{\item [{\bf T / F \hspace*{.1in} }]}
\newcommand\Ex{\mbox{Ex}}
\newcommand\vari{\mbox{Var}}
\newcommand\Prob{\mbox{Prob}}
\setcounter{page}{0}
\addtolength{\topmargin}{-.3in}
\setlength{\textheight}{9in}

\begin{document}

\handout{answers}{Answers to practice problems for the final exam}{May 13, 1994}
%\examinitials{Final Exam}{May 17, 1994}

\bigskip
These answers are provided for you to check your work.
You should try each problem for at least 15 minutes before consulting these
answers.

\medskip

\begin{problems}

\problem
$6\cdot 5\cdot {5\choose 3} \cdot \left({1\over 6}\right)^5.$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
{\bf F, T, T, F, T, F, F, T, T.}

It is somewhat amazing that number 4 is false. 
It was intended to be true, but Ravi pointed out that a counterexample
is $t(n) = 2^{1/n}$ and $p(n) = 2^{1-1/n}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
Proof sketch:
There are four ${1\over 2}\times {1\over 2}$-squares in the unit square
so by the pigeonhole principle, 
some two points inside the same one, where they can be at most
distance $\sqrt{(1/2)^2 + (1/2)^2}$ apart.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
Proof sketch:
Verify true for $n=2$, then start with the inequality for $n-1$ and
add $1/\sqrt{n}$ to both sides and notice that the right hand side is
\[
  \sqrt{n-1} + {1\over\sqrt{n}} 
= \sqrt{n} \left( \sqrt{1-{1\over n}} + {1\over n} \right)
> \sqrt{n}.
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem \mbox{}
\begin{problemparts}
\problempart
$T(n) = \Theta(n^3)$
\problempart
$T(n) = \Theta(n)$
\problempart
$T(n) = \Theta(n^2\lg n)$
\problempart
$T(n) = \Theta(n^2)$
\problempart
$T(n) = \Theta(n^{\log_2 7})$
\problempart
$T(n) = \Theta(\sqrt{n}\lg n)$
\problempart
$T(n) = \Theta(n^2)$
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem 
Proof sketch:
Show $n = R(k,\ell) \leq R(k,\ell-1) + R(k-1,\ell)$ for $k,\ell \geq 1$.\\
Note that if $k$ or $\ell$ is $\leq 1$, then $n=1$
(the (trivial) graph on one node is sufficient).
Take as the base case $k+\ell = 4$:  for $k$ or $\ell$ equal to 1,
we have $1\leq 1+1$; for $k=\ell=2$, we have $n=2$ (either the two nodes
are connected or not) which is equal to $1+1$.
For the inductive case, fix a node $v$. 
Either (1) $v$ has edges to $R(k-1,\ell)$ nodes, on which either there are
already $\ell$ nodes with no edges between them or there are $k-1$ nodes
with all edges between them, which together with $v$ makes $k$ nodes with
all edges between them, or
(2) $v$ has no edge to $R(k,\ell-1)$ nodes,  on which either there are
already $k$ nodes with all edges between them or there are $\ell-1$ nodes
with no edges between them, which together with $v$ makes $\ell$ nodes with
no edges between them.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem
\mbox{}
\begin{problemparts}
\problempart
$\sigma_{cR}=c\sigma_R = cs$.
\problempart
$\vari(R)$ may be arbitrarily large.
\problempart
$\Ex[1/R]\leq 1$.
\problempart
$\Prob[R=10]=3/4$ and $\Prob[R=4]=\Prob[R=16]=1/8$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
\begin{eqnarray*}
T(n) & = & (n-\lg n) + \max\left( 1 + T(\lg n), 1+\lg n\right) \\
& \leq  & (n-\lg n + 1) + T(\lg n)\\
& \leq  & (n+1) - \lg n + (\lg n -\lg\lg n +1) + T(\lg\lg n) \\
& \leq  & (n+2) - \lg\lg n + (\lg\lg n -\lg\lg\lg n + 1) + T(\lg\lg\lg n) \\
& \vdots &\\
& \leq & n + \lg^*n.
\end{eqnarray*}
(For the base case, notice either that $T(1) = 0 \leq 1 + 0$ or 
that $T(2) = 2 \leq 2 + 1$.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
\mbox{}
\begin{problemparts}
\problempart
$G_X(x) = {1\over 3} x + {1\over 6} x^3 + {1\over 2} x^4$.\\
$G_Y(x) = {3\over 4} x^2 + {1\over 4} x^5$.
\problempart
$G_R(x) = {3\over 12} x^3 + {3\over 24} x^5 + \left({3\over 8} + {1\over 12}\right) x^6 + {1\over 24} x^8 + {1\over 8} x^9 = G_X(x)G_Y(y)$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
\mbox{}
\begin{problemparts}
\problempart
(This was proved in lecture.  It requires that $X$ and $Y$ be independent.)
\problempart
\begin{eqnarray*}
\Ex[R] & =&  G'(1) \\
& = & G'_X(1)G_Y(1) + G_X(1)G'_Y(1) \\
& = & G'_X(1) + G'_Y(1) \\
& = & \Ex[X] + \Ex[Y].
\end{eqnarray*}
\problempart
(The rest is straightforward manipulation\ldots)
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
\mbox{}
\begin{problemparts}
\problempart
\[
G_R(x)= \sum_{k\geq 1} (1-p)^{k-1}p x^k
	= xp \sum_{k-1\geq 0} (1-p)^{k-1}x^{k-1}
	= {px\over 1-x(1-p)}.
\]
\problempart
$G'_R(x) = p/[1-x(1-p)]^2$.\\
$G''_R(x) = 2p(1-p)/[1-x(1-p)]^3$.\\
$\vari(R) = 2(1-p)/p^2 + 1/p - (1/p)^2 = (1-p)/p^2$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
\mbox{}
\begin{problemparts}
\problempart
Sum of $k$ balls = $\sum_{i=1}^{i=n}\,  i\cdot B_i$.
\problempart
\[ \Prob[B_i = 1] = { {n-1 \choose k-1} \over {n\choose k}} = {k\over n}. \]
\problempart
\[
\Ex[\mbox{Sum}] = \sum_i i\, {k\over n} = k \, {n(n+1)\over 2n}.
\]
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem
\mbox{}
\begin{problemparts}
\problempart
Else 
\[
\Ex[R] < L\, {\Ex[R]-k\over L-k} + k\left(1-{\Ex[R]-k\over L-k}\right) = 
{L\Ex[R] -k\Ex[R]\over L-k} = \Ex[R],
\]
a contradiction.
\problempart $1/6$
\problempart $0$.  (Could be he scores $50$ with probability 1.)
\problempart
If $\Prob[R>k] \geq p$ then $\Prob[R\leq k] \leq 1-p$.\\
So $\Prob[R<0] \leq 1-1/4 = 3/4$.
\problempart
1. $\Prob[R\leq 50] \leq 1$ is best bound for the same reason as part (c).\\
For any $p<1$, it is possible that he scores $50-\epsilon$ with probability
$p$ and $200$ with probability $1-p$, where $\epsilon = 150(1-p)/p$ to make
$\Ex[R] = 50$.
\problempart
Thinking of everything complemented, we have 
\[
\Prob[R<k] = \Prob[-R > -k] \geq {\Ex[-R] - (-k)\over 50 -(-k)}
\]
since $-R\leq 50$ always.  
So $\Prob[R<100]\geq (-50+100)/(50+100)=2/3$.\\
(Else $\Ex[R] > (-50){1\over 3} + 100{2\over 3} = 50$, a contradiction.)
\problempart
$1/4$.
\problempart
\[ \Prob\left[(R-\Ex[R])^6 > 50^6\right] \leq  
\Prob\left[(R-\Ex[R])^6 > 5^6 \cdot \Ex[(R-\Ex[R])^6]\right] \leq 1/5^6.
\]
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
(Should have said, ``using the calculation from Problem 11''.)\\

$\vari(R_i) = (1-p)/p^2 = ni/(n-i)^2$.\\
\begin{eqnarray*}
\vari(R) & = & \sum_{i=0}^{n-1} {ni\over (n-i)^2}
	 =  \sum_{i=0}^{n-1} {n(n-i)\over i^2} \\
& = &	n\, \sum_{i=0}^{n-1} {n-i\over i^2} \\
& = &	n\, \sum_{i=0}^{n-1} \left( {n\over i^2} - {1\over i} \right) \\
& \sim & n \left( n \left[-{1\over 2i}\right]_1^{n-1} 
				- \ln n \right) \\
& \sim & {n^2\over 2}.
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
$\displaystyle 
\Ex[return] = \sum_{k=0}^{k=\infty} \$ 2^k \left({1\over2}\right)^k,
$ 
which is infinite! \\
(You are still welcome to come play the game for \$1000 in NE43-371\ldots)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
\mbox{}\\
\hspace*{.3in} $\Ex[\# heads] = 100{1\over 2} = 50$.\\
\hspace*{.3in} $\vari(\# heads) = 100{1\over 2}(1-{1\over 2}) = 25$.\\
\begin{problemparts}
\problempart  $5/7$.
\problempart  $1/16$.
\problempart
\[
{1-0.3\over 1-0.6}   \cdot    \sqrt{2\over 100 \pi} \cdot
e^{-4^2/2}           \cdot    \left( {100\over e} \right)^{1\over 1200}
		\approx 0.000047
\]
\end{problemparts}	

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
$\Prob[\mbox{each unit does not fail}] = (1-p)^A \leq e^{-pA}$.

\end{problems}
\end{document}
