\documentclass[11pt]{article}
\input{macros-course}

\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

\askaboutsolutions
%%\showsolutionstrue

\begin{document}

\ifshowsolutions
  \handout{finsol}{Final Exam --- Solutions}{December 21, 2001}{\stamp}
\else
  \handout{final}{Final Exam}{December 21, 2001}{\stamp}

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

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{l@{\hskip 3em}l@{\hskip 3em}l@{\hskip 3em}l}
Yu-Han & Christos & Nikos & Ashish \\
\ &&& \\
Thien-Loc & Jaime & Tina & Tong
\end{tabular}
\end{center}

%\noindent Write the hour at which your Thursday tutorial begins \brule{3em}.

\medskip

\begin{closeitemize}
\item This quiz is \textbf{closed book}.  {\bf No calculators}. There
is an Appendix that includes many formulas from the course.

\item There are six (6) \textbf{short} problems each worth 5 or 10 points,
followed by six (6) \textbf{regular} problems each worth 25 points.

\item Put your name on the top of {\bf every} page -- \emph{these
    pages may be separated for grading}.

\item Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.

\item You may cite without proof any of the results presented in class or
in the lecture notes.

\item \remove{Show your work, as partial credit will be given.}
\textbf{Be neat and write legibly}.  You will be graded not only on the
correctness of your answer, but also on how clearly you present it.

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

\ifshowsolutions

{\bf Summary}
\begin{enumerate}

\item SHORT: Orders of growth table
\item SHORT: Annuity
\item SHORT: Induction False Proof
\item SHORT: Equivalence Relations+Probability
\item SHORT: Gambler's Ruin
\item SHORT: Surjection

\item LONG: Numbered Trees, Invariants (Ashish)
\item LONG: Random Graphs, Logic+Probability (christos, use part c)
\item LONG: Combinatorics Matching (Radhika)
\item LONG: k-cycles in Graphs, Combinatorics+probability (Tina)
\item LONG: Monty Hall, Conditional Probability (Jaime)
\item LONG: Gambler, Markov+Chebyshev+Chernoff (Tutorial)

\end{enumerate}
\newpage
\else {}
\fi

\section*{Short Problems}

\begin{problems}

%% SHORT: Orders of Growth
\problem For each pair of functions $(f(n), g(n))$ in the table below, indicate
whether the statement at the top of the column is true (e.g., whether
$f(n) = O(g(n))$). Your answer should be ``yes'' or ``no'' in each
box; no explanations needed.

\large{
\[
\begin{array}{|cc|c|c|}
\hline
f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) \\ \hline\hline
2^n         & 3^n           &&\\\hline
%
2^{n^2}     & 3^n           &&\\\hline
%
2^{(\log_2 n)^2} & n^2      &&\\\hline
%
n^3 & (\log_2 n)n^{2.9}      &&\\\hline
%
(n!)^2       & n^n          &&\\\hline
\end{array}
\]
}

\ifshowsolutions \else \vspace{.5in} \fi

\solnospace{
\newcommand\y{\text{yes}}
\newcommand\n{\text{no}}

\begin{equation*}
\begin{array}{|cc|*{3}{c|}}
\hline
f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n))\\\hline\hline
2^n         & 3^n               & \y & \n  \\\hline
%
2^{n^2}     & 3^n               & \n & \y \\\hline
%
2^{(\log_2 n)^2} & n^2          & \n & \y \\\hline
%
n^3 & (log_2 n)n^{2.9}          & \n & \y \\\hline
%
(n!)^2       & n^n              & \n & \y \\\hline
\end{array}
\end{equation*}
}

%% SHORT: Annuity
\problem Theory Pig wants to borrow $d$ dollars so that he can purchase a
stylish new pigsty.  At the end of each year for the next $n$ years, Theory
Pig will drop by the bank to make a payment on the loan.  The banker will
immediately invest this returned money at an $r$\% annual rate of
return. The banker wants to wind up with at least as much money as a result
of Theory Pig's payments as he would if he had invested the whole $d$
dollars at $r$\% for $n$ years starting today.

Write a closed form formula in $d,n$ and $r$ for the least annual payment
the banker might ask from Theory Pig.

\ifshowsolutions \else \newpage \fi

\solnospace{Let $R \eqdef (1+r/100)$, so that after 1 year, a one dollar
investment is worth $R$ dollars.  The banker will require that
\begin{equation*}
p \geq \frac{dR^{n}(R-1)}{R^n - 1}.
\end{equation*}
We derive this bound as follows:

Suppose that Theory Pig pays $p$ dollars at the end of each year.  The
banker can invest the first payment for $n-1$ years, the second payment
for $n-2$ years, etc., so that after $n$ years his total cash is:

\begin{eqnarray*}
\sum_{i=1}^{n} p \cdot R^{i-1}
& = & \sum_{i=0}^{n-1} p \cdot R^i\\
& = & p \frac{R^n - 1}{R - 1}.
\end{eqnarray*}

On the other hand, if the banker could invested the $d$ dollars today, then
after $n$ years his total cash is $d R^{n}$.  The first amount must
be at least as large as this, so

\begin{eqnarray*}
p \frac{R^n - 1}{R - 1} & \geq & dR^{n}\\
p &\geq& \frac{dR^{n}(R-1)}{R^n - 1}.
\end{eqnarray*}
}

\iffalse
%% SHORT: Infinite Expectation 
\problem Describe the probability density function for a random
variable, $Q$, such that $\expect{Q}$ is infinite but
$\expect{\sqrt{Q}}$ is finite.

\ifshowsolutions \else \vspace{1in} \fi

\solnospace{For example, let $a \eqdef \sum_{i=1}^\infty 1/i^2$.
Define $\pr{Q=i} \eqdef 1/ai^2$ for positive
integers $i$.  So
\[
\expect{Q} = \sum_{i=1}^\infty i\cdot 1/ai^2 = (1/a)\sum_{i=1}^\infty 1/i =
\infty.
\]

But
\[
\expect{\sqrt{Q}} = \sum_{i=1}^\infty \sqrt{i}\cdot 1/ai^2 =
(1/a)\sum_{i=1}^\infty 1/i^{3/2} < \infty.
\]
}
\fi

%% SHORT: False Proof
\ifshowsolutions \else \newpage \fi

\problem Let $L_n$ be the $n+1$-vertex simple ``line'' graph consisting of a
single simple path of length~$n$.  For example, $L_4$ is shown in the
figure below:

\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}} \put(20,15){\line(1,0){20}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){20}}
\put(60,15){\circle*{3}} \put(60,15){\line(1,0){20}}
\put(80,15){\circle*{3}}
\end{picture}
\end{center}

\centerline{The line graph $L_4$}
\end{figure}

Let's say a simple graph has ``two ends'' if it has exactly two
vertices of degree~one, and all its other vertices have degree~two.
In particular, for $n \ge 1$, the graph~$L_n$ has two ends. Consider
the following false theorem and false proof of that theorem.

\paragraph{False theorem:}
Every simple graph with two ends is isomorphic to~$L_n$ for some~$n~\ge~1$.

\paragraph{False proof:}
We prove by induction on the number, $n \ge 1$, of edges in a simple
graph, that every two-ended graph with $n$ edges is isomorphic
to~$L_n$.

(Base case $n = 1$): A simple graph with one edge can only consist of
the two vertices connected by that edge and some number of vertices
not attached to  any edge, i.e., vertices of degree~zero.  Since a
two-ended graph cannot have vertices of degree~zero, the only
two-ended graph with one edge must consist solely of the two vertices
connected by the edge, which makes it isomorphic to~$L_1$.

(Induction case): Assume that $n \ge 1$ and every two-ended graph with
$n$ edges is isomorphic to~$L_n$.  Now let $G_n$ be any two-ended
graph with $n \ge 1$ edges.  By hypothesis, $G_n$ is isomorphic
to~$L_n$.  Suppose an edge is added to~$G_n$ to form a two-ended
graph~$G_{n+1}$.

Since $G_n$ is isomorphic to~$L_n$, it consists of a simple path of
length~$n$.  The only way to add an edge to the path and preserve
two-endedness is to have that edge go from one end---that is, one of
the degree-one vertices---to a new vertex, lengthening the path by
one.  That is, the resulting $n+1$-edge graph must be a simple path of
length~$n + 1$, so it is isomorphic to~$L_{n+1}$.  Q.E.D.
\\

Explain briefly, but clearly, what is wrong with the false induction proof.

\ifshowsolutions \else \vspace{2in} \fi

\solnospace{
This proof assumes that every two-ended graph with $n+1$ edges is obtained
by adding an edge to a two-ended graph with $n$ edges.  But not every
two-ended graph is obtained this way, \eg the following graph is not:
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
The smallest two-ended graph not isomorphic to any line graph.
\end{center}}


%% SHORT: equivalence
\ifshowsolutions \else \newpage \fi

\problem Let $X,Y$ be real-valued random variables \iffalse defined on the
same sample space \fi, and let $[X=Y]$ be the event that the value of $X$
equals the value of $Y$.  Define a binary relation, $\rho$, on such random
variables by the rule that $X \rho Y$ iff $\prob{X = Y} = 1$.

It is obvious from the definition that $\rho$ is \emph{reflexive} and
\emph{symmetric}, so only one more property is needed to prove that $\rho$
is an equivalence relation.

\bparts

\ppart State the remaining property of $\rho$ that confirms it is an
equivalence relation.

\ifshowsolutions {} \else \vspace{0.5in} \fi

\solnospace{\pts{2} $\rho$ must be  \emph{transitive}: if $X \rho Y$ and $Y \rho
Z$ then $X \rho Z$.}

\ppart Prove that $\rho$ has the property.

\ifshowsolutions {} \else \vspace{1.5in} \fi

\solnospace{\pts{8}
Note that $X \rho Y$ iff $X(s) = Y(s)$ for every sample point, $s$, with
positive probability, \ie such that $\pr{s}>0$.

So let $s$ any sample positive with positive probability and suppose $X
\rho Y$ and $Y \rho Z$.  Now since $X \rho Y$, we know that $X(s) = Y(s)$,
and likewise since $Y \rho Z$ also $Y(s) = Z(s)$.  Therefore $X(s) =
Z(s)$, which implies that $X \rho Z$, as required.

\textbf{Alternative proof:}  We will prove
\begin{lemma*}
For any event, $W$, of probability one, and any event, $A$,
\[
\pr{A \intersect W} = \pr{A}.
\]
\end{lemma*}

Assuming the Lemma for the moment, we prove transivity as follows: if
$X\rho Y$ and $Y \rho Z$, then the events $[X=Y]$ and $[Y=Z]$ each have
probability 1 by definition.  By the Lemma, their intersection also has
probability 1.  But this intersection in the same as the event $[X = Y =
Z]$, which is a subset of the event $[X=Z]$.  Hence,
\[
\pr{X=Z} \geq \pr{X=Y=Z} = \pr{[X=Y] \intersect [Y=Z]} = 1,
\]
so $X\rho Z$.

To prove the Lemma, note that $1-\pr{B} \geq 0$ for any event, $B$, so
\[
\pr{A} \geq \pr{A \intersect W} = \pr{A} + \pr{W} - \pr{A \union W} = 
\pr{A} + (1 - \pr{A \union W}) \geq \pr{A}.
\]
}

\eparts

%% Gamblers Ruin
\problem We consider the gambler's ruin game, where there is some fixed
probability, $p$, that the gambler will win each individual 1-dollar bet,
and the gambler has some fixed goal of $T$ dollars.

Let $e(n)$ be the expected \emph{number of bets} the gambler must make
until the game ends, where $n \leq T$ is his initial capital, \ie the number
of dollars he starts with.  Then the function $e$ satisfies a linear
recurrence of the form
\[
e(n) = a \cdot e(n+1) + b \cdot e(n-1) + c.
\]
for constants $a,b,c \in \reals$.

\begin{enumerate}
\item What are a\brule{0.5in}, b\brule{0.5in}, c\brule{0.5in}?

\solnospace{$a=p, b=1-p , c = 1$}

\item What are $e(0)$ \brule{0.5in} and $e(T)$ \brule{0.5in}?

\solnospace{$0,0$.}
\end{enumerate}

%% Infinite Sets
\ifshowsolutions \else \vspace{.3in} \fi
\problem Describe two infinite sets $A$ and $B$ such that there
no surjection from $A$ to $B$.  Indicate whether conversely there is a
surjection from $B$ to $A$.  No proofs are required.

\solnospace{No surjection from $A$ to $B$ is equivalent to no injection
from $B$ to $A$, so $(A,B)$ for example could be $(\nats, \reals)$ or
$(I,\power(I))$ for any infinite set $I$.  There will always be a
surjection in the other direction.}

\ifshowsolutions \else \vspace{2in} \fi

%% REMOVED: Stars n bars problem
\iffalse

\problem A shelf holds 17 books in a row.  How many ways are there to
choose 7 books so that no two adjacent books are chosen? \brule{0.5in}

\solnospace{ There are 7 bars (chosen books), and therefore there are
8 places where the 10 stars (non-chosen books) can fit (before the
first bar, between the first and second bars,..., after the seventh
bar).  Each of the second through seventh of these slots must have at
least one star in it, so that adjacent books are not chosen. Once we
have placed these 6 stars, there are 4 stars left to be placed in 8
slots. The number of ways to do this is therefore
\[
\binom{8+4-1}{4}=\binom{11}{4}=330.
\]

An \emph{alternative solution} is:

There are 10 non-chosen books, and therefore there are 11 places where
the 7 chosen books can fit (before the first bar, between the first
and second bars, \dots, after the tenth bar).  As no two chosen books
can be adjacent, at most 1 chosen book can fit in 1 place. We have thus
to choose 7 places out of the 11 available where there will be 1 chosen book.
The number of ways to do this is therefore
\[
\binom{11}{7}=330.
\]
}

\ifshowsolutions \else \vspace{1.5in} \fi
\fi

\end{problems}

\ifshowsolutions \else \newpage \fi
\section*{Regular Problems}

\begin{problems}

\problem In tutorial we considered algorithms for coding a numbered
tree as a sequence of numbers and vice-versa.  In this problem we consider
methods to prove properties of a procedure for extracting the tree coded by
a number sequence.  The trees are undirected and unrooted.

The procedure will construct a tree with $n$ vertices numbered
$1,\dots,n$ from an input that is a sequence, $s$, of $n-2$ numbers
each between $1$ and $n$.  The procedure works by adding edges to a
graph, $G$, with vertices $1,\dots,n$, deleting elements from a set,
$I$, of vertices called the \emph{incomplete vertices}, and deleting
successive elements of a sequence, $t$, of numbers.

Given input $s$, the procedure goes as follows:
\begin{enumerate}

\renewcommand{\labelenumi}{P\arabic{enumi}.}
\renewcommand{\labelenumii}{P\arabic{enumi}.\arabic{enumii}}

\item Initialize $G$ to be the graph with vertices $\set{1,\dots, n}$
and no edges, where $n \eqdef \abs{s}+2$.  Initialize $t \eqdef s$ and
$I \eqdef \set{1,\dots,n}$.

\item Repeat the following loop of instructions until there remain exactly
two incomplete vertices, that is, until $\card{I} = 2$:

\begin{enumerate}
\item Let $l$ be the largest vertex in $I$ that does not occur in $t$.

\item $I \eqdef I - \set{l}$.

\item Add the edge $(l, \text{first}(t))$ to $G$,
where \text{first}(t) is the first number in $t$.

\item $t \eqdef \text{rest}(t)$, where $\text{rest}(t)$ is the sequence of
numbers in $t$ after the first.
\end{enumerate}

\item Add to $G$ the edge between the remaining two vertices in $I$ and
terminate.

\end{enumerate}

\bparts

\ppart Is this algorithm deterministic or nondeterministic?  No
explanation necessary.

\solnospace{Deterministic}

\ppart Draw the graph generated by the following code: 72357

\ifshowsolutions \else \vspace*{2in}\fi

\solnospace{Omitted.}

\ifshowsolutions \else \newpage \fi

\ppart\label{alg-invs} For each of the following derived variables,
indicate whether, from one time around the loop to the next, it is
\begin{itemize}
\item[\textbf{I}] Increasing
\item[\textbf{D}] Decreasing,
\item[\textbf{C}] Constant,
\item[\textbf{NI}] Nonincreasing but not constant or decreasing,
\item[\textbf{ND}] Nondecreasing but not constant or increasing,
\item[\textbf{N}] or None of these.
\end{itemize}
For example,
\begin{quotation}\noindent
\vspace{-.4in}
\begin{itemize}

\item $\abs{t}$  \hfill\brule{1in}D.

\item $\card{E_G} \bmod 2$, where $E_G$ is the set of edges of
$G$. \hfill\brule{1in}N.

\end{itemize}
The length of $t$ is decreasing because its first element is removed each
time around the loop.  The parity of the number of edges of $G$ has none
of the other growth properties because edges are added one at a time
around the loop, so it alternates between 0 and~1.
\end{quotation}
This is a short-answer question, so do \textbf{not} include explanations
like the ones above.

\begin{enumerate}

\addtolength{\leftskip}{0.25in}%
% Change this next line to modify numbering style.
% Current style: roman numeral followed by )
\renewcommand{\labelenumi}{\roman{enumi})}

\item the number of vertices of $G$.  \hfill\brule{1in}

\solnospace{
C; the vertices are always $\set{1,\dots,n}$.
}

\item $\card{E_G}$, the number of edges in $G$.  \hfill\brule{1in}

\solnospace{I; an edge is added each time around}

\item
$\card{I}$, the number of incomplete vertices. \hfill\brule{1in}

\solnospace{D; a vertex is removed each time around.}

\item
$\card{I} - \abs{t}$, the number of incomplete vertices, minus the length
of $t$. \hfill\brule{1in}

\solnospace{C; always equals 2.}

\item $\card{\text{nums}(t)}$, where $\text{nums}(t)$ is the set of numbers
that occur in $t$. \hfill\brule{1in}

\solnospace{NI; stays the same when the first element of $t$ occurs in $t$
more than once.}

\item the number of vertices of $G$ not touching an edge.
\hfill\brule{1in}

\solnospace{NI; won't decrease when two nonisolated components are
connected.}

\iffalse

\item the predicate: $\text{nums}(t) \subset I$. \hfill\brule{1in}

\solnospace{C: always true.}

\fi

\iffalse
\item $\card{I-\text{nums}(t)}$, the number of incomplete elements that do
not appear in $t$. \hfill\brule{1in}

\solnospace{NI; stays the same when the first element of $t$ is not
repeated.}
\fi

\iffalse

\item
$\card{E_G} + \card{I}$ \hfill\brule{1in}

\solnospace{C; always equals $n$; but not obvious.}
\fi


\iffalse

\item the number of connected components of $G$ minus $\card{I}$.
\hfill\brule{1in}

\solnospace{C; equals 0}
\fi

\item
the number of connected components of $G$. \hfill\brule{1in}

\solnospace{D; but not obvious.

The problem statement says the result is a numbered tree, so $G$ has one
connected component on termination.  But $G$ initially has $n$ components,
and adding an edge can only reduce the number of components by one and
there are only $n-1$ edges in the final tree, so the edge added each time
around the loop must reduce the number of components.

Proving this without assuming that the final result is a tree needs a more
general invariant: each connected component contains \emph{exactly} one
incomplete element.  Since only edges between incomplete elements are
added, this implies that when an edge is added, it connects different
components.}

\iffalse

\item the maximum number of vertices in $I$ in any connected component of
$G$. \hfill\brule{1in}

\solnospace{C; always 1}
\fi

\item the number of cycles in $G$. \hfill\brule{1in}

\solnospace{C; always 0}

\addtolength{\leftskip}{-0.25in}%
\end{enumerate}

\ppart How many edges are in $G$ when the procedure terminates?
\hfill\brule{1in} 

\solnospace{$n-1$, which equals $\card{s}+1$} 

\ppart How many connected components does $G$ have on termination?
\hfill\brule{1in}

\solnospace{1}

\ppart How many possible trees are there with vertices numbered
$\set{1,\dots, n}$? \hfill\brule{1in}

\solnospace{$n^{n-2}$}

\eparts

\ifshowsolutions \else \newpage \fi
\problem We are going to classify different counting problems by figuring
out which ones have the same formula.  Here are a set of six formula.

\begin{center}
\begin{tabular}{rl}
$n^m$:       &\brule{1in}\\
$m^n$:       &\brule{1in}\\
$P(n,m)$:    &\brule{1in}\\
$C(n-1+m,m)$:&\brule{1in}\\
$C(n-1+m,n)$:&\brule{1in}\\
$2^{mn}$:      &\brule{1in}\\
\end{tabular}
\end{center}

For each problem part below, write its label---(a),(b),\dots---on the line
next to the corresponding formula above.

\bparts


\ppart
Number of ways of putting $m$ indistinguishable balls into $n$
distinguishable urns.

\ppart Number of ways of putting $m$ distinguishable balls into $n$
distinguishable urns.

\ppart
Number of ways of creating $m$ letter words from an alphabet of size $n$,
with no letter used more than once ($m \leq n$).

\ppart
Number of ways of creating $m$ letter words from an alphabet of size $n$,
where any letter can be repeated any number of times.

\ppart Number of permutations of $m$ indistinguishable stars and
$n-1$ indistinguishable bars.

\ppart Number of matrices of size $\sqrt{n} \times \sqrt{n}$ with $m$
possible values for each entry.  (Assume $n$ is a perfect square.)

\ppart
Number of possible subsets of A, where $|A|=nm$.

\ppart
Number of possible functions from set $A$ to $B$ where $|A|=n$ and $|B|=m$.

\ppart
Number of relations from set $A$ to $B$ where $|A|=n$ and $|B|=m$.

\ppart Number of injections from set $A$ to $B$ where $\card{A}=m$ and
$\card{B}=n$, and $m \leq n$.

\ppart 
Number of natural number solutions of the equation $x_1 + x_2 + x_3
\cdots x_n = m$, where $m$ is a non-negative integer.  (A solution is
a non-negative integer vector of values for $x_1,x_2,\cdots x_n$.)

\ppart
Number of ways of lining up $n$ red balls and $m-1$ blue balls



\solnospace{
\begin{center}
\begin{tabular}{rl}
$n^m$: & b d\\
$m^n$: & f h \\
$P(n,m)$: & c j \\
$C(n-1+m,m)$: & a e k \\
$C(n-1+m,n)$: & l \\
$2^{mn}$: &  g i\\
\end{tabular}
\end{center}
\iffalse

\begin{enumerate}

\item
Number of ways of putting $m$ indistinguishable balls into $n$
distinguishable urns. $C(n-1+m,m)$

\item Number of ways of putting $m$ distinguishable balls into $n$
distinguishable urns. $n^m$

\item
Number of ways of creating $m$ letter words from an alphabet of size $n$,
with no letter used more than once ($m \leq n$). $P(n,m)$

\item
Number of ways of creating $m$ letter words from an alphabet of size $n$,
where any letter can be repeated any number of times. $n^m$

\item Number of ways of permutations of $m$ indistinguishable stars and
$n-1$ indistinguishable bars. $C(n-1+m,m)$

\item
Number of matrices of size $\sqrt{n} \times \sqrt{n}$ with
$m$ possible values for each entry. $m^n$

\item
Number of possible subsets of A, where $|A|=nm$. $2^{mn}$

\item
Number of possible functions from set $A$ to $B$ where $|A|=n$ and
$|B|=m$. $m^n$

\item
Number of binary relations between set $A$ and set $B$ where $\card{A}=n$ and
$\card{B}=m$. $2^{mn}$

\item
Number of injections from set $A$ to $B$ where $|A|=m$ and $|B|=n$,
and $m \leq n$. $P(n.m)$

\item 
Number of natural number solutions of the equation $x_1 + x_2 + x_3
\cdots x_n = m$, where $m$ is a non-negative integer.  (A solution is
a non-negative integer vector of values for $x_1,x_2,\cdots x_n$.)
$C(n-1+m,m)$

\item
Number of ways of lining up $n$ red balls and $m-1$ blue balls. $C(n-1+m,n)$

\end{enumerate}
\fi

}

\eparts

\ifshowsolutions \else \newpage \fi
\problem 

Suppose we construct a simple undirected graph $G$ with vertex set
$V=\set{1,2,\dots,n}$, as follows:

\begin{itemize}
\item
First, we color the nodes: For each $x\in V$, we flip a coin twice. 
If we get heads in both tosses, we paint $x$ blue; otherwise, we paint 
$x$ red. 
\item
Next, we draw the edges: For each unordered pair $\set{x,y}$ of
distinct vertices from $V$, we roll a die. If we get~$6$, we draw
the edge connecting $x$ and $y$; otherwise, $x$ and $y$ remain
unconnected.  
\end{itemize} 

The coin and the die are both fair; every toss and every roll occurs
independently from any other toss and any other roll. 

For a vertex $x\in V$, let $B(x)$ denote the property ``$x$ is blue'' and
$R(x)$ denote the property ``$x$ is red''. Similarly, for vertices $x,y\in
V$, let $E(x,y)$ denote the property ``there is an edge connecting $x$ and
$y$''. For example, the formula
\[
E(1,2) \wedge 
R(1)   \wedge 
\forall x\, x\neq 1 \implies B(x)
\]
denotes the property ``there is an edge connecting nodes $1$~and~$2$,
node~$1$ is red, and all other nodes are blue''.

Note that \emph{$E(x,x)$ is false} for every $x \in V$, because a simple
graph does not have self-loops.

\bparts
\ppart
For each one of the following properties, write down a formula that
denotes that property.  Only symbols from the list
\[
R\ B\ E\ 
=\ \neq\ 
\forall\ \exists\ 
\wedge\ \vee\ \neg\ \implies\ \iff\
x\ y\ 
(\ )\ ,\
\]
can appear in your formula.

\begin{enumerate}
\addtolength{\leftskip}{0.25in}%
\renewcommand{\labelenumi}{\roman{enumi})}
\iffalse

\item \label{item-first}
``all nodes are red'': 

\solnospace{
$(\forall x)R(x)$
}
\fi

\ifshowsolutions \else \vspace*{0.75in}\fi

%\item
%``all nodes are blue'': 
%
%\solnospace{
%$(\forall x)B(x)$
%}\hrulefill
%

%\item
%``not all nodes are blue'': 
%``at least one node is red'': 
%
%\solnospace{
%Any of the two: $\neg(\forall x)B(x)$, $(\exists x)R(x)$
%}

\item
``at least two nodes are red'': 

\solnospace{
$(\exists x)(\exists y)\bigl( x\neq y \wedge R(x) \wedge R(y) \bigr)$
}

\ifshowsolutions \else \vspace*{0.75in}\fi

\item
``the graph is complete'' (contains every possible edge)

\solnospace{
$\forall x\forall y\, x\neq y \implies E(x,y)$
}

\ifshowsolutions \else \vspace*{0.75in}\fi

%\item
%``the graph is \emph{not} complete'': 
%
%\solnospace{
%$(\exists x)(\exists y)\bigl( x\neq y \wedge \neg E(x,y) \bigr)$
%}\hrulefill

%\item
%``the graph is empty'': 
%
%\solnospace{
%$(\forall x)(\forall y) \neg E(x,y)$
%}

\iffalse

\item \label{item-fourth}
``the set of edges in the graph is \emph{not} empty'': 

\solnospace{
$\exists x\exists y\, E(x,y)$
}

\ifshowsolutions \else \vspace*{0.75in}\fi
\fi

\item
``there exist at least two blue adjacent vertices'':

\solnospace{
$\exists x\exists y\, 
	E(x,y) \wedge 
	B(x) \wedge B(y)$
}
\ifshowsolutions \else \vspace*{0.75in}\fi


\item 
``every red vertex is adjacent to every blue vertex'': 

\solnospace{
$(\forall x)(\forall y)\bigl( 
	R(x) \wedge B(y)
	\implies
	E(x,y)
\bigr)$
}

\ifshowsolutions \else \vspace*{0.75in}\fi


\item  \label{item-difficult}
``no two adjacent vertices have the same color'': 

\solnospace{
$(\forall x)(\forall y)\bigl( 
	E(x,y) 
	\implies
	\bigl( R(x) \wedge B(y) \bigr)
	\vee
	\bigl( B(x) \wedge R(y) \bigr)
\bigr)$, or

$\neg (\exists x)(\exists y)\bigl(
	E(x,y) \wedge
	R(x) \wedge B(y) 
\bigr)
$
}

\ifshowsolutions \else \vspace*{0.75in}\fi

\end{enumerate}

\iffalse

\ppart For each one of the properties i)--iv) above, write a simple
formula in $n$ for the probability that $G$ has the property.
\begin{enumerate}
\addtolength{\leftskip}{0.25in}%
\renewcommand{\labelenumi}{\roman{enumi})}

\item	% all nodes are red
\solnospace{ 
	$(\tfrac{3}{4})^n$
}\brule{0.5in}
 
%\item	% all nodes are blue
%\solnospace{ 
%	$(\tfrac{1}{4})^n$
%}\hrulefill
%
%$\lim_{n\to\infty}p(n)=$\solnospace{
%	0
%}\hrulefill

%\item	% at least one node is red
%$p(n)=$\solnospace{ 
%	$1 - (\tfrac{1}{4})^n$
%}\hrulefill
%
%$\lim_{n\to\infty}p(n)=$\solnospace{
%	1
%}\hrulefill

\item	% at least 2 nodes are red
\solnospace{ 
	$1 - (\tfrac{1}{4})^n - n\tfrac{3}{4}(\tfrac{1}{4})^{n-1}
	=
	1 - \tfrac{3n+1}{4^n}$
}\brule{0.5in}

\item	% the graph is complete
\solnospace{ 
	$(\tfrac{1}{6})^{n(n-1)/2}$
}\brule{0.5in}


%\item	% the graph is not complete
%$p(n)=$\solnospace{ 
%	$1 - (\tfrac{1}{6})^{n(n-1)/2}$
%}\hrulefill
%
%$\lim_{n\to\infty}p(n)=$\solnospace{
%	1
%}\hrulefill

%\item	% the graph is empty
%$p(n)=$\solnospace{ 
%	$(\tfrac{5}{6})^{n(n-1)/2}$
%}\hrulefill
%
%$\lim_{n\to\infty}p(n)=$\solnospace{
%	0
%}\hrulefill

\item	% the graph is not empty
\solnospace{ 
	$1 - \left(\tfrac{5}{6}\right)^{n(n-1)/2}$
}\brule{0.5in}

\end{enumerate}
\fi

\ppart For each one of the following logical formulas, write a simple
expression in $n$ for the probability that $G$ satisfies the formula.

\begin{enumerate}
\addtolength{\leftskip}{0.25in}%
\renewcommand{\labelenumi}{\roman{enumi})}

\item
$\exists x\, B(x)$ \brule{0.5in}

\solnospace{
\[
1 - \left(\frac{3}{4}\right)^n
\]}

\item 
$\forall x\, [B(x) \vee R(x)]$ \brule{0.5in}

\solnospace{1}

\item 
$\forall x\, B(x) \vee \forall x\, R(x)$\brule{0.5in}

\solnospace{
\[
\left(\frac{1}{4}\right)^n + \left(\frac{3}{4}\right)^n
\]}

\item 
$\forall x\, B(x) \wedge \forall x\forall y\, \neg E(x,y)$\brule{0.5in}

\solnospace{
\[
\bigl(\frac{1}{4}\bigr)^n\bigl(\frac{5}{6}\bigr)^{n(n-1)/2}
\]}

\end{enumerate}


\iffalse

\ppart
What is the the probability that $G$ has
property~\eqref{item-difficult} of part~(a)? 
Your answer doesn't have  to be in closed form.

\solnospace{
Fix any $k\in\set{0,\dots,n}$, and any $k$ vertices $x_1,\dots,x_k\in
V$. The probability that $x_1,\dots,x_k$ are blue, the rest of the
vertices are red and there is no edge between a blue and a red vertex
is 
\begin{equation} \label{probab-1}
(\tfrac{1}{4})^k 
(\tfrac{3}{4})^{n-k}
(\tfrac{5}{6})^{k(n-k)}.
\end{equation}
Since there are $\tbinom{n}{k}$ different ways to fix $x_1,\dots,x_k$,
there are exactly $\tbinom{n}{k}$ outcomes (graphs) supporting the
event that exactly $k$ vertices are blue, and there is no edge between
a blue and a red vertex, each with
probability~\eqref{probab-1}. Hence, the probability of this event is 
\begin{equation} \label{probab-2}
\tbinom{n}{k}
(\tfrac{1}{4})^k 
(\tfrac{3}{4})^{n-k}
(\tfrac{5}{6})^{k(n-k)}.
\end{equation}
Finally, the event that no edge connects a blue and a red vertex is
the union of the $n+1$ disjoint events that we get by varying $k$ over 
$\set{0,\dots,n}$, each of them having probability~\eqref{probab-2}. 
Hence, the coloring is consistent with probability 
$$
\sum_{k=0}^{n}
\tbinom{n}{k}
(\tfrac{1}{4})^k 
(\tfrac{3}{4})^{n-k}
(\tfrac{5}{6})^{k(n-k)}.
$$
}
\fi

\eparts

\iffalse
\ifshowsolutions \else \newpage \fi
\problem Each person carries a certain, rare disease
with probability 1 in 1000.  Two doctors claim to be able to test for
the disease before symptoms appear.

\begin{problemparts}

\problempart Doctor $A$ was educated at Harvard Medical School and
employs the latest high-tech test.  If a patient has the disease, then
the test comes back positive 99\% of the time.  If the patient does
not have the disease, then the test comes back negative 97\% of the
time.  What is the probability that Doctor $A$ correctly diagnoses a
patient? \brule{0.5in}

\solnospace{
\begin{eqnarray*}
\Pr(\text{$A$ is correct})
    & = &   \Pr(\text{is diseased} \cap \text{test positive}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased} \cap \text{test negative}) \\
    & = &   \Pr(\text{is diseased}) \cdot
        \Pr(\text{test positive} \mid \text{is diseased}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased}) \cdot
        \Pr(\text{test negative} \mid \text{not diseased}) \\
    & = &   0.001 \cdot 0.99 + 0.999 \cdot 0.97 \\
    & \approx & 0.970
\end{eqnarray*}
}

\ifshowsolutions \else \vspace*{2.0in}\fi

\problempart Doctor $B$---a quack from MIT---murmurs strange chants and
burns incense.  With probability 1 in 1000, Doctor $B$ says that a patient
has the disease, regardless of whether or not the patient actually does.
What is the probability that Doctor $B$ correctly disgnoses a patient?
\brule{0.5in}

\solnospace{
\begin{eqnarray*}
\Pr(\text{$B$ is correct})
    & = &   \Pr(\text{is diseased} \cap \text{test positive}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased} \cap \text{test negative}) \\
    & = &   \Pr(\text{is diseased}) \cdot
        \Pr(\text{test positive} \mid \text{is diseased}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased}) \cdot
        \Pr(\text{test negative} \mid \text{not diseased}) \\
    & = &   0.001 \cdot 0.001 + 0.999 \cdot 0.999 \\
    & \approx & 0.998
\end{eqnarray*}
}

\ifshowsolutions \else \vspace*{2.0in}\fi

\problempart How many times as many errors does one doctor make compared
to the other?\brule{0.5in}

\solnospace{
Doctor $A$ makes about 15 times more errors than Doctor
$B$.}

\ifshowsolutions \else \vspace*{1.0in}\fi

\end{problemparts}
\fi

\ifshowsolutions \else \newpage \fi

\problem A \emph{simple $k$-cycle} in a simple graph is an
undirected path going through each of $k>2$ vertices exactly once and
ending where it started.  A simple $k$-cycle can be represented by the
sequence of $k$ vertices $v_1, v_2, \ldots, v_k$ along the path.

Note that every $k$-cycle can be represented by many sequences.  For
example, the 4-cycle represented by $1234$ is as the same cycle represented
by $2341$ or $3412$ because a cycle does not have to start at any
particular vertex.  It is also represented by $4321$, because the cycle is
undirected.

\bparts

\ppart How many different sequences of vertices represent a given
$k$-cycle?\brule{0.7in}

\solnospace{\pts{4} $2k$}


\ppart How many $k$-cycles are there in a complete graph (all possible
edges are present) with $n$ vertices.\brule{0.7in}\\
\hint For $n=k=3$, the answer is 1.

\ifshowsolutions \else \vspace{0.7in} \fi

\solnospace{\pts{7}  $P(n,k)/2k$.

The number of ways of choosing a ordered sequence of $k$ vertices is
$P(n,k)$, but each $k$-cycle is represented by $2k$ such sequences.}

\eparts

Suppose we construct a simple $n$-node graph, $G=(V,E)$, randomly as follows:

For every set of two distinct vertices $\set{v,v'}$, toss a biased coin
whose probability of coming up heads is $p$.  The undirected edge between
$v$ and $v'$ is included in $E$ iff the coin comes up heads.  Assume that
all coin tosses are mutually independent.

\bparts

\ppart What is the probability that a $k$-cycle represented by a particular
sequence $v_1, v_2, \dots, v_k$ exists in $G$?

\ifshowsolutions \else \vspace{1.5in} \fi

\solnospace{\pts{4} 
A particular $k$-cycle (call it $e$) will occur only if all of
the edges in that cycle exist in the randomly constructed $G=(V,E)$.  Since
each edge is independently added with probability $p$, we have $\pr{e
\text{ occurs in } G} = p^k$.}

\ppart What is the expected number of $k$-cycles in $G$?  (Note: If
you were not able to solve part (b), you may let $X$ denote the answer
to part (b) and express your answer in terms of $X$, $k$, and $p$).

\ifshowsolutions \else \vspace{1.5in} \fi

\solnospace{\pts{10} 
Let $I_e$ be the indicator random variable of the event that a
particular $k$-cycle, $e$, occurs.  So the number, $N$, of $k$-cycles is
$\sum_e I_e$ where $e$ ranges over all possible $k$-cycles, \ie all
$k$-cycles in the complete graph on $V$.

We know from a previous part that $\pr{I_e = 1} = p^k$, which means that
$\expect{I_e} = p^k$.  Also, the total number of distinct possible
$k$-cycles is $X \eqdef P(n,k)/2k$.

Therefore
\[
\expect{N} = \sum_e \expect{I_e} = X p^k.
\]
}
                                                          
\eparts 

\ifshowsolutions {} \else \newpage \fi

\problem We consider a variation of Monty Hall's game.  The contestant
still picks one of three doors, with a prize randomly placed behind one
door and goats behind the other two.  But now, instead of always opening a
door to reveal a goat, Monty instructs Carol to \emph{randomly} open one
of the two doors that the contestant hasn't picked.  This means she may
reveal a goat, or she may reveal the prize.  If she reveals the prize,
then the entire game is \emph{restarted}, that is, the prize is again
randomly placed behind some door, the contestant again picks a door, and
so on until Carol finally picks a door with a goat behind it.  Then the
contestant can choose to \emph{stick} with his original choice of door or
\emph{switch} to the other unopened door.  He wins if the prize is behind
the door he finally chooses.

To analyze this setup, we define two events:
\begin{description}
\item[$GP$:] The event that the contestant \textbf{g}uesses the door with
the \textbf{p}rize behind it on his first guess.

\item[$OP$:] The event that the game is restarted at least once.  Another
way to describe this is as the event that the door Carol first
\textbf{o}pens has a \textbf{p}rize behind it.
\end{description}

\bparts

\ppart  What is $\pr{GP}$? \brule{0.5in}.  $\prcond{OP}{\bar{GP}}$?\brule{0.5in}.
\solnospace{\pts{2} 1/3, 1/2}

\ppart What is $\pr{OP}$? \brule{0.5in}
\solnospace{\pts{4}
\[
\prcond{OP}{GP}\pr{GP} + \prcond{OP}{\bar{GP}}\pr{\bar{GP}} = 0\cdot 1/3 +
1/2 \cdot 2/3 = 1/3.
\]
}

\ifshowsolutions
{}
\else
\vspace*{0.7in}
\fi

\ppart Let $R$ be the number of times the game is restarted before Carol
picks a goat.

What is $\expect{R}$?\brule{0.8in}\\
You may express the answer as a simple closed form in terms of $p \eqdef
\pr{OP}$.

\solnospace{\pts{3}
$1/(1-p) - 1 = 3/2 -1 = 1/2$.

Think of \emph{not} having to restart as a failure.  So
$\pr{\text{failure}} = 1-p$, and $\expect{R}$ is mean time to failure
minus one---because we are only counting the number of
``successes''---namely, $1/\pr{\text{failure}} - 1$.}

\ifshowsolutions
{}
\else
\vspace*{0.7in}
\fi

\ppart What is the probability the game will continue forever?\brule{0.5in}

\solnospace{\pts{2} 0.  In terms of the previous problem part, this is the
probability of \emph{never} failing.}

\ppart When Carol finally picks the goat, the contestant has the choice of
sticking or switching.  Let's say that the contestant adopts the strategy
of sticking.  Let $W$ be the event that the contestant wins with this
strategy, and let $w \eqdef \pr{W}$.  Express the following conditional
probabilities as simple closed forms in terms of $w$.
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}

\item $\prcond{W}{GP} = $ \brule{0.5in}
\solnospace{\onept 1}

\item $\prcond{W}{\bar{GP}\intersect OP} = $ \brule{0.5in}
\solnospace{\pts{2} $w$}

\item $\prcond{W}{\bar{GP}\intersect \bar{OP}} = $ \brule{0.5in}
\solnospace{\onept
0}
\end{enumerate}

\ppart What is $\pr{W}$? \brule{0.5in}

\solnospace{\pts{5} 1/2, because
\[\begin{array}{rcll}
w & = & \prcond{W}{GP}\pr{GP} 
        & +\ \prcond{W}{\bar{GP}\intersect OP}\pr{\bar{GP}\intersect OP}\\
  &   & & +\ \prcond{W}{\bar{GP}\intersect \bar{OP}}\pr{\bar{GP}\intersect \bar{OP}}\\
  & = & 1 \cdot 1/3 & +\ w \cdot 2/3 \cdot 1/2 + 0 \cdot 2/3 \cdot 1/2\\
  & = & 1/3 + w/3.
\end{array}\]
So $w(1- 1/3) = 1/3$.}

\ifshowsolutions
{}
\else
\vspace*{2in}
\fi

\ppart For any final outcome where the contestant wins with a ``stick''
strategy, he would lose if he had used a ``switch'' strategy, and vice
versa.  In the original Monty Hall game, we concluded immediately that the
probability that he would win with a ``switch'' strategy was $1-\pr{W}$.
Why isn't this conclusion quite as obvious for this new, restartable game?
Is this conclusion still sound?  Briefly explain.

\ifshowsolutions
{}
\else
\vspace*{4in}
\fi

\solnospace{\pts{5}
Switching strategies turns wins to losses for \emph{terminated}
games.  So the probability of win with switch is $t-\pr{W}$ where $t$ is
the probability of termination.  In original Monty Hall, the game obviously
terminated after one door-opening, so $t$ was 1.

The extra complication here is that it is possible for the game to run
forever, but this event has probability 0, so $t$ is still 1, and the
conclusion is still sound.}

\iffalse

\ppart Ben Bitdiddle claims that we didn't need all this analysis to
determine a good strategy.  He says that sticking will be a losing
strategy for the contestant, just as in the original Monty Hall game.  His
reasoning is that, because it is more likely than not that the prize is
behind one of the doors the contestant didn't pick, it's to the
contestant's advantage to switch whenever he has the opportunity.  How
would you explain to Ben, briefly, what the fallacy is in his reasoning?
\fi

\eparts


\iffalse
\ifshowsolutions \else \newpage \fi
\problem 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, and he may try the same
key over and over again).  He continues trying until he finds the key that
works.

\bparts

\ppart What is the expected number of trials of keys the man makes
until he finds the right one?\brule{1in}

\ifshowsolutions {} \else \vspace{1.0in} \fi
 
\solnospace{
Answer: $n$

The problem is the same as Mean Time to Failure.  The probability of
picking the right key on each trial is $1/n$, so mean time to
failure---in this case ``failing'' to pick the wrong key---is $1/(1/n)
= n$.

{\em Alternate Solution:} We can also do this explicitly by calculating the
probability of finding the right key in exactly $k$ trials. Let
$p=1/n$, then
\[
\prob{T=k} = (1-p)^{k-1}p
\]

From the definition of expectation, 

\[
\expect{T} = \sum_{k=1}^\infty{k(1-p)^{k-1}p} 
= p \sum_{k=1}^\infty{k(1-p)^{k-1}}
\]
This is essentially a geometric series, and using the formula from the
Appendix:
\[
\expect{T} = \frac{p}{(1 - (1-p))^{2}} = 1/p = n.
\]
}

\ppart  What is the variance for the number of trials, $T$, of keys
till he finds the right one? \brule{1.0in}

\hint Some relevant summation formulas are in the Appendix.

\ifshowsolutions {} \else \vspace{2in} \fi

\solnospace{
Answer: n(n-1)

The variance of $T$ can be computed directly from the formula,
\[
\variance{T} = \expect{T^2} - \expectsq{T}.
\]
By the definition of expectation we have
\[
\expect{T^2} = \sum_{k=1}^\infty{k^2 (1-p)^{k-1}p} 
= p\sum_{k=1}^\infty{k^2 (1-p)^{k-1}}
\]
This is a series similar to the geometric series and can be derived by
differentiating the infinite geometric series. But we have provided
the formula for this series in the Appendix, So
\[
\expect{T^2} = p \frac{(1 + (1-p))}{(1 - (1-p))^3}
= \frac{2-p}{p^2}.
\]

We know $\expect{T}=p$ from the previous problem, so the variance is
\[
\variance{T}= \frac{2-p}{p^2} - \frac{1}{p^2} = \frac{1-p}{p^2} = n(n-1).
\]
}

\ppart  What is the Chebyshev upper bound on the probability that the
man will make at least a $2n$ trials till success?

% 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}

\solnospace{

One-way bound:
\[
\prob{T \geq 2n} = \prob{T-n \geq 2n-n} \leq 
\frac{\variance{T}}{\variance{T}+ (2n-n)^2}=\frac{n-1}{2n-1}.
\]

Full credit also for using the regular two-way bound.
}

\ifshowsolutions {} \else \vspace{1.5in} \fi

\eparts
\fi

\ifshowsolutions \else \newpage \fi
\problem A gambler plays 120 hands of draw poker, 60 hands of black jack,
and 20 hands of stud poker per day.  He wins a hand of draw poker with
probability 1/6, a hand of black jack with probability 1/2, and a hand of
stud poker with probability 1/5.  Assume the outcomes of the card games are
mutually independent.  %He hopes to win 108 hands per day.

\bparts

\ppart What is the expected number of hands the gambler wins in a day?

\ifshowsolutions {} \else \vspace{1in} \fi

\solnospace{
$120(1/6)+60(1/2)+20(1/5)=54$.
}

\ppart What is the variance in the number of hands won per day?

\ifshowsolutions \else \vspace{1in} \fi

\solnospace{
The variance can also be calculated using linearity of
variance.  For an individual hand the variance is $p(1-p)$ where $p$ is
the probability of winning.  Therefore the variance is
$120(1/6)(5/6) + 60(1/2)(1/2) + 20(1/5)(4/5) = 50/3 + 15 + 16/5 = 250/15 +
225/15 + 48/15 = 523/15 = 34\ 13/15$.
}

\ppart What would the Markov bound be on the probability that the
gambler will win 108 hands on a given day?

\ifshowsolutions {} \else \vspace{1in} \fi

\solnospace{
The expected number of ganes won is 54, so
by Markov, $\pr{R \geq 108} \leq 54/108 = 1/2$.
}

\ppart What would the Chebyshev bound be on the probability that the
gambler will win 108 hands on a given day?  You may answer with a
numerical expression that is not completely evaluated.

\ifshowsolutions {} \else \vspace{1in} \fi

\solnospace{
\[
\pr{R - 54 \geq 54} \leq \frac{V}{V + 54^2} = \frac{523}{523 +
15(54)^2} \approx 1/80.
\]

}

\ppart Apply the Chernoff bound for the probability that the gambler will
win the 108 hands to find the largest integer, $n$, such that the bound is
less than $e^{-n}$.  \hint $\ln 2 \approx 0.7$.

\ifshowsolutions {} \else \vspace{1in} \fi

\solnospace{
Answer: $n=21$.
\begin{align*}
\pr{R \geq 108} & = \pr{R \geq 2\cdot 54}\\
     & \leq \textup{exp}(- (2\ln 2 - 2 + 1)54)\\
     & = \textup{exp}(-108\ln 2 + 54)\\
     & \approx \textup{exp}(- 108\cdot0.7+54)\\
     & \approx \textup{exp}(- 75.6 -54)\\
     & \approx \textup{exp}(- 21.6)\\
     & \approx \cfrac{1}{2,400,000,000}
\end{align*}
}

\iffalse

\ppart
Ben Bitdiddle knows he can get the best estimate using the
approximations to the binomial distribution developed in Notes 12.  He
reasons that since 60\% of the flies are small, 30\% are medium and
10\% are large, the probability that a random fly will be caught is
$0.6(1/6)+0.3(2/3)+0.1(4/5) = 0.38$, so he will use the approximation
for the binomial cumulative distribution function, $F_{1000,0.38}$, to
bound the probability that the spider catches at least 500 flies in 10
hours.

As usual, Ben hasn't got it quite right.

\ppart According to Ben's reasoning, what is the probability that the
spider will catch all 1000 flies that show up during the 10 hours?  Show
that this is not equal to the actual probability.

\ifshowsolutions \else \vspace{1in} \fi

\solnospace{According to Ben, the probability would be $(0.4)^{1000}=
(2/5)^{1000}$.  But the actual probability is
$(1/6)^{600}(2/3)^{300}(4/5)^100$, and we don't even need to evaluate
these expressions to see that they must have different values.  }

\ppart How would you explain to Ben what is wrong with his reasoning?

\ifshowsolutions \else \vspace{1in} \fi

\solnospace{Ben's reasoning would be ok if the event that a fly is large
is independent of whether the next fly is large.  That's not the case
here: after the 99th fly in the first hour, we can predict whether the
100th fly will be large or small.  The number, $R$, of flies caught in 10
hours is actually the sum of a random variable with distribution
$f_{600,1/6}$ and another variable with distribution $f_{400,3/4}$, and
$R$ not only disagrees with Ben's model on the probability that all the
flies will be caught, it does not even have a binomial distribution.}

\ppart For Ben's new distribution function (1000 flies in 10 hours
with probability 0.38 of ensnaring any fly), the expected number of
flies caught is still 380. Ben argues that even though his reasoning
wasn't totally right, we could still use all the same bounds we
calculated in parts (c,d,e) to bound the probability for his
distribution. He is wrong again. Which of the bounds you calculated
still apply? Briefly explain your reasoning.

\ifshowsolutions \else \vspace{1in} \fi

\solnospace{
Expectation is the same, but the variance is different. Markov will
apply, Chebyshev will not. 

I think the same Chernoff bound still applies in this case - is that
true???
}

\ppart NEW, Can you write a formula for the exact probability that the
spider catches at least 500 flies in 10 hours? You do not have to
provide a closed form formula.

\solnospace{Requires a little ingenuity. Lets say that the fly
catches $i$ big flies, where $i \leq 500$. In this case $i \leq 400$
because only 400 big flies pass by. In order to make the quote the fly
must catch at least $500-i$ small flies. The probability of this
overall event ($i$ big ones and at least $500-i$ small ones) is
$(3/4)^i(1/6)^{500-i}$. Since $i$ can take on any value from 0 to 400,
we simply sum over those possibilities. (Note that if we changed the
$3/4$ fraction to $y/6$, then in fact we could easily find a closed
form because the series just becomes a geometric series.)
\[
\pr{X>500} = \sum_{i=0}^{400}{(3/4)^i(1/6)^{500-i}}
\]
}
\fi

\eparts

\end{problems}

%% Only show Appendix in the final (not the solutions)
\ifshowsolutions
{}
\else

\newpage
\section{Appendix}

% \subsection{Dilworth Theorem:}
% If $t$ is the length of the longest chain in a poset $(A, \preceq)$
% then $A$ can be partitioned into $t$ antichains.


\subsection{Combinatorics}

\subsubsection{Summation}
\begin{eqnarray*}
\sum_{i=0}^{n} i^2 & = & \frac{n(n+1)(2n+1)}{6}\\
\sum_{i=0}^{n} x^i & = & \frac{1- x^{n+1}}{1 - x}\\
\sum_{i=0}^{\infty} x^i & = & \frac{1}{1-x}\\
\sum_{i=1}^{n} i x^i & = & \frac{x - (n+1)x^{n+1} + n x^{n+2}}{(1 - x)^2}\\
\sum_{i=1}^{\infty} i x^i & = & \frac{x}{(1-x)^2}\\
\sum_{i=1}^\infty{i^2x^i} & = & \frac{x(1+x)}{(1-x)^3}\\
e^x & = & 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots\\
1 + x & \leq & e^x\\
H_n & \eqdef & \sum_{i=1}^n \frac{1}{i} \quad\quad \text{(Harmonic Numbers)}\\
H_n &\sim& \ln n
\end{eqnarray*}

\subsubsection{Counting}
Given a set of $n$ elements:
\begin{closeitemize}
\item number of $r$-permutations without replacement:
\[P(n, r) \eqdef n (n-1) \ldots (n-r+1) = \frac{n!}{(n-r)!}\]

\item $r$-combinations without replacement:
\[C(n,r) \eqdef \binom{n}{r} = \frac{n!}{(n-r)! \ r!}\]

\item $r$-permutations with replacement ($r$ distinct balls, $n$ distinct
bins):
\[
n^r
\]

\item $r$-combinations with replacement ($r$ identical balls, $n$ distinct
bins):
\[\binom{n+r-1}{r}\]

\item permutations with repetition:
\[\binom{n}{r_1, r_2, \ldots, r_k} \eqdef\frac{n!}{r_1!\ r_2! \ldots r_k!}\]
where $r_1 + r_2 + \cdots + r_k = n$.
\end{closeitemize}

\subsubsection{Binomial Identity}
\[\binom{n}{m} = \binom{n}{n-m}\]

\subsubsection{Multinomial Theorem}
\[(x_1 + x_2 + \ldots + x_k)^n =
	\sum_{r_1 + r_2 + \ldots + r_k = n} \binom{n}{r_1, r_2, \ldots, r_k}
	x^{r_1} x^{r_2} \ldots x^{r_k}\]

\subsubsection{Inclusion-Exclusion}
\[|A_1 \cup \ldots \cup A_n| = \sum_{k=1}^n
(-1)^{k+1} \left( \sum_{S \subseteq \set{1,\dots,n}, |S| = k} | \bigcap_{i
\in S} A_i |\right)\]


\subsubsection{Stirling's Approximation}
\[
n! = \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n e^{a_n}
\]
where
\[
1/(12n+1) \leq a_n \leq 1/(12n).
\]

\subsection{Probability}

\subsubsection{Events}
\begin{eqnarray*}
\pr{\lgunion_{n \in \nats} A_n} & = & \sum_{n \in \nats} \pr{A_n}
\mbox{ for pairwise disjoint } A_n\\
%\item $\pr{A-B}  & = &  \pr{A} - \pr{A \intersect B}$
%
% \item $\pr{A \intersect B}  \le  \pr{A}, \label{ab<a}$
%
\pr{\bar{B}}  & = &  1 - \pr{B} \label{1-b}\\
\pr{A \union B}  & = &  \pr{A} + \pr{B} - \pr{A \intersect B}\\
\pr{A \union B} & \leq & \pr{A}+ \pr{B} \quad \mbox{[Boole's inequality]} \\
%
%\item $\pr{\Intersect_n A_n} \ge 1 - \sum_n \pr{\overline{A_n}}$
%
\prcond{A}{B}  & = &  \frac{\pr{A \intersect B}}{\pr{B}}\\
%\pr{A \mid B} & = & \frac{\pr{B\mid A}\pr{A}}{\pr{B}} quad \mbox{[Bayes Rule]}\\
\end{eqnarray*}

\subsubsection{Law of Total Probability}
Let $B_0, B_1, \ldots$ be disjoint events whose union is the
entire sample space.  Then for all events $A$,
\[
\pr{A} = \sum_{i \in \naturals} \pr{A \cap B_i}.
\]

\subsubsection{Expectation}
\begin{align*}
\expect{R} & \eqdef  \sum_{r \in \reals} r \cdot \pr{R = r}\\
\expect{R} & =  \sum_{r \in \nats} \pr{R > r} & \text{$R$ natural number valued}\\
\expect{\sum_{n \in \nats} R_n} & =  \sum_{n \in \nats} \expect{R_n} & 
 \mbox{providing } \sum_{n=1}^\infty \expect{\abs{R_n}} \text{ converges}\\
\expect{R_1R_2} & =  \expect{R_1}\expect{R_2} & \mbox{for independent }R_1, R_2
\end{align*}

\subsubsection{Conditional Expectation}
Let $B_0, B_1, \dots$ be disjoint events whose union is the entire sample
space.  Then for any random variable, $X$,
\[
\expect{X} = \sum_i \expectcond{X}{B_i} \pr{B_i}
\]
provided that all the expectations exist and are finite.

\subsubsection{Variance}
\begin{eqnarray*}
\variance{R} & \eqdef& \expect{(R-\expect{R})^2}\ =\ \expect{R^2}-\expectsq{R},\\
\sigma_R & \eqdef & \sqrt{\variance{R}}
\quad \mbox{(the \emph{standard deviation} of $R$)},\\
\variance{aR+b} & = & a^2\variance{R}, \mbox{ for } a, b \in \reals,\\
\variance{R_1+ \cdots + R_n} & = & \variance{R_1}+ \cdots + \variance{R_n}
\quad \mbox{for pairwise independent } R_1,\ldots,R_n.
\end{eqnarray*}

\subsubsection{Binomial Distribution}
\begin{eqnarray*}
f_{n,p}(k) & \eqdef & \binom{n}{k} p^k (1-p)^{n-k}\\
\expect{f_{n,p}} & = & np\\
\variance{f_{n,p}} & = & np(1-p)\\
f_{n,p}(\alpha n) & \leq & 2^{-n(H(\alpha,p) - H(\alpha))}
\overbrace{e^{a_n - a_{\alpha n} - a_{(1-\alpha) n}}}^{\sim 1}/
\sqrt{2 \pi \alpha (1 - \alpha) n}
\end{eqnarray*}
where $0 < \alpha < 1$, $a_n$ is from Stirling's
formula, and
\begin{eqnarray*}
H(\alpha,p) & \eqdef & - (\alpha \log_2 p + (1 - \alpha) \log_2 (1 - p)),\\
H(\alpha) & \eqdef & H(\alpha,\alpha) = - (\alpha\log_2 \alpha + (1-\alpha)\log_2 (1-\alpha)).
\end{eqnarray*}

\begin{eqnarray*}
F_{n,p}(k) & \eqdef & \sum_{i=0}^k f_{n,p}(i)\\
F_{n, p}(\alpha' n) & \leq & \frac{1 - \alpha'}{1 - \alpha'/p} f_{n, p}(\alpha' n)
\end{eqnarray*}
where $0 < \alpha' < p$.

\subsubsection{Poisson Distribution}
\begin{eqnarray*}
\pr{X=k} & \eqdef &  e^{-\lambda}\frac{\lambda^k}{k!},\\
%\binom{1/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{1/\delta-k} 
\expect{X} & = & \variance{X} = \lambda.
\end{eqnarray*}

\subsubsection{Markov's Theorem}
If $R$ is a nonegative random variable, then for all $x \geq 0$,
\[
\pr{R \geq  x} \leq \frac{\expect{R}}{x}.
\]

\subsubsection{The Chebyshev Bound}
For any random variable, $R$, and $x > 0$,
\begin{eqnarray*}
\pr{\abs{R-\expect{R}}\geq x} & \leq & \frac{\variance{R}}{x^2},\\
%\pr{\abs{R-\expect{R}}\geq x\sigma_R} & \leq & \frac{1}{x^2},\\
\pr{R - \expect{R} \geq x} & \leq & \frac{\variance{R}}{\variance{R}+x^2}.
\quad \mbox{[One-sided version]}
\end{eqnarray*}

% $$ \pr{R - \expect{R} \leq -x} \leq \frac{\variance{R}}{\variance{R}+x^2}$$

\subsubsection{Chernoff Bound}
Let $T_1, T_2, \dots, T_N$ be mutually independent Bernoulli variables,
and let $T \eqdef T_1 + T_2 + \cdots + T_N$.  Then for all $c \geq 1$,
\[
  \pr{T \geq c \expect{T}} \leq e^{- (c\ln c -c + 1) \expect{T}}.
\]

%% DO WE INCLUDE THESE ??
\iffalse
\subsubsection{Wald's Theorem}

\begin{theorem}
Let $C_1, C_2, \dots,$ be a sequence of nonnegative random variables, and
let $Q$ be a positive integer-valued random variable, all with finite
expectations.  Suppose that
\[
\expcond{ C_i}{Q \geq i} = \mu
\]
for some $\mu \in \reals$ and for all~$i \geq 1$.  Then
\[
\expect{C_1 + C_2 + \cdots + C_Q} = \mu \expect{Q}.
\]
\end{theorem}

\subsubsection{Weak Law of Large Numbers}

\begin{theorem*}
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
independent variables with the same mean, $\mu$, and deviation, $\sigma$.
Then
\begin{equation}\label{Sndev}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x} \leq \frac{1}{n}
\left(\frac{\sigma}{x}\right)^2.
\end{equation}
\end{theorem*}

\subsubsection{Central Limit Theorem}

\begin{theorem}
Let $S_n = \sum_{i=1}^n G_i$ where $G_1, \dots, G_i, \dots$ are mutually
independent variables with the same mean, $\mu$, and deviation, $\sigma$,
and let $S^*_n \eqdef (S_n-\mu)/\sigma$ be the normalized version of
$S_n$.  Then
\begin{equation}\label{normal}
\lim_{n\rightarrow\infty} \pr{S^*_n \leq \beta}= N(\beta)
\end{equation}
for any real number $\beta$, where $N$ is the Normal Distribution.
\end{theorem}
\fi

\fi  %match ifshow...


\end{document}
