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

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

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

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

\def\true{{\bf T}rue:}
\def\false{{\bf F}alse:}
\def\blank{\rule[-2pt]{.5in}{.5pt}}
\def\comp{\circ}

\handout{final}{Final Exam}{May 22, 1998 (typos corrected)}

\begin{closeitemize}
\item This exam is closed book.  Handout 60 with results and formulas is
attached for reference.

\item This exam contains twelve (12) problems totaling 250 points.
Problems are labelled with point values.

\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.

\item GOOD LUCK!
\end{closeitemize}

%%\renewcommand{\arraystretch}{1}
\bigskip

{\bf Your Name}:
\begin{center}
\emptybox{\textwidth}{.4in}
\end{center}


\textbf{Circle the name of your TA}:
\begin{center}
Alex Duran\quad
Stas Jarecki\quad
Al Lee\quad
Edmond Lee\quad
Mark Roh\quad
Tara Schenckel
\end{center}

$\begin{array}{ll}
\mbox{\textbf{Recitation Time}:} & \emptybox{2em}{1.5em}
\end{array}$

\medskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}

\medskip

\hrule

\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|c|c|c|c|}
\hline
Problem&Points&Grade&Grader\\
\hline
\hline
1 &  25 & &\\\hline
2 &  25 & &\\\hline
3 &  25 & &\\\hline
4 &  15 & &\\\hline
5 &  10 & &\\\hline
6 &  20 & &\\\hline
7 &  20 & &\\\hline
8 &  25 & &\\\hline
9 &  15 & &\\\hline
10 &  20 & &\\\hline
11 &  20 & &\\\hline
12 &  30 & &\\
\hline
\hline
Total & 250 & &\\
\hline
\end{tabular}
\end{center}

\newpage

%S97 final

\begin{problems}

\problem\points{25} Circle True/False.    %F97 Pfinal p4 in part

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
        \setlength{\labelwidth}{\leftmargin}%
        \setlength{\itemsep}{10pt}%
%        \setlength{\itemsep}{20pt}%
}

%\item
%Adding $k$ edges to an undirected graph increases its chromatic number
%(the number of colors needed to color the vertices) by at most $k$.

\item $[\exists x: P(x) \implies \forall x: Q(x)]$ implies $[\forall x: [P(x)
\implies \forall y: Q(y)]]$

\item
The number of distinct simple paths in a tree is bounded by $2^{(l+1)^2}$
where $l$ is the number of leaves.

\item
If every vertex of an $n$ vertex simple graph has degree at least $n/2$,
then the expected distance between a randomly chosen pair of distinct
vertices is strictly less than two.

%\item
%Reversing the directions of all edges in a directed graph leaves the
%number of simple directed cycles unchanged.

%\item
%If an undirected graph has the degree of every vertex divisible by a prime
%$p$, then $p$ must evenly divide the number of edges.

%\item
%Let $f:A\to B$ and $g:B\to C$.  If $g\comp f$ is a surjection, then both
%$f$ and $g$ are surjections.

\item
If there is a surjection from $A$ to $B$ and also a surjection from $B$ to
$A$, then there is a bijection from $A$ to $B$.

\item In the polynomial expansion of $(x - 1)^{123}$, every
coefficient occurs exactly twice.

\item Assume each Boolean variable is randomly assigned true or false with
equal likelihood and the choices are independent.  Then $\pr{(p_1 \vee p_2
\vee \overline{p_3})\wedge(\overline{q_1} \vee q_2 \vee q_3)\mbox{ is true}} \le 3/4$.

\item The function $f:\reals \rightarrow \reals$ defined by
$ f(x) = x^3$ is a bijection.

%\item The relation $\{(A,B) \mid \mbox{ there is a surjection from $A$ to
%$B$}\}$ is transitive.

\item If $r$ is a real number and not an integer, then the set of infinite
subsequences of the decimal representation of $r$ is uncountable.

\item There is a surjection from the real line onto the plane.

\item Every countable powerset is finite.

\item All $n$-vertex simple graphs with chromatic number $n$ (that is,
that require exactly $n$-colors) are isomorphic.

\item $n!= 2^{f(n)}$ for some $f = \Theta(n \log n)$.
\end{list}

\newpage


\iffalse
For each of the following statements, indicate whether it is true or
false.  If it is true, sketch a proof; if it is false, describe a
counterexample

\bparts

%\ppart\points{5} All nine-vertex trees with exactly two eight-vertex paths
%are isomorphic.

%\vspace{2.5in}

%\ppart\points{5} If a simple graph has a cycle, then it has a simple
%cycle.

\iffalse
\vspace{2in}

\ppart\points{10} If an seven-vertex graph has sixteen edges, then it is
connected.
\vspace{2.5in}
\fi

%\ppart\points{5} In the polynomial expansion of $(x - 1)^{123}$, every
%coefficient occurs exactly twice.

%\vspace{1.5in}

\ppart\points{10}
\fi


\newpage

\problem\points{25} Let $T:\nats\to\nats$ be defined by the following
recurrence.  Prove that $T(n)= \Theta(n)$. \hint Find a constant $a$ such
that $T(n) \le an + 8$ for all $n\ge 0$.

\begin{displaymath}
T(n) = 
\begin{cases}
8  & \text{if $n < 5$},\\
T\left(\floor{\frac{n}{5}}\right)+T\left(\floor{\frac{3n}{4}}\right)+8n
&  \text{if $n \ge 5$}.\\
\end{cases}
\end{displaymath}

\vspace{5in}


\newpage
\problem \points{25} Short answers.  No need to be rigorous, though
partial credit may be given based on the derivation.

\bparts


\ppart \points{8} %F97 Q1 p9

We'll say an integer $n\ge 2$ is ``good'' providing that in any set of 401
integers, there are three integers, $j$, $k$ and $l$, such that the
pairwise differences, $j-k, j-l, k-l$ are multiples of $n$.  There is a
bound $m \in \naturals$ such that $n$ is good iff $2 \le n \le m$.  What is
$m$?

\vspace{1.5in}

\iffalse

\ppart \points{5} How many simple paths of length 7 are there in an $n$
vertex complete simple graph?

\vspace{.7in}

% \textbf{Solution:} $(n)_7 = n(n-1)\cdots(n-6)$
\fi

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

\vspace{.7in}


\ppart \points{7} The space shuttle runs 5 identical computers so that if
two goof, the other three will out-vote them with the right answer.  If
each computer goofs independently with probability $g$, what is the
probability of getting the right answer in a given computation?

\vspace{1.5in}


\ppart \points{5} Suppose two 6-sided dice are thrown, and then as many
coins are flipped as the sum of the dice.  The dice and coins are fair.
What is the expected number of coins showing heads?

\vspace{.7in}


\eparts

\newpage

\problem \points{15} %F96 Q2 p6

\bparts 

\ppart\points{5} Prove, by direct calculation, that 
for $1 \leq r \leq n$,
\[\binom{n}{ r} = \frac{(n-r+1)}{r} \binom{n}{ r-1}.\]

\vspace{2.5in}


\ppart\points{10} Now prove the same identity combinatorially by comparing
two procedures for choosing a committee of $r$ members out of $n$ people
and also choosing a committee member to be chairman.


\vspace{5in}

\eparts

\iffalse

\problem\points{10} Write a closed form expression for the number of
shuffles of a deck of 52 cards in which no two aces are adjacent.  Briefly
explain your reasoning.

\vspace{3in}

\iffalse
\textbf{Solution:} must have at least 1 non-ace in the 3 places between the aces.
So select three non-aces in $\binom{48}{3}$ ways.  Now permute the
remaining $52-3= 49$ cards in $49!$ ways.
\fi
\fi



\iffalse

\problem\points{10} Write a closed form expression for $\Pi_{k=1}^n
2^{2^k}$.

\vspace{3in}
\fi


\newpage
%S97 Q2

\problem \points{10}
Prove that the number of sequences of eleven letters which can be
made from the letters in MISSISSIPPI is not divisible by four.

\vspace{4in}


\newpage
\problem\points{20}

Prove that there are 16,800 permutations of the letters
$\set{a,b,c,d,e,f,g,h}$ such that neither the letters $\set{a,b,c}$ nor
the letters $\set{d,e}$ occur in order.  For example, $fbgadceh$ is not
allowed because $d$ occurs before $e$, and $fagbecdh$ is not allowed
because $a$ occurs before $b$ and $b$ occurs before $c$, but $fbgaedch$ is
OK.

\vspace{4in}

\newpage
\problem\points{20} %F97 9 pfinal

A high blood pressure test is known to be $90\%$ accurate in detecting
high blood pressure (that is, $10\%$ false negatives), whereas only $5\%$
of people without high blood pressure will falsely test positive.  Suppose
$30\%$ of the population has high blood pressure.  Given that a person
picked at random tests positive, what is the conditional probability that
this person has high blood pressure?

\vspace{3in}


\end{problems}

\newpage

The two problems are based on the following scenario: an urn contains red,
white and blue colored balls.  The fraction of red, white, and blue balls
is $r,w,b$, respectively (so $r + w + b =1$).  A gambler repeatedly pulls
a ball at random from the urn.  That is, at any point during succesive
pulls, each ball in the urn is equally likely to be the next one pulled.
The gambler puts the ball back into the urn before making the next pull.
He keeps pulling balls until he pulls \emph{two red balls in a row}.


\begin{problems}

\iffalse

\problem\points{25}

Suppose their are $m$ balls in the urn to begin with, and the gambler
pulls a series of $n \leq m$ of them \emph{without} replacing any.

\bparts

\ppart \points{15} Write an expression involving binomial coefficients for
the probability that the gambler pulls exactly $n_r$ red balls and $n_w$
white balls.

\vspace{1.5in}

\iffalse

\textbf{Solution}: Let $n_b = n - n_r - n_w$ be the number of blue balls
pulled.  Let $R = rm, W = wm, B = bm$ be the number of balls of each color
initially in the urn.

\[\binom{R}{n_r}\binom{W}{n_w}\binom{B}{n_b}/\binom{m}{n}\]
\fi

\ppart\points{10} Write an expression for the probability that the Gambler pulls
\emph{all} the red balls.  (You may assume $n$ is at least as large as the
number of red balls.)

\vspace{1in}

\iffalse
\textbf{Solution}: 
\[\binom{m-R}{n-R}/\binom{m}{n}\]
\fi

\eparts
\fi


\iffalse

\problem\points{25} Suppose the number of balls in the urn is unknown, but the
gambler pulls a series of $n$ balls \emph{replacing} each ball into the
urn before making the next pull.

\bparts

\ppart\points{5} Write an expression for the probability that the gambler
pulls $n_r$ red balls and $n_w$ white balls, where $n_r+n_w \le n$.

\vspace{1.5in}

%\textbf{Solution}: $\binom{n}{n_r,n_w,n_b}r^{n_r}w^{n_w}b^{n_b}$

\ppart\points{2} What is the expected number of red balls the Gambler pulls?

\vspace{.5in}

%\textbf{Solution}: $rn$

\ppart\points{3} What is the variance of the number of red balls pulled?

\vspace{1in}

%\textbf{Solution}: $nr(1-r)$

\ppart\points{5} What is the expectation of the sum of the number of red and
white balls pulled?

\vspace{1.5in}

\ppart\points{5} What is the variance of the sum of the number of red and
white balls pulled?

\vspace{1.5in}

\iffalse
\textbf{Solution}: It's $\variance{1-\mbox{num(blue)}} =
\variance{\mbox{num blue}} = nb(1-b) = n(1-r-w)(r+w),$ NOT the sum of the
var's of red and whites.
\fi

\eparts
\fi

\iffalse

\newpage

\problem\points{25} The gambler pulls a series of balls from the urn
replacing each ball into the urn before making the next pull.  He
keeps pulling and replacing balls until he pulls a red ball.

\bparts

\ppart\points{3} To be precise about the sample space in this case, we let
the sample points be the stopped sequences, namely, the finite sequences
of white and blue balls ending with a red ball.  We also add one more
sample point corresponding to the event that the stopping condition does
not occur, that is, that the Gambler keeps pulling and replacing balls in
the urn forever.  Explain how to assign appropriate probabilities to these
sample points.

\vspace{2in}

\ppart\points{7} Verify that the result satisfies the conditions of a probability
space.

\vspace{3in}

\ppart\points{5} Explain why the previous sample space is countable.

\vspace{3in}

\ppart\points{6}\label{uncountable} Suppose that instead of a single
``runs forever'' sample point, we included all the infinite sequences of
colored balls which do not satisfy the stopping condition.  Prove that the
resulting sample space is uncountable.

\vspace{3in}

\ppart\points{4} What is the expected number of balls pulled before the
gambler pulls a red ball?

\vspace{.5in}

\iffalse
\ppart\points{5} Prove that there are more events in the sample space of
the previous part than there are real numbers.  That is, there is an
injection from the reals to the set of events, but not from the set of
events into the set of reals.  In your proof, you may assume any of the
results proved in the lectures or notes, without having to prove them
yourself.
\fi

\eparts
\fi


\iffalse

\problem\points{15} As in the previous problem, the gambler pulls a series
of balls from the urn replacing each ball into the urn before
making the next pull.  In this case, he stops when he pulls a red ball for
the second time.

\bparts

\ppart\points{5} Write an expression for the probability that the gambler
pulls $n$ balls.

\vspace{.5in}

%\textbf{Solution:} $\binom{n}{2}r^2(1-r)^{n-2}$

\ppart\points{10} What is the expected number of balls pulled?

\vspace{.5in}

%\textbf{Solution:} $2/r$

\eparts
\fi

\problem\points{25}
\bparts

\ppart\points{5} Let $N_n$ be the event that at least $n$ balls have been
pulled and the $n$th ball is \emph{not} red; let $p_n = \pr{N_n}$.  Write
an expression in terms of $p_n$ for the probability that the Gambler stops
pulling after exactly $n+2$ balls.

\vspace{1in}

\ppart\points{10} Write a linear homogeneous recurrence equation for
$p_{n+2}$ in terms of $p_{n+1}$ and $p_n$.


\vspace{1.5in}

%\textbf{Solution}: $p_{n+2} = (1-r)p_{n+1} + (1-r)rp_n$.

\ppart\points{5} Suppose $r=2/3$.  Write a closed form expression for 
$p_n$.

\vspace{1.5in}


\iffalse

\ppart\points{5} \emph{Outline in a few words} how the previous result could
be used to calculate the expected number of balls pulled by the Gambler.
You need not actually carry out the calculation.

\vspace{2in}

\iffalse
\textbf{Solution:}  $\expect{\mbox{num balls}} = \sum_{n=0}^\infnty np_n$
The generating function for $np_n$ is the derivative of a geometric
series, which we know how to sum and differentiate.  Its value at 1 will
then be the sum.
\fi
\fi

\eparts

\newpage

\problem\points{15} The sequence of pulls by the Gambler can be regarded
as a sequence of \emph{tries}, where the first try begins with the first
ball pulled.  Each try consists of a sequence of pulled balls continuing
until either a white ball, a blue ball, or two red balls in a row, are
pulled.  For example, if the colors of pulled balls are RBBWRWRR, then
there are five tries which we indicate with slashes: /RB/B/W/RW/RR/.
Note that each try consists of one or two consecutive balls.

\bparts

\ppart\points{5}  What is the expected length of a try?

\vspace{1in}


\ppart\points{5}  What is the expected number of tries?
\vspace{1in}

\ppart\points{5} Write a simple expression in terms of your answers to
the previous parts of this problem for the expected number of balls pulled
by the Gambler.  Briefly justify your reasoning, citing appropriate
results from the attached Handout 60.

\vspace{4in}

\eparts

\newpage

\problem\points{20}
Let $R_1,R_2$ be random variables such that $\expect{R_1R_2} =
\expect{R_1}\expect{R_2}$.
Prove that
\[\variance{R_1 + R_2} = \variance{R_1} + \variance{R_2}.\]
\vspace{5in}


\iffalse

\ppart\points{10} Give an example of $R_1,R_2$ such that $\expect{R_1R_2}
= \expect{R_1}\expect{R_2}$ but $R_1$ and $R_2$ are \emph{not}
independent.  Include a proof that your example has these properties.

\vspace{4in}

\eparts
\fi

\newpage

\problem\points{25} Psychological diagnosis of sociopaths is notoriously
unreliable.  For example, a random psychologist is as likely to diagnose a
normal patient as sociopathic as he is to recognize that the patient is
normal.  A random psychologist is actually slightly \emph{less} likely to
correctly diagnose a real sociopath than not---sociopaths are really good
actors.  In these circumstances it might seem there was no reliable way to
diagnose sociopaths, but in theory there is a way---if we have a large
enough population of psychologists who reach their judgements
independently.  Explain how to obtain a reliable diagnosis in this case.
Briefly explain why your method will be reliable, citing appropriate
results from class.  A qualitative answer is all that's required---you
need not come up with any numerical estimates or growth rates.

\vspace{4in}

\iffalse \textbf{Solution:} Get a reliable test by repeating the
unreliable one enough times that there is small probability that the
average of the repeated test answers differs from the actual expected
value of the unreliable test by more than the difference of the expected
value of the unreliable test on contaminated water and on uncontaminated
water.
\fi


\newpage

\problem\points{30}  %F97 pfinal

\bparts

\ppart\points{10} Knowing only that the average graduating MIT student's
total number of credits is 200, find a tight upper bound for the fraction
of MIT students graduating with at least 235 credits.  (Ignore the fact
that students who graduate do so after at most 700 years; that is, assume
that there is no theoretical upper bound on the possible number of credits
a student may earn.)

\vspace{2in}

\iffalse
\textbf{Solution:}

We use Markov's inequality $\Pr(X \geq c) \leq E[X]/c$, with $c = 235$,
to obtain the upper bound $200/235 \approx .85$.  \fi

\ppart\points{10} Assuming in addition only that the standard deviation of
the total credits per graduating student is~7, give a tight bound on the
fraction of students who can graduate with at least 235 credits.

\vspace{2in}

\iffalse
\textbf{Solution:}

We use the one-way Chebychev inequality 
$\Pr(X \geq E[X] + c \sigma_X) \leq \frac{1 }{1+c^2}$
with $c = 5$ to get an upper bound of $\frac{1 }{26}$
\fi

\ppart\points{10} Different information about MIT credits is now provided
by the Registrar.  The standard deviation is not 7 after all.  Instead,
the registrar reports that 30\% of past graduates are EECS majors and half
of them had 235 or more credits.  Only $1/7$th of the non-EECS students
graduated with that many credits.  Use this information and the Chernoff
bound to give a tight upper bound on the probability that among 1000
randomly chosen graduating students, at least 300 have 235 or more
credits.  (Since you don't have a calculator, you may leave $\ln$ and $e$
in your answer).

\iffalse \textbf{Solution:} We use the Chernoff bound.  Among 1000
students, the expected with more than 235 credits is $(1/7)700+(1/2)300 =
250$.

$\Pr(N \ge 300) = \pr{X \geq (1.2)250} \leq 
e^{-(\ln{1.2} + 1/(1.2) - 1)250} = e^{-(\ln{1.2} -.1666)250} = 
e^{-(.182 -.1666)250} \le e^{-3.9} \approx .02$
\fi


\eparts


\iffalse

\newpage

\problem\points{25}  %F96 final

A pentium chip has 753 components.
Past experience with Intel engineers indicates that 
225 of these components fail with probability $1/15$,
400 fail with probability $1/10$, 
and 128 fail with probability $1/8$.
Assume that all component failures are independent.
\bparts
%\setlength{\itemsep}{3.5in}	
\ppart
What is the expected number of components that will fail on a pentium chip?
\vspace{2in}

\ppart
Compute the variance for the number of components that will fail on a
pentium chip.

\vspace{2in}

\ppart
Derive a formula for the exact probability that a pentium chip has 
no failures.

\vspace{3in}

\ppart
Derive an upper bound of the form $e^{-x}$, where $x$ is an integer,
on the probability that a pentium chip has no failures.

\vspace{2in}

\eparts

\fi

\iffalse

\newpage

%F96 final
\problem\points{15}

In an effort to relieve congestion on the Internet, ARPA is
considering building SUPERNET.  SUPERNET is a heierarchical routing
network for which the country is divided into 6 regions: New England
(NE), New York (NY), Washington DC (DC), the south (SO), Los Angeles
(LA), and the rest of the country (RE).  The 6 regions will be
connected with 9 ultra-high bandwidth, bidirectional links so that
region $u$ is directly connected to region $v$ if and only if 
$u\in\{\mbox{NE,NY,DC}\}\mbox{, and}~ v\in\{\mbox{SO,LA,RE}\}$.

\bparts

\ppart
Draw the graph corresponding to the ultra-high bandwidth connections.\\
Is the graph planar? Is it bipartite?
%\vspace{5in}

\ppart
When a message on the SUPERNET needs to go from one region to another,
it travels on a shortest path through the ultra-high bandwidth
network.  In the event that there is more than one shortest path, then
a shortest path is picked uniformly at random from among the shortest
paths.  (Note that there is always a unique shortest path or exactly
three shortest paths.)  ARPA engineers believe that there will be 15
million messages per second emanating from each region and that each
such message has a random destination (i.e., each message is destined
for each of the 5 other regions with equal probability--the message
cannot stay within the region).  What is the expected message load on
each ultra-high bandwidth connection? When counting load,
make sure to count messages that are travelling in either direction.
({\em Hint}: The expected load on each edge is the same.) 

%\vspace{3in}

\ppart
Because of budget cutbacks, ARPA engineers have been forced to do
without buffers and so if ever the message traffic across a link
during a second of time exceeds its capacity, the entire SUPERNET will
come to a crashing halt.  The president has decreed that the
probability of such a crash during the next 4 years should be at most
$10^{-9}$.  ARPA has the option of buying links with capacity
$\sqrt{E},
E/2, .99E, E, 1.01E, 2E, 2.718E$, and $E^2$ (where $E$ is the expected load
that you computed in part (b) above), but the cost of a link goes up with
its capacity.  Your job is to decide the least expensive link that
will fit within the President's mandate.  You may assume that the
destinations of each of the messages are mutually independent.
There are at most $e^{19}$ seconds in 4 years.\\

Which capacity should you choose?  Show your work and justify your
answer.  Compute an upper bound of the form $e^x$, where $x$ is an
integer on the probability that SUPERNET crashes in the next 4 years
given your choice of link capacity.  (You may use the following
facts: $e^{-21}<10^{-9}<e^{-20},~
\ln(1.01)+1/1.01 = 1.00005,~ \ln 2 +1/2 = 1.19$. These estimates are
close enough for government work.)

\eparts
\fi

\iffalse
\newpage

\problem\points{30}

The spider is expecting guests and wants to catch 500 flies for her
dinner.  The expected number of flies caught in the web per hour is $40$.

\bparts

\ppart\points{10}
 
What is an upper bound to the probability that the spider will have caught 500
flies in 10 hours?

\vspace{2in}

\iffalse

\textbf{Solution:} 

Using Markov's inequality we obtain
$\Pr(X =(5/4)400) \leq \Pr(X \geq (5/4)400) \leq 4/5$
\fi
 
\ppart\points{10}

What is a lower bound to the probability that the spider will have to 
wait more than 10 hours to catch 50 flies?

\vspace{2in}

\iffalse

\textbf{Solution:} 

The event that the fly has to wait more than 10 hours to catch 500 flies
is the same as the event that the spider will catch less than 500 flies in
10 hours.  This is the complement of the event that the spider catches at
least 500 flies in 10 hours, so by part (a) the answer is $1 - 4/5 = 1/5$.
\fi

\ppart\points{10}

The spider checks her log and discovers that the standard deviation for
the number of flies caught in an hour is 20.  Find an upper bound on the
probability that the spider will catch 500 flies within 10 hours, using
this additional information.

\vspace{3in}

\iffalse
\textbf{Solution:} 

Since the standard deviation for the number of flies caught in one hour is 20, 
the standard deviation for the number of flies caught in 10 hours is 
$\sqrt{(10 \cdot 20^2)} = 20 \sqrt{10}$

Using Chebychev's inequality we obtain
$$
\Pr(X = 500) \leq \Pr(X \geq 400 +  \frac{\sqrt{10}}{ 2} \cdot 20\sqrt{10}) 
\leq \frac{1}{ c1+\frac{\sqrt{10}}{ 4}^2} = \frac{2}{ 7}
$$
\fi

\ppart

\points{10}

The spider discovers additional interesting information.  
The standard deviation is not 20 after all, but
100 flies pass by her web every hour.  
60 of these flies are quite small and are caught with probability $1/6$ each.
40 of the flies are big and are caught with probability $3/4$ each.
Assume all fly interceptions are mutually independent.
Using this information, find an upper bound on the probability that 
the spider will catch 500 flies within 10 hours.
(Since you don't have a calculator, you may leave $\ln$ and $e$ in 
your answer).

\vspace{3in}

\iffalse
\textbf{Solution:} 

We use the Chernov bound. The expected number 
of flies caught every hour is $(1/6)60+(3/4)40 = 40$,
so the expected number of flies in 10 hours is 400.

$\Pr(X = 500) \leq \Pr(X \geq \frac{5}{ 4} 400) \leq 
e^{-(\ln\frac{5}{ 4} + \frac{4}{ 5} - 1)500} =
e^{-(\ln\frac{5}{ 4} - \frac{1}{ 5})500} = 9.45 \cdot 10^{-6}$

\eparts
\fi

\eparts
\fi

\end{problems}


\end{document}
