\documentstyle[12pt,amssymb]{article}
\input{/a/class/6.042/spring95/macros-course}

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}

% \setcounter{page}{0}
\begin{document}
\examinitials{Final Exam Solutions}{May 26, 1995}

\begin{closeitemize}
\item The grades will be available after Monday 3pm from Professor 
Rivest's secretary Be. Her phone number is 253-6098 and email address
is {\tt be@theory.lcs.mit.edu}.
\end{closeitemize}

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem

A woman rolls a fair die to obtain a result $X$, and then flips a fair coin 
$X$ times. She reports getting a total of $2$ heads.  
Compute 
% Estimate    why only ``estimate''  the calculations are easy.  -steve
the probability that she observed $X=5$.  Show your work.

Let $Y$ be the total number of heads in the $X$ coin flips. 
We need to calculate $P(X=5 \mid Y=2)$. 	By Bayes' Rule:
\begin{eqnarray*}
P(X=5 \mid Y=2)&=&\frac{P(Y=2 \mid X=5) \cdot P(X=5)}
		{\sum_{i=1}^{6} P(Y=2 \mid X=i) \cdot P(X=i)}
\;\;\left( = \frac{P(X=5 \;\& \;Y=2) }{P(Y=2)} \right) \\
	& &	\\
&=& \frac{{5 \choose 2} \left(\frac{1}{2} \right)^5 \cdot \frac{1}{6}} 
	 {\sum_{i=2}^{6}{i \choose 2}
		\left( \frac{1}{2} \right)^i \cdot \frac{1}{6}} \\
	&=&  \frac{10 \times 2}{2^4+3\cdot 2^3+6\cdot 2^2+10\cdot 2+15} \\
	&=& 20/99.
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Let $X$ and $Y$ be independent random variables which take on only positive
values. Prove or disprove:  %  they should know how to ``disprove''  -steve
\[ E(X/Y)=E(X)/E(Y)	\]
(You may assume that $E(X/Y), E(X)$, and $E(Y)$ are all well-defined and 
finite positive quantities. Note: $0$ is not a positive number.)

We will disprove this by giving a counter example: \\
Let $P(X=3)=P(X=4)= 1/2$ and $P(Y=1)=P(Y=2)= 1/2$, with $X$ and $Y$ 
independent. 
$X/Y$ thus has value $\frac{3}{2}, 3, 2, 4$ each with probability 
$\frac{1}{4}$. 
Thus, $E(X/Y)=(1.5+3+2+4)/4=2.625$. 
But $E(X)=(3+4)/2=3.5$, $E(Y)=(1+2)/2=1.5$. 
So $E(X)/E(Y)=3.5/1.5=2.33 \neq E(X/Y)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
In how many ways can $r$ integers
be selected from the set $\{1,2, \cdots, n\}$ so that no two are consecutive?

$\displaystyle{n-r+1 \choose r}$ for $r \leq n/2$ (and 0 for $r>n/2$).

That is, the number of ways of selecting $r$ numbers from $\set{1\ldots n}$
with no two consecutive is the same as the number of ways
of selecting $r$ numbers from $\set{1\ldots n-(r-1)}$ in any fashion.
Note that selecting a number $k$ in the no-two-consecutive fashion 
rules out two numbers---$k$ and $k+1$.
So it is easy to construct a bijection between these two sets of possiblities:
the ``arbitrary-fashion'' set 
$\set{x_0, x_1, x_2, \ldots, x_{r-1}}\subseteq \set{1,\ldots n-(r-1)}$ 
corresponds to the no-two-consecutive set 
$\set{x_0, x_1+1, x_2+2, \ldots, x_{r-1}+(r-1)}\subseteq \set{1,\ldots, n}$.

\remove{
First if $r>\frac{n}{2}$, there is no way to select $r$ integers from 
$n$ without two being consecutive. If $r \leq \frac{n}{2}$, we claim that
the solution is $\displaystyle{n-r+1 \choose r}$, the number of ways to 
put $r$ black balls and $n-r$ white balls on a line such that no black balls 
are adjacent to each other. (this is easy to see using ball and bin argument.
$n-r$ white balls form $n-r+1$ bins and you choose $r$ bins to throw in
one black ball each.) Why? Because there is a one-to-one correpondence
between selecting numbers and lining up the balls. You can think of the
$n$ numbers as $n$ balls on a line. You color a ball black if it is selected
and white if not. Then for each way you select the numbers, you have a unique
permutation for the black and white balls.  And for each permutation of balls,
 we can number the balls from left to right as $1,2, \cdots, n$ and the
 numbers correspond to the black balls that are to be selected.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem

The weather in a certain city is somewhat predictable: it is either
sunny or rainy. If it rains one day then it is sunny the
following day with probability $1/3$. If it is sunny one day
then it rains the following day with probability $1/3$. 

Given that it is sunny today, find the average number of sunny
days for the next $n$ days, starting tomorrow.  

Let $X_i=1$ if the $i$th day is sunny and $0$ if rainy. Let $p_i=P(X_i=1)$.
Since 
\[P(X_i=1)=P(X_i=1 \mid X_{i-1}=0) \cdot P(X_{i-1}=0)
	+P(X_i=1 \mid X_{i-1}=1) \cdot P(X_{i-1}=1),
\]
and we are given that 
\[
P(X_i=1 \mid X_{i-1}=0)=P(X_i=0 \mid X_{i-1}=1)=1/3,
\]
we have 
\[
p_i=\frac{1}{3}(1-p_{i-1})+\left(1-\frac{1}{3}\right)p_{i-1}
	=\frac{1}{3}+\frac{1}{3}p_{i-1}. 
\]
Today is sunny, so have $p_0=1$. 
To solve the recurrence, we first solve the homogeneous part. 
$p_i=\frac{1}{3} p_{i-1}$. 
The solution is clearly $p_i= c_1\left( \frac{1}{3} \right)^{i}$. 
Now try $p_i= c_1\left( \frac{1}{3} \right)^{i}+c_2$ to solve for the 
nonhomogeneous part. 
We get $c_2=\frac{1}{2}$. 
Using initial condition $p_0=1$, we get $c_1=\frac{1}{2}$.
So, $p_i=\frac{1}{2}+\frac{1}{2}\left( \frac{1}{3} \right)^{i}$.
The expected number of sunny days is 
\[
E\left(\sum_{i=1}^{n}X_i\right) 
= \sum_{i=1}^{n}p_i = \frac{1}{2}n+\frac{1}{2}\cdot
  \sum_{i=1}^n \left(\frac{1}{3}\right)^i = \frac{1}{2}n+\frac{1}{4}
	\left(1- \left(\frac{1}{3} \right)^n\right). 
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
A boolean formula is said to be in 3-CNF if it is in conjunctive
normal form and each clause contains exactly $3$ distinct literals.  For
example, 
\[
(x_1 \vee \lnot x_2 \vee x_3) \wedge (\lnot x_1 \vee x_2 \vee x_4)
\]
is in 3-CNF.  Prove that if $\varphi$ is a formula in 3-CNF
then there is an assignment that satisfies at least $7/8$ of its clauses.
(Hint: Use the probabilistic method.)

Consider a random assignment where each variable $x_i$ has probability
$\frac{1}{2}$ of being true.  Then each clause $x_i \vee  x_j \vee x_k$, 
has probability at most $\frac{1}{8}$ of being false (only if none of
the three literals is satisfied). By linearity of expectation, 
the expected number of clauses satisfied is $7/8$. 
(Notice the events ``clause 1 is satisfied'' and ``clause 2 is satisfied''
may be highly dependent.)
It follows that some  assignment achieves the expectation and thus
satisfies at least $7/8$ of the clauses.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem
Let $f$ be a function chosen uniformly at random from the set of all 
functions from $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$.
Let random variable $R$ denote the cardinality of the range of~$f$.
\bparts
\ppart What is the expected value of $R$? 

Let $X_i$ denote the indicator variable of the event $i$ is in 
the range of $f$, then $R = \sum_{i=1}^{n}X_i $. 
Since the total number of functions from set $A$ of size
$a$ to set $B$ of size $b$ is $b^a$, ($b$ choices for each $f(i), i \in A$)
the number of functions from 
$\{1,\ldots,n\}$ to $\{1,\ldots,n\}$ is $n^n$ and  the number of 
functions from  $\{1,\ldots,n\}$ to $\{1,\ldots,n\}\backslash \{i\}$
 is $(n-1)^n$. So, 
\[P(X_i=0)=\frac{(n-1)^n}{n^n} = (1-1/n)^n \approx e^{-1} \]
and
\[
E(R) 	= E\left(\sum_{i=1}^{n}X_i\right) 
	= \sum_{i=1}^{n} E(X_i)
	= \sum_{i=1}^{n}P(X_i=1)
	\approx n(1-e^{-1}) 
\]
\ppart What is the variance of $R$?
\begin{itemize}
\item Use the principle of inclusion/exclusion to compute $P(X_iX_j = 0)$.
\begin{eqnarray*}
P(X_iX_j=0) &=& P(X_i=0)+P(X_j=0)-P(X_i=X_j=0) \\
 	&\approx & e^{-1} +e^{-1} -(n-2)^n/n^n \\
	&=& 2e^{-1}-e^{-2}
\end{eqnarray*}

\item Compute ${\rm Cov}(X_i,X_j)$.

\begin{eqnarray*}
{\rm Cov}(X_i,X_j) &=& E(X_iX_j)-E(X_i)E(X_j) \\
	&=& \left(P(X_iX_j=0)\cdot 0+P(X_iX_j=1)\cdot 1\right) 
		- P(X_i=1)P(X_j=1) \\
	&\approx & \left(1-2e^{-1}+e^{-2}\right)-(1- e^{-1})^2 \\
	&=& 0
\end{eqnarray*}

\item Compute ${\rm Var}(R)$
\begin{eqnarray*}
{\rm Var}(R) &=& {\rm Var}\left(\sum_{i=1}^{n}X_i\right) 
	= \sum_{i=1}^{n}{\rm Var}(X_i) 
		+\sum_{i=1}^{n}\sum_{j=1}^{n}{\rm Cov}(X_i,X_j) \\
	&=& \sum_{i=1}^{n}\left(P(X_i=1)\cdot (1-E(X_i))^2
		+P(X_i=0)\cdot (0-E(X_i))^2\right)+ 0\\
	&\approx& \sum_{i=1}^{n}
		\left( 	(1-e^{-1})\cdot (e^{-1})^2
			+ e^{-1}\cdot(1-e^{-1})^2 \right) \\
	&=& n e^{-1}(1-e^{-1}).
\end{eqnarray*}
\end{itemize}

\newpage
\ppart What can you say about $P(R - E(R) > \lambda \sqrt{n})$?

We cannot use Chernoff bound here because the $X_i$'s are not independent.
But we may still use Chebycheff's bound, 
$ P(|R-E(R)| > \lambda \sigma_R) \leq 1/\lambda^2$.
Since $\sigma_R \approx \sqrt{ne^{-1}(1-e^{-1})}$, 
we have 
\begin{eqnarray*}
P(R-E(R)> \lambda \sqrt{n}) 
& \approx & P( R-E(R)> {\textstyle
	\frac{\lambda}{(e^{-1}(1-e^{-1}))^{1/2}}} \cdot \sigma_R ) \\
& \leq & P( |R-E(R)| > {\textstyle
	\frac{\lambda}{(e^{-1}(1-e^{-1}))^{1/2}}} \cdot \sigma_R ) \\
& \leq & \frac{e^{-1}(1-e^{-1})}{\lambda^2}.
\end{eqnarray*}

\remove{
\[
\sigma_R = \sqrt{{\rm Var}(R)} 
	\approx \sqrt{e^{-1}(1-e^{-1})} \cdot \sqrt{n} 
\]
\begin{eqnarray*}
P(R-E(R)> \lambda \sqrt{n}) &<& P(|R-E(R)| > \lambda \sqrt{n}) \\
	&=& P(|R-E(R)| > \frac{\lambda}{\sqrt{1-e^{-1}}} \sigma_R) \\
	&\leq & \left( \frac{\sqrt{1-e^{-1}}}{\lambda} \right)^2 
		= (1-e^{-1})/{\lambda}^2
\end{eqnarray*}
}
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
\mbox{} 

\thm 
Let $G$ be a tree (a connected acyclic undirected graph) on $n$ vertices.
Let $k\geq 2$ be a fixed integer.  
The number of ways to color $G$ with $k$ colors (so that no two adjacent
vertices get the same color) is $k(k-1)^{n-1}$.
\ethm

\remove{
Intuitively, if we color the tree from root to leaves, at each node,
the only restriction is that the color has to be different from 
its parent. Therefore, we have $k$ ways to color the root
and $k-1$ ways to color any other nodes. So the solution is $k(k-1)^{n-1}$.
}
\pf
By induction on $n$.
For $n=1$, there are clearly $k$ ways to color~$G$.\\

For the inductive step, $|G|=n$, 
we suppose that any tree with $n-1$ vertices can be colored in 
$k(k-1)^{n-2}$ ways. 
\begin{claim}
$G$ has a leaf (a vertex of degree 1).
\end{claim}
\pf
Every vertex has degree at 
least 1 (since $G$ is connected) and if $G$ had no leaf, the sum of the 
degrees of the vertices of $G$ would be at least $2n$, but $G$, 
being a tree, has $n-1$ edges and therefore the sum of the degrees of its 
vertices is exactly $2(n-1)$.
\epf

Removing a leaf from $G$ leaves a tree with $n-1$ vertices.
Any coloring of $G$ may be obtained by coloring these $n-1$ vertices 
``first'' and then coloring the leaf.
By the inductive hypothesis, the nodes of this tree may be colored in 
$k(k-1)^{n-2}$ ways.
For each such coloring, there are exactly $k-1$ ways to color the leaf
yet uncolored, since it only has one neighbor.
Thus, the number of ways to color $G$ is 
 $(k-1) \cdot k(k-1)^{n-2} = k(k-1)^{n-1}$.
\epf

\remove{
Assume there are $k(k-1)^{n-2}$ ways to color a tree with $n-1$ nodes.
Then for a tree with $n$ nodes, there must exist at least
one leaf. The leaf  is connected to only one node(its parent) 
in the tree. Remove the
leaf first, then by induction we have $k(k-1)^{n-2}$ ways to color 
the remaining $n-1$ nodes. For any given coloring, add in the leaf,
 pick a color different from its parent.
So it has $k-1$ choices. Therefore, the total number of ways to color the
tree is $(k-1) \cdot k(k-1)^{n-2} = k(k-1)^{n-1}$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem
Rank the following functions by their orders of growth.
That is, order the functions $f_a, f_b, f_c, f_d$ so that
\[
f_a = O(f_b) \;\;\mbox{ and } \;\;
f_b = O(f_c) \;\;\mbox{ and } \;\;
f_c = O(f_d).
\]
Justify your answers and say whether the $O$'s are asymptotically tight 
or if they can be replaced by $o$'s.

\begin{itemize}
\item $f_1(n)=$ the number of undirected (loop-free) graphs on 
$\{1,\ldots,n\}$.
\item $f_2(n) =$ the number of binary relations on $\{1,\ldots,n\}$.
\item $f_3(n) =$ the number of equivalence relations on $\{1,\ldots,n\}$.
\item $f_4(n) =$ the number of $n \times n$ $(0,1)$-matrices where one-quarter 
of the entries are 1's.
\end{itemize}

$f_1(n) = 2^{{n \choose 2}} = 2^{n(n-1)/2}$ \\
since each of the
$n \choose 2$ edges may be either be present or not.

$f_2(n) = 2^{n^2}$ \\
since a binary relation on $\{1,\ldots,n\}$
is nothing more than a subset of $\{1,\ldots,n\} \times \{1,\ldots,n\}$.

$f_3(n) = B_n = 2^{\Theta(n \lg n)}$ \\
since an equivalence relation
is merely a partition of $\{1,\ldots,n\}$, and the number of partitions
of $\{1,\ldots,n\}$ is $B_n$, the $n$th Bell number. 
(The asymptotic value of $B_n$ was given in lecture, but it is easy 
to see that $B_n \leq n^n = 2^{n \lg n}$, which is 
sufficient for this problem.)

$f_4(n) = {n^2 \choose n^2/4} = 2^{H(\frac{1}{4}) n^2 - \Theta(\lg n)}$. \\

Comparing the exponents, we see that 
\begin{itemize}
\item $\lg f_1 = \frac{1}{2} n^2 - \frac{1}{2} n$,
\item $\lg f_2 = n^2$,
\item $\lg f_3 = \Theta(n \lg n)$, and 
\item $\lg f_4 = H\left(\frac{1}{4}\right) n^2 - \Theta(\lg n)$, 
\end{itemize}
where $H(1/4) > 1/2$ because the entropy function $H(x)$ is concave-down.
Thus, we see that the proper ranking is $f_3, f_1, f_4, f_2$:
\[
f_3 = o(f_1) \;\;\mbox{ and } \;\;
f_1 = o(f_4) \;\;\mbox{ and } \;\;
f_4 = o(f_2), 
\]
with $o$'s since $2^{c_1 n^2}/2^{c_2 n^2} = 2^{(c_1-c_2)n^2}$, which goes
to 0 with $n$ if $c_1-c_2 < 0$.

\remove{
Because 
\[\lg f_3 = n \lg n \;\mbox{ and } \; \lg f_1 = n(n-1)/2 \]
$\lg f_3 = o(\lg f_1)$, therefore, clearly, $f_3 = o(f_1)$.
Also
\[\lg f_4  = \theta (2n^2 - \frac{3}{4} \lg 3 n^2 ) = \theta(.8 \lg n^2)
\;\mbox{ and } \; \lg f_2 = n^2 \]
If $g(n) = 2^{an}$ and $h(n) = 2^{bn}$ where $a=b-c$ for some $c>0$, 
then $h(n) = 2^{an} \cdot 2^{cn}$.  Clearly $g(n) = o(h(n)$.
So it is easy to see the ranking between $f_1, f_4,$ and $f_2$.
(Here note that in the calculation of $f_4$, I used $\theta$ notation all the
time.  As we have been emphasizing in the homework, we can not carry around 
$\theta$ in the calculation. Sometimes you could get wrong solution. 
 You can only use it as an educated guess which needs to be confirmed 
by formal proof, namely start from the definition of $\theta$. 
I'll leave that part to you.)
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{problems}

\end{document}

