\documentclass[11pt]{article}
\usepackage{amsmath}
\input{/a/class/6.042/fall99/inputs/macros-course}

\renewcommand{\solution}[1]{}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}
\def\medblank{\rule[-2pt]{1in}{.5pt}}
\def\relz{\mathbin{\, \rho \,}}

\newcommand{\emptybox}[3][]{%
\begin{center}
    \leavevmode\fbox{%
        \vbox to #3{%
            \vfil
            \hbox to #2 {\hfil#1\hfil}%
            \vfil
        }%
    }%
\end{center}
}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\begin{document}

\handout{final}{Final Exam}{December 14, 1999}

\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your TA}:
\begin{center}
\begin{tabular}{lll}
Mary    & Kyle & Sarfraz\\
Albert  & Mike  & Yana\\
Alantha & Ryan & Victor\\
\end{tabular}
\end{center}

\medskip

\begin{closeitemize}
\item This exam is \textbf{closed} book; no calculators either.  A
two-sided sheet of prepared notes is allowed.
\textbf{Your answers may cite without proof any of the results from lecture
or handouts.}

\item There are 14 problems totaling 200 points.  The first eight are worth
13 points each, the last 6 are worth 16 points each.

%The parts of a
%problem count equally unless noted otherwise.

\item Put your name on the top of {\bf every} page.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.

\textbf{You need not show your work}: a correct short answer with no
explanation will receive full credit.  But part credit for incorrect
answers can only be given if the work leading to the answer is clearly
shown.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline & & & \\
1 & 13  & & \\ & & & \\\hline & & &\\
2 & 13  & & \\ & & & \\\hline & & &\\
3 & 13  & & \\ & & & \\\hline & & &\\
4 & 13  & & \\ & & & \\\hline & & &\\
5 & 13  & & \\ & & & \\\hline & & &\\
6 & 13  & & \\ & & & \\\hline & & &\\
7 & 13  & & \\ & & & \\\hline & & &\\
8 & 13  & & \\ & & & \\\hline & & &\\
9 & 13  & & \\ & & & \\\hline & & &\\
10 & 16  & & \\ & & & \\\hline & & &\\
11 & 16  & & \\ & & & \\\hline & & &\\
12 & 16  & & \\ & & & \\\hline & & &\\
13 & 16  & & \\ & & & \\\hline & & &\\
14 & 16  & & \\ & & &\\
\hline \hline & & &\\
Total & 200 & & \\
& & &\\
\hline
\end{tabular}
\end{center}

\newpage

\begin{problems}

\section*{13 Point Problems}

\problem \textbf{Injections and Cardinality}

\bparts

\ppart

Let $f:D \to D$ be a function from some nonempty set $D$ to itself.
In the following propositions, $x$ and $y$ are variables ranging over $D$,
and $g$ is a variable ranging over functions from $D$ to $D$.  Circle all
of the propositions that are equivalent to the proposition that $f$ is an
\emph{injection}:

\begin{enumerate}
\item $x =y \vee f(x) \neq f(y)$
\item $x =y \implies f(x) = f(y)$
\item $x \neq y \implies f(x) \neq f(y)$
\item $f(x) =f(y) \implies x = y$
%\item $\forall x \forall y(f(x) \neq f(y))$
\item $\neg[\exists x\exists y(x \neq y \wedge f(x)= f(y))$
\item $\neg[\exists z \forall x(f(x) \neq z)$
\item $\exists g \forall x (g(f(x))=x)$
\item $\exists g \forall x (f(g(x))=x)$
\end{enumerate}

\solution{

a,c,d,e,g

}

\eparts


We have proved that the infinite set of real numbers is ``strictly
bigger'' than the infinite set of integers, and the set of integers is
``strictly bigger'' than any finite set.

\bparts

\ppart State precisely what it means to say a set $A$ is ``strictly
bigger'' than another set $B$.

\solution{

There is no injection from $A$ to $B$.  Alternatively, there is no
bijection between $A$ and $B$, but there is an injection from $B$ to $A$.
}

\vspace{1in}

\ppart Give an example of a set that is strictly bigger than the set of
real numbers.

\solution{$P(\reals)$.}

\vspace{1in}

\eparts


\iffalse
\problem \textbf{Expectation}

The blunder in the published probabilistic analysis comparing CISC to RISC
architecture performance was the assumption that
\[
\expect{\frac{R}{C}} = \frac{\expect{R}}{\expect{C}}
\]
for random variables $R$ and $C$.  Give a simple example of two random
variables $R$ and $C$ for which the assumption is not true.

\solution{

Let $R \equiv 1$, and $C \eqdef 1\text{ or }2$ with equal
probability.  Then E[R]=1, E[C]=3/2, yield E[R]/E[C]=2/3.  But
E[R/C]=E[1/C]=3/4.

}

\vspace{2in}

\fi


\problem  \textbf{Modular Arithmetic}

\bparts

\ppart
Prove that there is no $x$ such that
\[
117\cdot x \equiv 1 \pmod{213}.
\]

\solution{

$117\cdot x \equiv 1 \pmod{213}$ iff $117 \cdot x + 213 \cdot y = 1$ for
some integer $y$.  This is equivalent to having $\gcd(213,117) = 1$, but
by Euclid's algorithm, $\gcd(213,117) = 3$.

}

\vspace{2in}


\ppart
Find an integer $x$ for which
\[
123 \cdot x \equiv 1 \pmod{2347 } \brule{1in}
\]

\solution{

$x = -706$ works because $1=37\cdot 2347 + (-706)\cdot 123$.  }

\vspace{2in}

\eparts


\problem \textbf{Invariants} Every Invariant Predicate for a state machine
is determined by the states that satisfy the Invariant.  For example, the
identically \texttt{true} Invariant determines the set of all states, and
the identically \texttt{false} Invariant determines the empty set of
states.  How many other Invariant Predicates does the following state
machine have?  What are the state sets for each of them?  States $Q \eqdef
\set{A,B,C,D,E,F,G,H}$, transitions:
\[
\set{(A,B), (B,C), (C, A), (D,E), (E,F) (F,D), (C,D), (G,A), (B,H)}.
\]

\solution{

$\set{ABCDEFH}, \set{DEF}, \set{H}$.

}


\vspace{3in}


\problem \textbf{Stars and Bars} A juggler plans to juggle 11 rings for his
finale.  In his bag are 20 identical red rings, 30 identical blue rings,
and 40 identical white rings.  He must select at least one of each color to
be patriotic.  An example of a patriotic choice of 11 rings would be: 3
red, 2 white, and 6 blue.  How many different patriotic choices are there
for the 11 rings?  \emptybox{1in}{0.6in}

\solution{

This is the same as asking how many ways there are to arrange 11 stars and
two bars such that there is at least one star in each of the three groups
delimited by the bars.  Reserving three stars for this purpose leaves 8
stars and 2 bars, so there are
\[
\binom{8}{2}.
\]
Note that the initial number of red, white, and blue rings available to
the juggler is irrelevant as long as there are at least nine of each.
}

\vspace{1in}


\problem Define a binary relation $\relz$ on real-valued random variables
$X,Y$ by the rule that $X \relz Y$ iff $\prob{X \neq Y} = 0$.  Prove that
$\relz$ is an equivalence relation.

\solution{

$\relz$ is \emph{reflexive} because the event $X \neq X$ is the empty
event---which has probability zero.

$\relz$ is \emph{symmetric} because the event $X \neq Y$ is the same as the
event $Y \neq X$, so if either of these events has probability zero, then
they both do.

To prove $\relz$ is \emph{transitive}, suppose $X \relz Y$ and $Y \relz Z$.  We
must show that if $X(s) \neq Z(s)$ for some sample point $s$, then
$\prob{s} = 0$.  This implies $\prob{X \neq Z} = 0$, so $X \relz Z$ as
required.

So suppose $X(s) \neq Z(s)$.  If also $X(s) \neq Y(s)$, then $\prob(s) =
0$ because $X \relz Y$.  Otherwise, $Y(s)= X(s) \neq Z(s)$, so $Y(s) \neq
Z(s)$, and hence $\prob{s} = 0$ in this case as well because $Y \relz Z$.

}

\vspace{3in}


\problem \textbf{Counting with Repetition}

\bparts

\ppart How many distinguishable ways are there to rearrange the letters in
\begin{center}
``{\bf INSTRUCTOR}''?
\end{center}
\emptybox{1in}{0.6in}

\solution{There are $10!$ ways to arrange 10 distinct letters, but we have two
T's and two R's, so this overcounts by a factor of $2!$ for the T's
and by a factor of $2!$ for the R's.  The correct answer is
$$\frac{10!}{2! 2!} = 907200$$ 
}

\vspace{1in}

\ppart \dots with all vowels consecutive?
\emptybox{1in}{0.6in}

\solution{

Let the letter V represent the block of vowels, treated as a single
unit.  How many ways can we rearrange the letters NSTRCTRV?  There are
$8!$ ways to arrange 8 distinct letters, but we have two T's and two
R's, so this overcounts by a factor of $2! 2!$.  So there are
$\frac{8!}{2!2!}$ ways to arrange the letters NSTRCTRV.  There are
three vowels, so there are $3!$ ways to arrange the vowels within the
block V, so the number of ways to arrange the letters of INSTRUCTOR
with all the vowels consecutive is $$3! \frac{8!}{2!2!} = 60480$$

(Alternatively: $\frac{7!}{2!2!}$ ways to arrange the consonants,
and $8$ places 
to insert the $3$ vowels within these $7$ consonants.)

}

\vspace{1in}
\eparts


\problem \textbf{Conditional Probability.}

Boston is justly famous for its enthusiastic sports fans.  Surveys show
that 90\% of adult Bostonians are Celtics fans, and 75\% are Red Sox fans.
However, only 80\% of the Celtics fans are also Red Sox fans.  Now suppose
that an adult Bostonian is chosen at random from among those that are
\emph{not} Celtics fans.  What is the probability that such a person is a
Red Sox fan?  \emptybox{0.7in}{0.5in}

\solution{

Let $P$ represent the event that a Bostonian is a Red Sox fan, and $S$
represent the event that the resident is a Celtics fan.  Then 
\begin{eqnarray*}
\prob{P} & = & \prob{P  \mid  S} \prob{S} + \prob{P  \mid  \overline{S}}
                    \prob{\overline{S}}, \qquad \text{so}\\
\prob{P  \mid  \overline{S}} & = &
       \frac{\prob{P} - \prob{P  \mid  S} \prob{S}}{\prob{\overline{S}}} \\
& = & \frac{0.75 - (0.80 \cdot 0.90)}{1 - 0.9} \\
& = & 0.3.
\end{eqnarray*}

}

\vspace{2in}



\problem \textbf{Markov Bound}

A herd of 350 cows is stricken by an outbreak of "mad cow" disease.  The
disease lowers the normal body temperature of a cow, and a cow will die if
its temperature goes below 90 degrees F.  The disease epidemic is so
intense that it lowered the average temperature of the herd to $45$
degrees.  Body temperatures as low as $20$ degrees, but no lower, were
actually found in the herd.

\bparts

\ppart State a best possible upper bound on the number of cows whose
temperature is high enough to survive.    \emptybox{0.7in}{0.5in}

\solution{

Let $R$ be the temperature.  Apply Markov's Bound to $R-20$:
\[
\prob{R \geq 90} = \prob{R-20 \geq 70} \leq \expect{R-20}/70 = (45-20)/70 = 5/14,
\]
so at most $(5/14)350 = \textbf{125}$ cows have temperature $\geq 90$
degrees.

}

\vspace{2in}

\ppart Give an example set of temperatures that achieve your bound.

\solution{

Of the 350 cows, 125 have 90 degree temperature and 225 have 20
degree temperature.  The mean is
\[
(125 \cdot 90 + 225 \cdot 20)/350 = 45,
\] as required.
}

\vspace{2in}

\eparts


\section*{16 Point Problems}


\problem \textbf{Linear Recurrence}

You just moved into your new house and you are throwing a housewarming
party.  You invite 5 people on the first day and tell them to invite their
friends.  Each newly invited person invites 2 people the day after they
are invited.

\bparts

\ppart
Give a recurrence describing the number of people invited by the $n$th
day.

\solution{
You know that the number of people for each day will
equal the number of people who were invited from the day before in
addition to 2 new guests for each of the new people on the day before.
T(n) = T(n-1) + 2 [ T(n-1) - T(n-2) ] = 3 T(n-1) - 2 T(n-2) }

\vspace{1in}

\ppart Describe initial conditions for the recurrence.

\solution{ You know that T(0) = 0 since no one was invited on day 0 and
T(1) = 5, since you invited 5 people on the first day.}

\vspace{1in}

\ppart Give a closed form expression equal to the number of people invited
by the $n$th day.

\solution{ Solving this recurrence $a^2 = 3a - 2$ $a^2 - 3a + 2 = 0$
$(a-2) (a-1) = 0$ $a = 2$ or $1$

$T(n) = c2^n + b1^n = c2^n + b$

Plugging in the initial conditions, gives you two equations :
$T(0)=0=c+b$
$T(1)=5=c*2 + b$
$c = 5, b = -5$

$T(n) = (5 * 2^n) - 5  $

}

\vspace{1.5in}

\eparts


\problem {\bf Binomial Identity.}  Suppose you want to choose a team of
$m$ people from a pool of $n$ people for your startup company, and from
these $m$ people you want to choose $k$ to be the team managers.  Prove
that you can do this in
\[
\binom{n}{k}\binom{n-k}{m-k}
\]
ways.

\solution{
First, brute-force: To choose m out of n and then k out of chosen m,
can be done in 
$\binom{n}{m}\binom{m}{k}$ ways. Now, 
\begin{eqnarray*}
\binom{n}{m}\binom{m}{k}
& = & \frac{n!}{m! (n-m)!} \frac{m!}{k! (m-k)!} \\
& = & \frac{n!}{(n-m)! k! (m-k)!} \\
& = & \frac{n! (n-k)!}{(n-m)! k! (m-k)! (n-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{(n-m)!(m-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{((n-k) - (m-k))! (m-k)!} \\
& = & \binom{n}{k}\binom{n-k}{m - k}
\end{eqnarray*} 


Another way to look at this.  
Instead of choosing first $m$ from $n$ and then $k$ from $m$, you could 
alternately choose the $k$ managers from the $n$ people and then
choose $m-k$ people to fill out the team from the remaining $n-k$ people.  This
gives you ${\binom{n}{k}}{\binom{n-k}{m-k}}$ ways of picking your team.  Since
you must have the same number of options regardless of which order you choose
to pick team members and managers in, 
${\binom{n}{m}} {\binom{m}{k}} = {\binom{n}{k}} {\binom{n-k}{m-k}}$.
}

\vspace{5in}


\problem \textbf{Trees and Structural Induction} A \emph{full binary tree}
with its {\it vertices} and {\it leaves} is defined inductively as
follows:

\begin{itemize}

\item A simple graph with one vertex is a full binary tree.  The vertex is
called the \emph{root} of the tree.  The \emph{set of leaves} of the tree
is the set whose sole member is the root.  The \emph{ set of vertices} of
this tree is the same as the set of leaves.

\item If $B_1$ and $B_2$ are full binary trees such that the vertices of
$B_1$ and $B_2$ are disjoint, then a simple graph consisting of a new
vertex with edges from the new vertex to the roots of $B_1$ and $B_2$ is
also a full binary tree, $B$.  The \emph{root of $B$} is the new vertex.
The \emph{vertices of $B$} are exactly its root, the vertices of $B_1$,
and the vertices of $B_2$.  The \emph{leaves of $B$} are exactly the
leaves of $B_1$ and the leaves of $B_2$.

\end{itemize}

For example, a full binary tree with 5 nodes and 3 leafs is is shown in
Figure \textbf{INSERT FIGURE}.

Prove that for all full binary trees $B$,
\[
\card{\text{leaves}(B)} = \frac{\card{\text{vertices}(B)}+1}{2}.
\]

\solution{The induction hypothesis, $P(B)$, is the equation to be proved. 

\textbf{Base case} $P(\text{single root})$: there is 1 leaf, 1 vertex and
indeed $1=(1+1)/2$.

\textbf{Inductive step} $B$ has a root $r$ connected to two full binary
trees $B_1$, $B_2$; the induction hypothesis is that $P(B_1)$ and $P(B_2)$
are true. So
\begin{eqnarray*}
\card{\text{leaves}(B)} & = & \card{\text{leaves}(B_1) \union \text{leaves}(B_2)}\\
 & = & \card{\text{leaves}(B_1)} + \card{\text{leaves}(B_2)} \qquad \text{because
       vertices of $B_1$ and $B_2$ are disjoint}\\
 & = & \frac{\card{\text{vertices}(B_1)}+1}{2} +
       \frac{\card{\text{vertices}(B_2)}+1}{2} \qquad\text{by induction hypothesis}\\
 &= & 1 + \frac{\card{\text{vertices}(B_1)}+
                \card{\text{vertices}(B_2)}}{2}\\
 & = & \card{ \set{r} \union \text{vertices}(B_1) \union
             \text{vertices}(B_2)} \qquad \text{disjointness again}\\
 & = & \card{\text{vertices}(B)}
\end{eqnarray*}
}

\vspace{5in}


\problem \textbf{Chebyshev Bound}

A man has a pocketful of $n$ keys, exactly one of which will open the door to
his apartment.  He picks a random key from his pocket, tries to open the
door with it, and puts it back in his pocket if it doesn't work (no, he
isn't very together about key management).  He continues until he finds
the key that works.

\bparts

\ppart
What is the expected number of keys the man draws until he finds the right
one?  \hint Mean time to failure.  \emptybox{0.7in}{0.5in}
 
\solution{
The probability of picking the right key on each trial is $1/n$, so mean
time to failure is $1/(1/n) = n$.
}

\vspace{1in}

\ppart  What is the variance for the number of keys he picks?
\hint Some relevant summation formulas are in the Appendix.
\emptybox{1in}{0.7in}

\solution{The probability stays the same on all subsequent trials since
the picked key is always returned to the urn.  Thus
\[
\prob{T=k} = \left(\frac{n-1}{n}\right)^{k-1}\frac{1}{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$.

The variance of $T$ can be computed directly from the formula,
\[
\variance{T} = \expect{T^2} - \expectsq{T}.
\]
Again, by definition we have
\[
\expect{T^2} = \sum_{k=1}^\infty{k^2 pq^{k-1}}{.}
\]
We know that
\[
\sum_{k=1}^\infty{kq^k} = q\sum_{k=1}^\infty{kq^{k-1}} = \frac{q}{(1-q)^2}.
\]
Moreover,
\begin{eqnarray*}
\sum_{k=1}^\infty{k^2 q^{k-1}} &=& \sum_{k=1}^\infty{\frac{d\, k q^k}{dq}}\\
 &=& {1/q}\sum_{k=1}^\infty{k q^k}\\
 &=& {1/q}\frac{q}{(1-q)^2}\\
 &=& \frac{1}{(1-q)^2} + \frac{2q}{(1-q)^3} = \frac{1}{p^2} + 
\frac{2q}{p^3}{.}
\end{eqnarray*}
Finally, the expectation $\expect{T^2}$ is
\[
\expect{T^2} = p \left(\frac{1}{p^2} +\frac{2q}{p^3}\right) = 
\frac{1}{p} + \frac{2q}{p^2},
\]
and the variance is
\[
\variance{T}= 1/p + \frac{2q}{p^2} - \frac{1}{p^2} = \frac{q}{p^2} = n(n-1).
\]
}

\vspace{3in}

\ppart What is the Chebyshev upper bound on the probability that the man
will have to pick at least 100 keys?  Let $V$ denote the variance that you
were asked to calculate in the previous part, and express your answer as a
closed formula using $V$.
\emptybox{1in}{0.7in}

\solution{

One-way bound:
\[
\prob{K \geq 100} = \prob{K-n \geq 100-n} \leq \frac{V}{V+ (100-n)^2}.
\]

Also OK to use the regular two-way bound.

}

\vspace{1in}

\eparts


\problem \textbf{Random Graphs} A simple graph with 10 vertices is
constructed by randomly placing an edge between every two vertices with
probability $p$.  These random edge placements are performed
independently.

\bparts

\ppart What is the probability that a given vertex, $v$, of the graph has
degree two?  \emptybox{1in}{0.6in}

\solution{
$\binom{9}{2} \cdot p^2\cdot ({p-1})^7$.
}

\vspace{1in}

\ppart What is the expected number of nodes with degree two? \emptybox{2in}{1in}

\solution{
10 times the previous answer by linearity of expectations.
}

\vspace{2in}

\iffalse
\ppart Are $X_i$ and $X_j$ independent for $i\neq j$?  Prove
your answer.

\solution{
No.

Prob($X_i=9$ and $X_j=0$)=0 $\neq Prob(X_i=9)\cdot Prob(X_j=0)$

}
\fi

\ppart What is the expected number of cliques of size $k$, that is,
subgraphs isomorphic to the complete graph with $k$ vertices?  Express
your answer as a closed form formula involving binomial
coefficients. \emptybox{1.5in}{0.7in}

\solution{

The strategy for computing the expected number of cliques is again:
linearity of expectation.  Define an indicator random variable for every
possible $k$-clique.  Every $k$-subset of the $n$ nodes is a possible
$k$-clique, so there are $\binom{n}{k}$ such random variables.  The random
variable for a particular $k$-clique is 1 if the $k$-clique is found in
the graph and 0 if not, so its expected value is just the probability that
a particular $k$-clique occurs in the graph.  This happens if and only if
all $k$ nodes are connected by edges; there are $\binom{k}{2}$ such
edges, so the probability of a particular $k$-clique is
$p^{\binom{k}{2}}$.  Summing the expected values of all the $k$-cliques
gives the expected number of $k$-cliques:
\[
\binom{n}{k} p^{\binom{k}{2}}.
\]

}

\vspace{1in}

\ppart The previous result impliies an interesting fact which you may
assume without proof: if $p=1/2$, then the expected number of cliques of
size $2 \log n$ is greater than one.  Oddly, even though we can expect
there to be such a clique, no procedure is known to \emph{find} some
clique of size $2\log n$ in the graph---when there is one---that is much
more efficient than exhaustively searching through all possible subsets of
vertices of size $2 \log n$ and checking each subset to see if it is a
clique.  Circle each of the following expressions which correctly bounds
the number of subsets such an exhaustive search would examine:
\begin{enumerate}
\item $O(2^n)$
\item $O(n^2)$
\item $O(n^{\log n})$
\item $O(n^{2 \log n})$
%\item $\Theta(e^{\log^2 n})$
%\item $\Theta((\log n)^n)$
\end{enumerate}


\solution{

(a),(d).

The number of such subsets is
\[
\binom{n}{2 \log n} = \frac{P(n, 2 \log n)}{(2 \log n)!} < n^{2 \log n},
\]
and 
\[
\frac{P(n, 2 \log n)}{(2 \log n)!} > (\frac{(n- \log n)}{\log n})^{2 \log
n} > n^{(2- \epsilon) \log n} \neq O(n^{\log n}).
\]

}

\eparts



\problem We have three coins to flip: one has probability 3/4 of coming up
heads, another has probability 7/8 of coming up heads, and finally there
is one with probability 15/16 of coming up heads.  One of the three coins
is picked, and this coin is repeatedly tossed.

Explain a way to determine a number of tosses sufficient to allow
identification with 99\% confidence of the coin being tossed.  You do not
have to carry out the calculation, and you may cite without proof any of
the results from the Appendix or other course material.


\solution{

Identify the coin to be the one whose probability is closest to the
fraction of heads among $n$ flips.  This identification will be correct
99\% of the time if the probability that the actual fraction of heads in
$n$ flips differs from the expected fraction of heads by more than 1/32 in
at most 0.01.  We choose 1/32 because it is half the distance between the
two closest coin probabilities.

Let $S_n$ be the number of heads appearing in $n$ flips, so $S_n/n$ is the
fraction of heads.  We assume the successive flips are independent, so the
variance of $S_n/n$ is $1/n^2$ times the variance of $S_n$ which is $n$
times the variance of a Bernoulli variable whose probability was the
probability of heads in one flip.  We know the variance of a Bernoulli
variable is at most 1/4, so $\variance{S_n/n} = (1/n^2)(1/4)n = 1/4n$.
Chebyshev's bound implies that the probability that $S_n/n$ deviates from
its mean by 1/32 is at most $(1/4n)/(1/32)^2$.  Choose $n$ so this
quantity is at most 0.01.

Alternatively, observe that $S_n$ will have a Bernoulli distribution with
one of the three probabilities 3/4, 7/8, 15/16.  Using the bounds from
Lecture 21 on the tails of the binomial distribution, we could choose $n$
large enough that the probability that $\prob{\abs{S_n - pn} \geq n/32}
\leq 0.01$ for each $p = 3/4, 7/8,$ and 15/16.

}

\vspace{4in}


\end{problems}

\newpage

\section*{Appendix}

\subsection*{Graphs}

A \textbf{simple graph} is an undirected graph with no self loops and at
most one edge between any two nodes.

A \textbf{tree} is a connected, acyclic simple graph.

An \textbf{Eulerian circuit} in a graph is a path beginning and ending at
the same vertex and containing each edge exactly once.

The \textbf{complete graph}, $K_n$, is the simple graph with $n$ vertices and
with an edge between every two vertices.

The \textbf{degree} of a vertex in a graph is the number of edges at the vertex.

A \emph{connected component} of a simple graph is an equivalence class of
vertices under the ``is connected by a path to'' relation on pairs of vertices.

\subsection*{Partial Orders}

\textbf{Lexicographic order}, $\preceq$, on pairs of natural numbers is
defined by the rule that
\[
(n_1,n_2) \preceq (m_1,m_2) \quad \mbox{iff} \quad [(n_1 < m_1) \mbox{ or } (n_1
= m_1 \mbox{ and } n_2 \leq m_2)].
\]

\subsection*{Sums}

\[
\sum_{i=0}^n r^i = \frac{r^{n+1} - 1}{r-1}.
\]

\[
\sum_{i=0}^{n} ir^i = \frac{{r - (n+1) r^{n+1} + n r^{n+2}}}{(1-r)^2}.
\]

\[
\int \ln x dx = x \ln (x/e).
\]

\subsection*{Combinatorics}

\textbf{Stirling's formula}:
\[
n! \sim  \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n.
\]

\textbf{The Principle of Inclusion-Exclusion}:
\[
\card{A \union B} = \card{A}+ \card{B} - \card{A \intersect B}.
\]
For $n$ sets:
\[
\card{\Union_{i=1}^n A_i}
= \sum_{S \subset \set{1,\dots,n}}
           (-1)^{\card{S}} \card{\Intersect_{j \in S} A_j}.
\]

Probabilistic version:
\[
\prob{A \union B} = \prob{A} + \prob{B} - \prob{A \intersect B}.
\]

\[
\prob{\Union_{i=1}^n A_i}
= \sum_{S \subset \set{1,\dots,n}}
           (-1)^{\card{S}} \prob{\Intersect_{j \in S} A_j}.
\]

\begin{eqnarray*}
n!  & \eqdef & n \cdot (n-1) \cdots 2 \cdot 1\\
0!  & \eqdef & 1\\
P(n,r)  & \eqdef & n \cdot (n-1) \cdots (n - (r-2) \cdot (n - (r - 1))\\
C(n,r) = \binom{n}{r}  & \eqdef & \frac{n!}{r!\, (n-r)!}
\end{eqnarray*}


\subsection*{Markov \& Chebyshev Bounds}

Markov bound:
\[
\prob{R \geq x} \leq \frac{\expect{R}}{x}.
\]


Chebyshev bound: for $c \geq 0$,
\[
\prob{\abs{R - \expect{R}} \geq c\sigma_R} \leq \frac{1}{c^2}.
\]

The ``one-way'' version of Chebyshev bound: for $c \geq 0$,
\[
\prob{R - \expect{R} \geq c\sigma_R} \leq \frac{1}{1+c^2}.
\]


\subsection*{Weak Law of Large Numbers for Bernoulli Variables}

A \emph{Bernoulli variable} is a 0-1-valued random variable.  For any
event $A$, the \emph{index variable}, $I_A$, is the Bernoulli variable
which is 1 exactly when event $A$ occurs.

Let $G_1, G_2, \dots, G_n$ independent Bernoulli variables, each with the
same probability $p$ of being equal to one.  In this case, $G_i=G_i^2$, so
\[
\expect{G_i^2} = \expect{G_i} = \prob{G_i=1} = p,
\]
and
\[
\variance{G_i} = \expect{G_i^2} - \expectsq{G_i} = p - p^2 = p(1-p).
\]
Let
\[
S_n \eqdef \sum_{i=1}^n G_i,
\]

We can use the random variable $S_n/n$ to estimate $p$.  This estimator
$S_n/n$ is a random variable with two critical properties:
\begin{eqnarray*}
\expect{\frac{S_n}{n}} & = & \expect{G_i} = p,\\
\variance{\frac{S_n}{n}} & = & \frac{\variance{G_i}}{n} = \frac{p(1-p)}{n}.
\end{eqnarray*}

To prove this, note that by linearity of expectation
\[
\expect{\frac{S_n}{n}} = \frac{\expect{\sum_{i=1}^n G_i}}{n}
   = \frac{\sum_{i=1}^n \expect{G_i}}{n}
   = \frac{np}{n} = p.
\]

Also, since the $G_i$'s are independent, their variances will add, so
\begin{eqnarray*}
\variance{\frac{S_n}{n}} & = & (\frac{1}{n})^2 \variance{S_n}\\
& = & (\frac{1}{n})^2 \sum_{i=1}^n \variance{G_i}\\
& = & (\frac{1}{n})^2 n\variance{G_i}\\
& = & \frac{\variance{G}}{n}.
\end{eqnarray*}

Now Chebyshev's Bound tells us that
\begin{theorem*}
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
independent Bernoulli variables with the same probability $p$ of being
equal to one.
Then
\[
\prob{\abs{\frac{S_n}{n} - p} \geq x} \leq \frac{p(1-p)}{nx^2}.
\]
\end{theorem*}

Now if we fix $p$ and $x$ and let $n$ approach infinity, we conclude that
the Weak Law of Large Numbers holds:

\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{S_n}{n} - p} \geq x} = 0.
\]

\end{document}



\iffalse
\problem \textbf{State Machines}  %almost verbatim from F98 midterm

Three monks must evenly divide the monastery's collection of prayer beads.
Initially, monk $A$ has 5 beads, monk $B$ has 3 beads, and monk $C$
has 4 beads.  The monastic order has strict rules regarding the
exchange of prayer beads.  Only the following transactions are
allowed.

\begin{enumerate}

\item Monk $B$ may give a bead to monk $A$ at any time.

\item If $C$ has an odd number of beads, then monk $A$ may give a bead to
monk $B$.

\item If $C$ has an even number of beads or monk $A$ has at least two more
beads then monk $B$, then monk $C$ may give or take a bead from either
monk $A$ or monk $B$.
\end{enumerate}

\begin{problemparts}
\problempart Model the situation with a state machine.  Define the set of
states, the set of start states, and the set of transitions.

\solution{

The set of states $Q$ consists of all triples $(a, b, c)$ such that $a, b,
c \geq 0$ and $a + b + c = 12$.  The set of starts states $Q_0$ consists
of the single triple $(5, 3, 4)$.  The set $\delta$ contains six types of
transition:

\[
\begin{array}{rcll}
(a, b, c) & \rightarrow & (a+1, b-1, c) &
        \quad \text{($b > 0$)} \\
\\
(a, b, c) & \rightarrow & (a-1, b+1, c) &
        \quad \text{($a > 0$ and $c$ is odd)} \\
\\
(a, b, c) & \rightarrow & (a-1, b, c+1) &
        \quad \text{($a > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a, b-1, c+1) &
        \quad \text{($b > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a+1, b, c-1) &
        \quad \text{($c > 0$ and either $c$ is even or $a \geq b + 2$)} \\
(a, b, c) & \rightarrow & (a, b+1, c-1) &
        \quad \text{($c > 0$ and either $c$ is even or $a \geq b + 2$)}
\end{array}
\]
}

\vspace{2.5in}

\problempart  Prove that the monks can reach the state
where monk $A$ has 0 beads, monk $B$ has 9 beads, and monk $C$ has 3
beads by describing a sequence of steps leading to this state.

\solution{
Initially, monk $C$ gives a bead to monk $B$ using rule 3.  Then monk
$A$ gives his 5 beads to monk $B$ using rule 2 repeatedly. }

\vspace{2in}

\problempart The monks can not reach the state where every monk has 4
beads. This can be proved by the Invariant Method using a simple invariant
$P(a,b,c)$ where $a,b,c$ are the numbers of beads held by monks $A,B,$ and
$C$.  State such an invariant; you need not prove that it works.


\solution{

$P(a,b,c) \eqdef \text{ if $c$ is even, then $a > b$}$.

Here is the proof that it works (not required):

\begin{proof}
We prove that if monk $C$ has an even number of beads, then monk $A$ has
more beads than monk $B$.  This implies that the monks can never evenly
divide up the prayer beads; an even division would require that $C$ have 4
beads, but then the invariant would imply that $A$ has more beads then
$B$.

The invariant holds in the single start state $Q_0$, since in this
case monk $C$ has an even number of beads (4), and monk $A$ has more
beads than monk $B$ (5 vs. 3).  Furthermore, if the invariant holds
before a transition, then it holds after a transition.  There are six
cases to check, corresponding to the six types of transition.

\begin{enumerate}
\item $(a, b, c) \rightarrow (a+1, b-1, c)$ where $b > 0$.  If $c$ is
odd, then the invariant holds after the transition because the
hypothesis of the invariant if false.  If $c$ is even, then the
invariant holds after the transition because $a + 1 > a > b > b - 1$.

\item $(a, b, c) \rightarrow (a-1, b+1, c)$ where $a > 0$ and $c$ is
odd.  The invariant holds after the transition because the hypothesis
of the invariant is false.

\item $(a, b, c) \rightarrow (a-1, b, c+1)$ where $a > 0$ and either
$c$ is even or $a \geq b + 2$.  If $c$ is even, then the invariant
holds after the transition because the hypothesis is false.  If $c$ is
odd, then the invariant holds after the transition because the
conclusion is true; that is, monk A has more beads than monk B.
\end{enumerate}

The argument in the remaining three cases is identical to the argument
for case 3.  Since the invariant hold in all start states and is
maintained under all transitions, the claim is proved by the Invariant
Theorem.
\end{proof}
}

\vspace{2in}

\end{problemparts}
\fi




