\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{practice}{Some practice problems for the final exam}{May 11, 1994}
%\examinitials{Final Exam}{May 17, 1994}

\bigskip
The final will contain problems that draw on material from the
entire semester.  The emphasis will be on probability and topics covered since 
the last exam.  This handout contains some review problems and some
practice problems on the material since the last problem set.

\begin{problems}

\npage
\problem
If you roll five fair, (mutually) independent dice, what is the
probability of getting a full house (two dice with one value and
three dice with a different value)?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
True or false.\\
Let $p,r,s$ and $t$ be functions from $\nat$ to $\reals$.
\begin{itemize}
\setlength\itemindent{.5in}
\tfitem  $2^{\lg^2 n}$ is $\Theta(n^2)$.
\tfitem  $p(n) = 10(\frac{1}{5} + \frac{1}{5^2} + \cdots + \frac{1}{5^n})$
	 is $O(1)$.
\tfitem  If $t(n)$ is $\omega(1)$ and $p(n)$ is $O(1)$, 
	  then $t(n) + p(n) \sim t(n)$.
\tfitem  If $t(n)$ is $\Theta(p(n))$ 
		then $\lg (t(n)p(n))$ is $\Theta(\lg t(n))$.
\tfitem  If $p(n)=5$ then $p(n)$ is $O(1)$.
\tfitem If $p(n) \sim s(n)$ and $t(n) = o(1)$, then $p(n) \sim s(n)+t(n)$.
\tfitem If $p(n)$ is $O\left( s(n)t(n) \right)$ then $p(n)$ is $O(s(n))$
	and $O(t(n))$.
\tfitem  $p(n)=2n$ is a bijection between $\nat$ and $2\nat$	
		(the even natural numbers).
%\tfitem  If $f\circ g$ is the identity function, then $f$ maps $A$ onto $B$.
\tfitem  $p(n) = \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2n}$
		is $\sim \ln(\sqrt{n})$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
Suppose $p_1, p_2, \ldots, p_5$ are any five points in the interior of 
the unit square in the plane, and let $d_{ij}$ denote the (Euclidean) distance
between $p_i$ and $p_j$.  Prove that there exist $p_i$ and $p_j$ such
that $d_{ij} < \sqrt{2}/2$.  [Use the pigeonhole principle.]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
Prove that
\[
{1\over\sqrt{1}} + {1\over\sqrt{2}} + {1\over\sqrt{3}} + \cdots + 
	{1\over\sqrt{n}}
 > \sqrt{n} \mbox{\hspace*{.3in} for $n=2,3,4,\ldots$}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem
Give asymptotic upper bounds for $T(n)$ in each of the following recurrences.
Assume that $T(n)$ is constant for $n\leq 2$.
Make your bounds as tight as possible.
\begin{problemparts}
\problempart
$T(n) = 2 T(n/2) + n^3$
\problempart
$T(n) = T(9n/10) + n$
\problempart
$T(n) = 16 T(n/4) + n^2$
\problempart
$T(n) = 7 T(n/3) + n^2$
\problempart
$T(n) = 7 T(n/2) + n^2$
\problempart
$T(n) = 2 T(n/4) + \sqrt{n}$
\problempart
$T(n) = T(n-1) + n$
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem 
Recall that on Problem Set 2 you were asked to prove that 
any graph on $6$ vertices contains either $3$ vertices with no edges  
between them or $3$ vertices with all edges between them.
The idea was to fix a particular node $v$ and look at its set of neighbors:
if they number three or more, then either 
none of them share an edge (in which case we're done), 
or two of them share an edge, 
in which case they and $v$ have all edges between them.
If $v$'s neighbors number 2 or fewer, a complementary
argument is carried out on the nodes not adjacent to~$v$.

This is a special case of what is called a ``Ramsey Theorem''.
One Ramsey Theorem states that 
\begin{quotation}
For any pair of positive integers $(k,\ell)$
there exists an $n$ large enough so that {\em every } graph on $n$ 
nodes has either a subset of $k$ vertices with all $k\choose 2$
edges between them or a subset of $\ell$ vertices with no edge between any
two of them.
\end{quotation}
Prove this by induction on $k+\ell$ by 
assuming it is true for $(k-1,\ell)$ and $(k,\ell-1)$ 
and proving it's true for $(k,\ell)$.  It may help to write 
$n$ as a function of $k$ and $\ell$, $n=R(k,\ell)$, and show
$R(k,\ell) \leq R(k,\ell-1) + R(k-1,\ell)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem
Let $R:S\rightarrow \nat$ be a random variable.
\begin{problemparts}
\problempart
If $\sigma_R = s$ and $c$ is a constant, what is $\sigma_{cR}$?
\problempart
If $\Ex[R]=1$, how large can $\vari(R)$ be?
\problempart
If $R$ is always positive (nonzero), how large can $\Ex[1/R]$ be?
\problempart
Exhibit (sketch) a possible distribution for $R$ with 
\begin{itemize}
\item $\Ex[R]=10$, 
\item $\sigma^2_R=9$, and 
\item $\Prob[|R-\Ex[R]| \geq 6] = 1/4$.
\end{itemize}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage\problem
Consider the following problem of communication complexity.
You and I are each given a string of $n$ bits---I get $x\in\{0,1\}^n$
and you get $y\in\{0,1\}^n$.
Neither of us knows the other's string, but we know that they are different,
$x\neq y$.
We must determine a position in which our strings differ---a bit $i$, 
$1\leq i\leq n$ such that $x_i \neq y_i$.
We communicate by sending one-bit messages back and forth
according to some algorithm, and we would like to minimize the total number
of bits sent in the worst case.  At the end of the algorithm, both of us must 
agree on a position in which our strings differ.
For example, a simple
algorithm would be for me to simply send my whole string, and for you
to tell me the answer ($i$).  This requires exactly $n+\lg n$ bits.
%	$n$ for my message and $\lg n$ for yours.

In fact, this problem can be solved with only $n+\lg^*n$ bits\footnote{%
	Recall that $\lg^*n$ is the least integer $i$ such that $\lg^in\leq 1$.
	Note that $\lg*n$ has a different ``type'' than 
	$\lg^in= \underbrace{\lg\lg\cdots\lg}_i n$
	(undefined if $\lg^{i-1}\leq 0$);
	for $\lg^*n : \reals\to\nat$ but $\lg^in : \reals\to\reals$.
	Also, $\lg^* n$ grows extremely slowly---$\lg^*(2^{65536})=5$---so 
	$n+\lg^*n$ is better than $n+\lg n$.}, 
using a clever recursive algorithm:
I send you my first $n-\lg n$ bits,
and either (1) you now know a bit in which our strings differ, in
which case you first send me a 1 (to tell me this is the case) and then
you send me the answer, or (2) our strings are the same in the first 
$n-\lg n$ bits, in which case you first send me a 0 (to tell me 
this is the case) and then we recurse on the remaining $\lg n$ bits.

Write a recurrence for $T(n)$, the total number of bits required
by the algorithm.  Note that in case (1) above, we finish with a total
of only $(n-\lg n) + (1+\lg n) = n+1$ bits; you should convince yourself
that it's the recursive case (2) that costs the most and therefore determines
maximum number of bits required.
Solve the recurrence by iterating it and discovering a telescoping sum.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
Say random variable $X:S\to \nat$ has distribution
\[
X = \left\{ \begin{array}{ll} 	1 & \mbox{with probability } 1/3\\
				3 & \mbox{with probability } 1/6\\
				4 & \mbox{with probability } 1/2
	\end{array}
	\right.
\]
and random variable $Y:S\to\nat$ has distribution 
\[
Y = \left\{ \begin{array}{ll} 	2 & \mbox{with probability } 3/4\\
				5 & \mbox{with probability } 1/4
	\end{array}
	\right.
\]
and $X$ and $Y$ are independent. 
\begin{problemparts}
\problempart
What is the probability generating function for $X$?  For $Y$?
\problempart
Let random variable $R:S\to\nat$ be given by $R=X+Y$.\\
Compute the probability generating function for $R$.\\
How is it related to the probability generating functions for $X$ and $Y$?
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
Let's generalize the result from the last problem.
Let $X:S\to\nat$ and $Y:S\to\nat$ be independent random variables
and let $R=X+Y$ be their sum.
\begin{problemparts}
\problempart
Show that the probability generating function $G(x)$
for $R$ is the product of those for $X$ and $Y$.
Is true in general if $X$ and $Y$ are not independent?
\problempart
Recall that $\Ex[R] = G'(1)$ where $G'$ denotes the derivative
with respect to $x$.  Verify that this gives $\Ex[R] = \Ex[X] + \Ex[Y]$.
\problempart
Show that $G''(1) = \Ex[R^2] - \Ex[R]$.
\problempart
Deduce that $\vari(R) = G''(1) + G'(1) - (G'(1))^2$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
Let's use the last result of the last problem to compute the variance
of ``the time until the first success''.
If each trial has probability $p$ of success, then random variable 
$R: S\to\nat$, denoting the trial in which the first success is obtained, 
has distribution $\Prob [R=k] = (1-p)^{k-1}p$.
\begin{problemparts}
\problempart
Compute the probability generating function $G_R(x)$
and check that $G_R(1) = 1$.
\problempart
Compute $\vari(R)$ as outlined in the previous problem.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem
Recall Problem 33 on page 492 of [MR], which was problem {\bf O9-8}
on Problem Set 9. You were asked to compute the expected sum of $k$
balls taken randomly {\em without} replacement from an urn of $n$ balls 
numbered $1$ through~$n$.
By linearity of expectation, this may be computed as the sum of the 
expected values of each of the balls taken from the urn.
Each ball is equally likely to be any of the $n$, and so has expected 
value $\frac{1}{n}(1+2+\cdots+n)=\frac{n+1}{2}$, so the expected sum is
$k(n+1)/2$ (just as the case {\em with} replacement).

Solve this problem in a different way, using $n$ indicator variables $B_i$,
one for each of the $n$ balls in the urn, to indicate the event that
ball $i$ is one of the $k$ balls selected.
\begin{problemparts}
\problempart
Write an equation for the sum of the $k$ balls using the indicator
variables $B_i$.
\problempart
Compute $\Prob[B_i = 1]$.
\problempart
Now use parts {\bf (a)} and {\bf (b)} to compute the expected value of the sum.
\\ (Of course you should get the same answer!)
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem
A cadet at the Naval Academy takes a multiple-choice test with 100 questions
on which he gets 2 points for every correct answer and $-1$ point for every 
incorrect answer.
He has mastered the material to only a small extent; he has a strategy for
making educated guesses in such a way that his expected score is~50.
Luckily, he has obtained a copy of a portion of the exam in advance,
so he will not score less than~$-50$.
We don't know how the cadet is making his guesses, so we don't know anything
about the distribution his score obeys except that the expected value is 50
and that his score is always in the range $-50$ to~$200$.
\begin{problemparts}
\problempart
Recall from lecture the converse of Markov's Inequality:
\begin{quotation}
For random variable $R:S\to\reals$, if $R$ is always at most $L$, then
\[  \Prob [ R > k] \geq {\Ex[R] - k \over L - k}. \]
\end{quotation}
Prove this using a proof by contradiction:  assume the conclusion is false
and reach a contradiction by showing that $\Ex[R] < \Ex[R]$.
\problempart
To repeat, we don't know what distribution the cadet's score obeys, but 
we can say something about it from the information we have.\\
What is a lower bound on the probability that the cadet scores more 
than~20?
\problempart
What is a lower bound on the probability that the cadet scores more 
than~50?\\
Why is this?
What distribution on the cadet's score achieves this probability?
\problempart
What is an {\em upper bound} on the probability that the cadet scores less
than~0?
\problempart
What is an upper bound on the probability that the cadet scores less
than~50?
\problempart
What is a {\em lower bound} on the probability that the cadet scores less
than~100?
\problempart
Suppose we are told that the cadet guesses in such a way that the
variance of the distribution on his score is~$625$.
What is an upper bound on the probability that he scores at least~100?\\
\problempart
Suppose we are told that the cadet guesses in such a way that the
sixth {\em central} moment of the distribution on his score is~$1,000,000$.
What is an upper bound on the probability that he scores at least~100?\\
You should do this by imitating the proof of Chebyshev's Theorem:
 Write 
	\[ \Prob [R-\Ex [R] > 50] \leq \Prob[(R-\Ex[R])^6 > 50^6] \]
 and use Markov's Inequality to get the upper bound for the latter.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\newpage
\problem
Recall from recitation the baseball-card-collecting problem, 
where you buy cards one at a time and each is uniformly distributed
from the entire set of $n$ possible cards.
We calculated the expected number of cards you will buy before collecting
the entire set.  To do this, we let random variable $R_i$ denote
the number of cards you buy to get a new card if you already have $i$ 
different cards.  The total number of cards you buy is therefore
$R = \sum_{i=0}^{n-1} R_i$ and $\Ex[R] = \sum \Ex[R_i]$.
$R_i$ obeys the distribution from the last problem with $p={n-i\over n}$,
so $E[R_i] = {n\over n-i}$.  So 
\[
\Ex[R] = \frac{n}{n} + \frac{n}{n-1} + \cdots + \frac{n}{1} =
	n\left( \frac{1}{n} + \cdots + 1\right) \sim n\ln n.
\]
Calculate the variance of $R$ using the calculation from the last
problem and the fact that 
$\vari(X+Y) = \vari(X) + \vari(Y)$ for $X,Y$ independent.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
Suppose you are offered a betting game in which you keep flipping a fair coin
until you get a head and if you flip the coin $k$ times without getting a head,
you win $\$ 2^k$.
If the game costs \$1 to play, what is your expected return (net winnings)?\\
Would you be willing to play this game?
(If so, please stop by NE43-370 any time and ask for Ravi.)
Would you be willing to play this game if it cost \$1000?
(If so, please stop by NE43-371 any time.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
Suppose you flip a fair coin 100 times.
What is an upper bound on the probability 
that the number of heads is at least 70\ldots
\begin{problemparts}
\problempart
\ldots according to Markov's Inequality?
\problempart
\ldots according to Chebyshev's Inequality?
\problempart
\ldots according to the upper bound for binomial distributions 
	derived in recitation?\\
	(Get a strict upper bound by using the multiplicative factors of
	$\frac{1-\alpha}{1-2\alpha}$ to account for the case that 
	there are strictly more than 70 heads, 
	and $(\frac{n}{e})^{\frac{1}{12n}}$ to adjust Stirling's 
	approximation.)  \\
	(This part requires a calculator, which won't be allowed on the
	exam.)
\end{problemparts}	

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
When designing VLSI circuits, a good rule of them is that the
probability that the circuit will work is $e^{-pA}$ for some constant $p$,
where $A$ is the area of the circuit.  Give a justification for this rule
under the assumption that every unit of area on the chip fails independently
with probability $p$ and that the circuit will fail if any unit of area fails.
%   Idea we want is prob of working is $(1-p)^A$ which is at most $e^{-pA}$.


\end{problems}
\end{document}
