\documentclass[12pt]{article}
\usepackage{amsmath}

\input{macros-course}

\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}


\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\ignore}[1]{}
\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1}

\newcommand{\script}[1]{\mathbold{#1}}


\newcommand{\pts}[1]{\relax[#1 pts]\enskip\ignorespaces}

\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

\newcommand{\bij}{\mathop{\mbox{\rm bij}}}

\begin{document}

\handout{final}{Final Exam}{May 20, 1999}

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

\textbf{Circle the name of your TA}:\\
\begin{center}
\begin{tabular}{lll}
Matt Blum & Stas Jarecki\&Eric Lehman & Amit Khetan\\
Mike Leonida & Zulfi Ramzan & Jared Smith-Mickelson
\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 twelve (12) problems totaling 200 points.  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.

\iffalse
\item Show your work, as partial credit will be given.  You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it.  {\bf Be neat}.
\fi

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\iffalse
\noindent Write the hour at when your Friday recitation begins \brule{3em}

\medskip
\fi

\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 & 35  & & \\ & & & \\\hline & & &\\
2 & 10  & & \\ & & & \\\hline & & &\\
3 & 10  & & \\ & & & \\\hline & & &\\
4 & 15  & & \\ & & & \\\hline & & &\\
5 & 15  & & \\ & & & \\\hline & & &\\
6 & 15  & & \\ & & & \\\hline & & &\\
7 & 15  & & \\ & & & \\\hline & & &\\
8 & 20  & & \\ & & & \\\hline & & &\\
9 & 15  & & \\ & & & \\\hline & & &\\
10 & 20  & & \\ & & & \\\hline & & &\\
11 & 15  & & \\ & & & \\\hline & & &\\
12 & 15  & & \\ & & &\\
\hline
\hline
& & &\\
Total & 200 & & \\
& & &\\
\hline
\end{tabular}
\end{center}

\newpage

\begin{problems}

\problem\pts{35} \textbf{Short Answers.}
\bparts

\ppart An assembly line produced 10001 cars which passed inspection and 19
which did not.  What is the largest $n$ for which there must have been a
run of $n$ consecutive cars that passed inspection?  \brule{1.0in}
\solution{501}

\ppart What is the largest number of edges possible in a two-colorable,
four vertex undirected graph (without self-loops)?  \brule{1.0in}
\solution{4}

\ppart %F96 Final

A bridge hand consists of 13 cards.  The {\em suit-distribution} of a hand
is the number of cards in each suit.  For example, one possible
suit-distribution is 4 spades, 3 hearts, 3 diamonds, and 3 clubs.  How many
suit-distributions are there?

\solution{This is equivalent to placing 13 balls (corresponding to each
card in a hand) to 4 bins (corresponding to each suit).  Thus the number of
distributions is $\binom{13 + 4 - 1}{4 - 1} = 560.$
}
\vspace{0.5in}

\ppart In an employment interview for an expedition to the Sahara desert, a
weather forecaster honestly promises at least 95\% accuracy for his daily
predictions of sunshine versus rain.  Is this an impressive credential for
the job?  Briefly explain.

\solution{Unimpressive: he could be 95\% accurate by always predicting
sunshine.  It would be impressive if his daily prediction was 95\% accurate
\emph{given that it rained}.}

\vspace{1in}

\ppart In a simple path in an undirected tree with $n$ vertices, what is
the largest number of edges possible? \brule{0.7in}

\solution{$n-1$}

\ppart What is the coefficient of $x^{12}$ in the polynomial $(7x+3)^{50}$?
(Your answer may contain binomial coefficients and integer powers.)

\solution{$3^{50-12}7^{12}\binom{50}{12}$}

\vspace{.7in}

\ppart Write a closed form expression for
\[
\Pi_{k=1}^\infty 2^{2^{-k}}.  \brule{1in}
\]

\solution{$2^{\sum_{k=1}^\infty 2^{-k}} = 2^1 = 2$}

\eparts

\newpage
\problem\pts{10} \textbf{Cardinality.}  Let $P(A)$ denote the powerset of a
set $A$.  Prove there is no bijection between $S$ and $P(P(S))$ for any set
$S$.

\solution{By contradiction.  If there was such a bijection, then there is
an surjection from $S$ to $P(P(S))$.  But there is an obvious surjection
$P(P(S))$ to $P(S)$, namely map every one-element set $\set{T}\in P(P(S))$
to $T \in P(S)$ (and map all the other elements of $P(P(S))$ to an
arbitrary member of $P(S)$---say the empty set).  Since the composition of
surjections is a surjection, we conclude there is an surjection from $S$ to
$P(S)$, contradicting Cantor's Theorem.}

\iffalse
\problem\pts{25} \textbf{Cardinality.}  Let $A$ be an infinite set and $B$
be a finite set.  Show that there is a bijection $g:A \union B \to A$.

\solution{If $A \union B = A$ there is trivially a bijection, so we may
assume there is at least one element in $B-A$.  Let $b_0,b_1,\dots,b_{n-1}$ be
the elements in $B-A$ where $n> 0$.  Since $A$ is infinite, there is an
injection $f:\naturals \to A$.  Define $g:A \union B \to A$ as
\[g(x) = \left\{\begin{array}{ll}
            f(i) & \mbox{if }x = b_i\\
            f(j+n) & \mbox{if }x = f(j)\\
            x & \mbox{otherwise.}  
\end{array} \right.
\]
}

\fi

\newpage
\problem\pts{10} \textbf{Stable Marriage Problem and Partial Order.}  We
know the ``morning-evening'' protocol yields a man-optimal set of stable
marriages when the men propose, or a woman-optimal set of stable marriage
if we reverse the roles and let the women propose.  In many cases there are
further sets of stable marriages in addition to those produced by our
protocol.  We say that a stable marriage set, $S_1$, \emph{improves}
another such set $S_2$, in symbols $S_1 \succeq S_2$, if every man likes
his wife in $S_1$ at least as much as his wife in $S_2$.

\bparts

\ppart Prove that the improves relation, $\succeq$, is a partial order on
stable marriage sets.

\solution{LATER}
\vspace{2.5in}

\ppart What special properties do the the man-optimal and woman-optimal
stable marriage sets have in this partial order?

\solution{They are the maximum and minimum elements, respectively.}
\vspace{0.5in}

\ppart For stable marriage sets $S_1,S_2$, define the set of marriages,
$S_1 \sqcup S_2$, by having each man marry whichever of his spouses in
$S_1$ or $S_2$ he prefers.  It turns out, and you may take as given, that
$S_1 \sqcup S_2$ defines a marriage set and the set is stable (neither of
these facts is obvious).  What special relationship does $S_1 \sqcup S_2$
have with $S_1$ and $S_2$ in this partial order?

\solution{It is the \emph{least upper bound} of $S_1$ and $S_2$.}
\vspace{1.0in}
 \eparts

\newpage
\problem\pts{15}  %S96 Final
\textbf{Divide and Conquer.}  We wish to prove by induction on $n$ that the
recurrence
\[
T(n) = T(\floor{n/2}) + T(\floor{n/4}) + n
\]
has an asymptotic growth rate of $O(n)$.

Circle each of the inequalities below which can serve as \emph{an induction
hypothesis} in a such a proof.
\[
\begin{array}{lrcl}
(i) & T(n) & \leq & 4n^2 \\
(ii) & T(n) & \leq & 2n \\
(iii) & T(n) & \leq & 10n \\
(iv) & T(n) & \leq  & 3n+10\\
(v) & T(n)&  \leq & 4n
\end{array}
\]
\solution{(iii) and (v)}

\newpage

\problem\pts{15} \textbf{Inclusion-exclusion.}  Consider the set of letters
\[\set{a,l,m,e,y,e,r},\]
\bparts

\ppart\pts{5}  How many different sequences of these letters are there? \brule{1in}

\solution{$\binom{7}{1,1,1,2,1,1} = 7!/2!$}


\ppart\pts{10} How many different sequences are there that do not
contain either of the words \emph{eye} or \emph{ram}? \brule{1in}

\solution{
\begin{eqnarray*}
\mbox{Arrangements with eye: use} \set{eye,a,l,m,r} & = & 5!\\
\mbox{Arrangements with ram: use} \set{ram,l,e,y,e} & = & 5!/2!\\
\mbox{Arrangements with ram and eye: use} \set{ram,eye,l} & = & 3!\\
\mbox{Arrangements with neither ram nor eye}
      & = & 7!/2! - 5! - 5!/2! + 3! = 2346.
\end{eqnarray*}
}

\vspace{2.5in}

\eparts

\newpage

\problem\pts{15} %S97 Final
\textbf{Binomial Coefficients.}  Consider the following identity:
\[
\sum_{k=0}^n \binom{n}{k} 2^k = 3^n.
\]

\bparts

\ppart\pts{5} Prove this identity using the binomial theorem.

\solution{LATER}
\vspace{2.0in}

\ppart\pts{10} Prove this identity via a combinatorial argument. (Hint: Consider
the number of ways to donate some subset of your $n$ baseball cards to two
museums.  For one side, consider where each card ends up.  For the other,
consider where each \emph{donated} card ends up.)

\solution{LATER}
\vspace{3.5in}

\eparts

\iffalse

\newpage
\problem\pts{10} \textbf{Counting.} A standard deck of $52$ cards plus two
additional jokers is shuffled so that each of the permutations of the 54
cards are equally likely.  What is the {\bf probability} that no two spades
are adjacent in the shuffled deck?  (All you need to know about jokers is
that they are not spades.)  You may express your answer using factorials
and binomial coefficients.

\solution{13 spades are ``bars.''  The other cards are ``stars.''  Place
one star in each of the 12 places between bars.  This leaves $54 - 13 -12 =
29$ stars to place among the bars; there are $\binom{29 + 13}{13}$ such
patterns of stars and bars.  There are $13! \cdot (54 -13)!$ shuffles
matching each pattern, and the total number of shuffles is $54!$, so the
probability of no two adjacent spades is
\[
\binom{29 + 13}{13} \cdot 13! \cdot (54 -13)!/54! = \binom{29 +
13}{13}/\binom{54}{13} = 29!/54!
\]}

\vspace{3in}
\fi


\newpage
\problem\pts{15} \textbf{Conditional Probability.}  We consider a
hypothetical Institute with only two departments: EECS and Math, and
consider the experiment where we pick a random applicant for admission to
one of these departments.  Define the following events:
\begin{center}
\begin{tabular}{rcl}
A & ::= & applicant is accepted,\\
F & ::= & applicant is female,\\
M & ::= &  applicant is male,\\
MATH & ::= & applicant applied to Math,\\
EECS & ::= & applicant applied to EECS.
\end{tabular}
\end{center}
Assume that all applicants are either male or female, and that no
applicant applied to both departments.
\iffalse
That is, the events $F_{EECS}$,
$F_{CS}$, $\mbox{M-EECS}$, and $\mbox{M-CS}$ are all disjoint.
\fi

\bparts

\ppart The Institute is sued for gender discrimination, with
the plaintiff observing that in both EECS and Math, the probability that a
woman is accepted is less than the probability that a man is accepted.
This observation can be precisely expressed with two inequalities
between conditional probabilities involving the events above.  State these
inequalities.

\solution{
\begin{eqnarray*}
\Pr(A \mid F \intersect EECS) & < & \Pr(A \mid M \intersect EECS), \\
\Pr(A \mid F \intersect MATH) & < & \Pr(A \mid M \intersect MATH).
\end{eqnarray*}
}
\vspace{1.5in}

\ppart The Institute's defense attorneys retort that overall among all
applicants, a woman is {\em more} likely to be accepted than a man.
Express this observation as an inequality between conditional probabilities
involving the events above.

\solution{
\begin{eqnarray*}
\prob{A \mid F \intersect (EECS \cup MATH)} & > & \prob{A \mid M
\intersect (EECS \cup MATH)}
\end{eqnarray*}
}
\vspace{1.5in}

\ppart Although the assertions above may appear to be logically
inconsistent, both the plaintiff's and the defense's claims about the
conditional probabilities can be correct. (Never mind whose interpretation
of the data we find more persuasive.)  Fill in the missing table entries
below with possible applicant statistics for which both the plaintiff and
the University attorneys' assertions are true.

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
     & Applied & Accepted & percent accepted\\
 & & & \\ \hline \hline & & &\\
Dept & Females & Females &  Females\\
& & & \\ \hline & & &\\
CS & & & \\ & & & \\ \hline & & &\\
EECS & 100 & 70 & 70\% \\ & & & \\ \hline & & &\\
Total & &  & \\ & & &\\ \hline \hline & & &\\
Dept & Males & Males & Males\\
& & & \\ \hline & & &\\
CS & 100 & 50 & 50\% \\ & & & \\ \hline & & &\\
EECS & & & \\ & & & \\ \hline & & &\\
Total & &  & \\
& & &\\
\hline
\end{tabular}
\end{center}

\solution{
\[
\begin{array}{ccr}
\mbox{CS} & \mbox{0 females accepted, 1 applied} & 0\% \\
          & \mbox{50 males accepted, 100 applied} & 50\% \\
\mbox{EECS} & \mbox{70 females accepted, 100 applied} & 70\% \\
          & \mbox{1 male accepted, 1 applied} & 100\% \\
\hline
\mbox{Overall} & \mbox{70 females accepted, 101 applied} & \approx 70\% \\
          & \mbox{51 males accepted, 101 applied} & \approx 51\%
\end{array}
\]
}

\eparts

\newpage
\problem\pts{20} \textbf{Probability of Graph Assertions.}  A digraph with
vertices $\set{1,2,\dots, n}$ is called an \emph{$n$-digraph}.  (The edges
of an $n$-digraph may be \emph{any} pair of vertices; self-loops are
allowed.)  Given an $n$-digraph, $G$, let ``$d(x,y)$'' be the assertion
that $G$ has a directed edge from vertex $x$ to vertex $y$.

\bparts

\ppart\pts{1} How many $n$-digraphs are there? \brule{1in} \solution{$2^{n^2}$}

\ppart\pts{1} How many $n$-digraphs satisfy the assertion $\forall x, y : d(x,y)$?
\brule{1in}\solution{1}

\ppart\pts{3} How many $n$-digraphs satisfy the assertion $\exists x, y : d(x,y)$?
\brule{1in}\solution{$2^{n^2}-1$}

\medskip

Suppose we randomly select an $n$-digraph, with all $n$-digraphs equally
likely to be selected.

\ppart\pts{5} Explain why there is nonzero probability that the selected
$n$-digraph satisfies \emph{both} of the following assertions:
\[\begin{array}{l}
\forall x_1 \exists x_2 \exists x_3 \forall x_4 \forall x_5 \exists x_6 :
d(x_1,x_2) \vee d(x_3,x_4) \vee d(x_5,x_6) \vee  d(x_3,x_1)\\
\exists x_1 \forall x_2 \forall x_3 \exists x_4 \exists x_5 \exists x_6 :
d(x_1,x_2) \wedge d(x_3,x_4) \wedge d(x_5,x_6) \wedge  d(x_3,x_1)
\end{array}\]

\solution{We need only show that some $n$-digraph satisfies both assertions.
The complete $n$-digraph is one.}
\vspace{1in}

\iffalse
\ppart Let $p$ be the probability that the selected $n$-digraph satisfies
the first assertion in the previous part.  Outline a proof that the
probability that it satisfies the second assertion $1-p$.

\solution{The second assertion is the complement of the first assertion if
we replace $d(\cdot,\cdot)$ with $\neg (\cdot, \cdot)$ throughout.  Now a
graph $(V,E)$ satisfies such a logical assertion iff its complement graph
$(V,V^2 - E)$ satisfies the assertion when we replace $d(\cdot,\cdot)$ with
$\neg d(\cdot, \cdot)$ throughout.  This defines a bijection between the
sample points satisfying the formula and its replacement, so the
probabilility of an assertion is the same as the probability of the
assertion with $d$ replaced by $\neg d$.  Hence the probability of the
second assertion is the same as the probability, $1-p$, of the complement
of the first one.}

\vspace{3in}
\fi

\iffalse
\ppart Show that the probability that the selected graph satisfies $\forall
x \exists y : d(x,y)$ approaches 1 as $n$ approaches infinity.

\solution{For given $x$, the probability that there is no edge to all of
the vertices (including itself) is $1/2^n$, since the existence of each
edge is independent of the others.  So the probability that there is some
edge out of $x$ is $1- 1/2^n$.  Whether one value of $x$ has this property
is independent of whether any other does, so the probability that all the
vertices have this property is $(1- 1/2^n)^n$ which approaches 1 as $n$
approaches infinity.}


\vspace{3in}
\fi

\ppart\pts{6} A directed Hamiltonian cycle in a digraph is a directed cycle going
through each vertex exactly once.  What is the expected number of directed
Hamiltonian cycles in the selected graph?

\solution{
\begin{eqnarray*}
\lefteqn{ \expect{\mbox{number of cycles through a particular
simple cycle of vertices}}}\\
 & = & \prob{\mbox{all edges present in a particular cycle of the
vertices}}\\
& = & 1/2^n.
\end{eqnarray*}
The number of simple cycles is $n!/n$ so the expected number of cycles is
$n!/n2^n$.}

\vspace{2in}

\ppart\pts{4}  Circle all that apply: the expected number of simple cycles is
\[
=\Omega (e - 0.001)^{n \ln n}, \qquad
=\Theta(e^{n \ln n}), \qquad
=O(e + 0.001)^{n \ln n}, \qquad
\sim e^{n\ln n}/(2e)^n.
\]

\solution{The first and third.}

\iffalse
\ppart Show that the expected number of simple cycles is $\Omega (e -
0.001)^{n \ln n}$.

\solution{Using Stirling's formula
\[n!/n2^n \sim \sqrt{2\pi/n}(n/e)^n/2^n = \sqrt{2\pi/n}e^{n\ln n}/(2e)^n.\]
But $e^{n\ln n} = [(e - 0.001)\alpha]^{n\ln n}$ where $\alpha = e/(e -
0.001) > 1$, so
\begin{eqnarray*}
\sqrt{2\pi/n}e^{n\ln n}/(2e)^n & = &
\sqrt{2\pi/n}\alpha^{n \ln n}(e- 0.001)^{n\ln n}/(2e)^n\\
& = & \sqrt{2\pi/n}(e- 0.001)^{n\ln n}(\alpha^{\ln n}/2e)^n\\
& \geq  & \sqrt{2\pi/n}(e- 0.001)^{n\ln n}3^n\\
& = & [\sqrt{2\pi/n}3^n](e- 0.001)^{n\ln n}
\end{eqnarray*}
when $n$ is large enough that $\alpha^{\ln n} \geq 6e$.  Since the final
bracketed expression grows unboundedly, the whole final expression is
$\Omega((e- 0.001)^{n\ln n}).$ }

\vspace{2in}
\fi

\eparts

\newpage

\iffalse

\problem\pts{???}  \textbf{Probability of Assertion}
Let $A$, $B$, and $C$ be mutually independent random
variables taking on values in the range $1$ to $n$ uniformly.  What is
the probability that the following statement is true?

\[
\neg ((A \geq B) \vee (A \geq C)) \wedge
	\exists x \ ((B < x \wedge x < C) \vee
		     (C < x \wedge x < B))
\]

Assume that the universe is the set of natural numbers.

\solution{
The statement says that $A$ is less than $B$ and $C$ and there is some
number between $B$ and $C$.  The number of assignments to $A$, $B$,
and $C$ satisfying this statement is
\[
2 \cdot \binom{n-1}{3}.
\]
Therefore, the probability that a random assignment is satisfying is
\[
\frac{2 \cdot \binom{n-1}{3}}{n^3}.
\]}
\fi


\iffalse
\newpage

\problem\pts{20} \textbf{Bayes' Theorem.} One percent of the population is
infected with a sexually transmitted disease (STD).  There are two
over-the-counter tests which detect STD infection.  Test A gives 95\%
reliable results for both infected and uninfected individuals.  Likewise
for Test B but with 90\% reliability.  The correctness of each test is
independent of the other.
\bparts

\ppart
If the tests are performed on someone infected with STD, what is the
probability that both tests return positive?

\solution{$P(A \intersect B|H) = P(A|H) * P(B|H)
         = 95\% * 90\%
	 = 85.5\%$}

\vspace{1.5in}

\ppart You apply both tests to yourself and both come back positive.  What
is the probability that you actually have an STD?

\solution{
\begin{eqnarray*}
\lefteqn{P(H|A \intersect B)  =  P(A \intersect B|H) * P(H) / P(A \intersect B)}\\
         & = & P(A \intersect B|H) * P(H) / ( P(A \intersect B|H) * P(H) + P(A \intersect B|-H) * P(-H) )\\
         & = & P(A \intersect B|H) * P(H) / ( P(A \intersect B|H) * P(H) + P(A|-H) * P(B|-H) * P(-H) )\\
	 & = & 85.5\% * 0.01\% / ( 85.5\% * 0.01\% + \%5 * \%10 * 99.99\%)\\
	 & = & 1.68\%
\end{eqnarray*}
}

\vspace{1.5in}

\eparts
\fi

\iffalse
\newpage

\problem\pts{20}        

In this problem we are going to prove a case of {\bf Vandermonde's
theorem} which says:
\[
\sum_{i=0}^n \binom{n}{i}^2  =  \binom{2n}{n}
\]

\bparts
\ppart A {\bf lattice path} is a path from a point in the plane with
integer coordinates to another point where each step in the path is
either one unit to the right or one unit up.  Show how many lattice
paths exist from (0,0) to $(p,q)$ by applying a bijection between
paths and an appropriate set of binary strings.

\solution{Each path corresponds to a string of $(p+q)$ bits where $p$
of them are ones.  We choose $p$ out of the total $p+q$ positions to
be one, yielding $\binom{p+q }{ p}$ possibilities.}

\vspace{2in}

\ppart Prove the theorem above combinatorially by showing that both sides
count the number of lattice paths from $(0,0)$ to $(n,n)$. \hint classify the
paths by the poin on the diagonal from $(n,0)$ to $(0,n)$.

\solution{Each path from (0,0) to $(n,n)$ passes through some point
$(i,n-i)$.  There are $\binom{n }{ i}$ paths from (0,0) to $(i,n-i)$ and
$\binom{n }{ n-i}$ = $\binom {n }{i}$ paths from $(i,n-i)$ to $(n,n)$.  No
paths are double-counted because no path can go through two points on
the diagonal $y=n-x$.  The total number of paths is then $\sum_{i=0}^n
\binom{n }{ i}^2$.}

\eparts
\fi


\newpage
\problem\pts{15} \textbf{Wald's Theorem.}  Suppose successive digits from
zero to nine were generated independently until the four digit sequence
\textbf{9992} appeared.  What is the expected number of digits generated?
\brule{1in}

\hint Parse the sequence into consecutive ``tries to get 9992'', where a
``try'' is either a single digit other than 9, or a 9 followed by a single
digit other than 9, etc.  For example, the sequence 92349982999769992
parses into eight tries:
\[/92/3/4/998/2/9997/6/9992/.\]

\solution{11110.

By Wald's Theorem, the expected number is the mean time to a
successful try, namely $10^4$, times the expected
length of a try, which is
\[
1 \cdot \frac{9}{10} + 2 \cdot \frac{1}{10}\frac{9}{10} + 3 \cdot
(\frac{1}{10})^2\frac{9}{10} + 4 \cdot (\frac{1}{10})^3
 =  (900 + 180 + 27 + 4)/1000 = 1111/1000
\]
Thus on average, we will have to read 11110 digits in order to see
``9992''.}

\iffalse
\newpage

\problem\pts{20}

Solve the following linear recurrence:
\[
F_n  =  \frac{6 F_{n-1} - F_{n-2} + (1/2)^n}{9}
\]
subject to the initial conditions $F_0$ = 2, $F_1$ = 7/6.

\bparts
\ppart Obtain a particular solution.
\solution{$(1/2)^n$}

 \vspace{2in}

\ppart Solve the homogeneous equation.

\solution{$c_1 (1/3)^n + c_2 n (1/3)^n$}

\vspace{2in}

\ppart Combine the particular and homogeneous solutions to solve for $F_n$.

\solution{$F_n = (1/2)^n + (1/3)^n + n(1/3)^n$}

 \vspace{2in}

\ppart Solve the infinite series $\sum_{n=0}^\infty F_n$ using any method
you wish (but show your work).

\solution{$\frac{1}{1-1/2} + \frac{1}{1-1/3} + \frac{1/3}{(1-1/3)^2} =
17/4$.}

\vspace{2in}

\eparts
\fi

\newpage

\problem\pts{20} \textbf{Law of Large Numbers.}  Let $X_1, X_2, \dots$ be a
sequence of mutually independent random variables such that $\variance{X_i}
\leq b$ for some $b \geq 0$ and all $i \geq 1$.  Let
\[
S_n ::= X_1 + X_2 + \cdots + X_n.
\]
Prove that for every $\epsilon > 0$
\[
\lim_{n \rightarrow \infty}
        \prob{\abs{\frac{S_n}{n} - \expect{\frac{S_n}{n}}}
 \geq \epsilon} = 0.
\]
\hint Adapt the proof in the class handout of the Weak Law of Large
Numbers.  Note that in the version from the handout, the $X_i$'s came from
independent samples of the same 0-1 valued experiment, which is not the
case here.

\solution{Same as proof in the notes, simply replacing $\variance{G}$ by
$b$.}

\iffalse
\newpage

\problem \textbf{Expectation.} %F96 practice final

An integer $X$ is drawn from the set $1,2,\ldots,n$ uniformly at random. 

\bparts

\ppart 
Prove that the probability that $X$ is divisible by $k$ is $(1/n)(\lfloor
n/k\rfloor)$.

\solution{LATER}
\vspace{2in}

\ppart
Prove that the expected number of divisors of $X$ is $\Theta(\ln n)$

\solution{LATER}
\vspace{2in}
\eparts

\fi

\newpage
\problem\pts{15}  %revised from previous Final
\textbf{Bounds from the Mean.}  Two hundred students take a final
exam.  Given only that the mean on the exam is $60$ and the lowest score
was 20,
\bparts

\ppart\pts{10} state a best possible upper bound on the number of students who
scored at least $120$.  \brule{1in}

\solution{Let $R$ be the score.  Apply Markov's Bound to $R-20$:
\[
\prob{R \geq 120} = \prob{R-20 \geq 100} \leq \expect{R-20}/100 = 40/100 = 2/5,
\]
so at most $(2/5)200 = \textbf{80}$ students score $\geq 120$.}

\ppart\pts{5} Give an example set of scores which achieve your bound.

\solution{Of the 200 students,
80 score 120 and 120 score 20.  The mean is
\[
(80 \cdot 120 + 120 \cdot 20)/200 = 60,
\]
as required.}

\vspace{2in}

\eparts

\newpage

\problem\pts{15} %F96 practice final slight revision
\textbf{Bounds from the Mean.}  An exam has $20$ true/false questions and
$10$ multiple choice questions. Each true/false question is worth $2$
points while each multiple choice question is worth $6$ points.  There is a
student who answers the questions randomly and independently.  The student
is correct with probability $1/2$ on each true/false question, and with
probability $1/3$ on each multiple choice question.

\bparts

\ppart\pts{4} What is the expected score of the student? \brule{1in}

\solution{$1/2 \cdot 20 \cdot 2 + 1/3 \cdot 10 \cdot 6 = 40$}

\vspace{0.5in}

\ppart\pts{6} What is the variance of the student's score?  \brule{1in}

\solution{100.

Let $T_i$ be the score on $i$th T/F question.
\[
\variance{T_i}=\expect{T_i^2}-\expectsq{T_i} = 1/2\cdot 2^2 - 1 = 1.
\]
Let $M_i$ be the score on $i$th multiple choice question.
\[
\variance{M_i}=\expect{M_i^2}-\expectsq{M_i} = 1/3 \cdot 6^2 - 2^2 = 8.
\]
Let $S$ be the final score, so
\[
S = \sum_{i=1}^{20}T_i + \sum_{i=1}^{10}M_i.
\]
Because of independence,  the variances add:
\[\variance{S} = \sum_{i=1}^{20}\variance{T_i} +
\sum_{i=1}^{10}\variance{M_i}
= 20 \cdot 1 + 10 \cdot 8 = 100.
\]
}

\vspace{1.5in}
                                     
\ppart\pts{5} To give an upper bound on the probability that the student scores
more than $80$ points, one or more among Markov's, Chebyshev's, and
Chernoff's bounds, and the bounds derived for the tails of the binomial
distribution are applicable.  Which ones?

\solution{Markov and Chebyshev apply; Chernoff requires Bernoulli
(0/1-valued) variables, so doesn't apply in any direct way; the
distribution of $S$ would be binomial only if the probabilities and values
of the two kinds of questions were the same, but they aren't, so binomial
bounds don't apply.}
\vspace{0.5in}

\iffalse

\ppart What is the best upper bound on the probability that the student
scores more than
\iffalse $272$ \fi
$80$ points obtainable using the applicable results from the previous part?

\solution{Use one-sided Chebyshev \dots.  AM I MISSING AN APPLICATION OF
CHERNOFF HERE?}

\vspace{2in}
\fi

\eparts

\end{problems}
\end{document}

