%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #11 (added by Ivan)
\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.


\medskip
\solution{
\textbf{Solution:} Get a reliable test by repeatedly asking randomly
chosen psychologists to do the diagnosis and computing the fraction, $f$,
of ``normal'' diagnoses.  Let $s>1/2$ be the probability of a
``normal'' diagnosis on a sociopathic patient.  Diagnose normal if
$f$ is closer to $1/2$ than to $s$.

By diagnosing independently enough times, there is small probability that
$f$ differs from the expected value of a diagnosis by very much (the
expected value is either 1/2 or $s$ depending on whether or not the
patient is normal---we don't know which).  By the Law of Large
Numbers, by Chebyshev's bound, or by the estimation of the binomial
distribution as used in the Gallup Poll example from lecture, if we
diagnose enough times, we can make this probability as small as desired,
so the probability of a correct diagnosis can be as close to 1 as desired.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #12 (added by Ivan)  %previously F97 pfinal
\problem\points{30}

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


\medskip
\solution{
\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$.
}

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

\medskip
\solution{
\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 $1/26$.
}

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

\medskip
\solution{
\textbf{Solution:} We use the Chernoff bound.  Among 1000 students, let
$N$ be the number with at least 235 credits. So $\expect{N}=
(1/7)700+(1/2)300 = 250$ and

\[\begin{array}{rl}
\pr{N \ge 300} & = \pr{X \geq (1.2)250} \leq e^{-(\ln{1.2} + 1/(1.2) -
 1)(1.2)250} = e^{-(\ln{1.2} -.1666)300}\\
& =  e^{-(.182 -.1666)300} \le e^{-4.6} \approx .01.
\end{array}\]
}

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 points)} Solve the following problems concerning
grades at MIT.

\begin{problemparts}

\problempart {\bf (5 points)} Suppose that the average GPA at MIT is
4.0.  Give a tight upper bound on the probability that a random
student's GPA is 4.5 or higher.

\examonly{\vspace{3in}}

\solution{
From Markov's Inequality,

\begin{eqnarray*}
\Pr(\text{GPA} \geq 4.5)
    & \leq &    \frac{4.0}{4.5} \\
    & = &       \frac{8}{9}.
\end{eqnarray*}
}

\problempart {\bf (5 points)} Suppose in addition that the standard
deviation of GPA's at MIT is 0.2.  Give a tight upper bound on the
probability that a random student's GPA is 4.5 or higher, taking this
new information into account.

\solution{From the one-sided Chebyshev inequality,

\begin{eqnarray*}
\Pr(\text{GPA} - 4.0 \geq 0.5)
    & \leq &    \frac{0.2^2}{0.2^2 + 0.5^2} \\
    & = &       \frac{4}{29}
\end{eqnarray*}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\examonly{\newpage}

\problem {\bf (10 points)} A primality testing algorithm takes as
input an integer $n \geq 2$ and outputs either PRIME or COMPOSITE.
The algorithm uses random numbers in a clever way to give a much
better run-time.  An unfortunate consequence is that the algorithm
only ouputs a correct answer with probability $\frac{2}{3}$.  The
answers produced by multiple runs of the algorithm are mutually
independent.

\begin{problemparts}
\problempart {\bf (7 points)} Suppose that we run the algorithm $Q$
times.  Use the Chernoff inequality to lower bound the probability
that the most common answer is correct.  You may treat the
approximation $\ln\left(\frac{3}{2}\right) \approx \frac{2}{5}$ as an equality.

\examonly{\vspace{3.5in}}

\solution{The expected number of wrong answers is $\frac{1}{3}Q$.  Now
we apply the Chernoff bound to upper bound the probability that the
wrong answer is actually the most common answer.

\begin{eqnarray*}
\Pr\left(\text{num wrong} \geq \frac{1}{2} \cdot Q\right)
    & = &   \Pr\left(\text{num wrong} \geq
            \frac{3}{2} \cdot \Ex(\text{num wrong})\right) \\
    & \leq &    e^{-\left(\frac{3}{2}\right)
            \cdot \left(\ln \frac{3}{2} - 1 + \frac{2}{3}\right)
            \cdot \Ex(\text{num wrong})} \\
    & \approx & e^{-\frac{1}{10} \cdot \Ex(\text{num wrong})} \\
    & = &       e^{-\frac{1}{30} Q}
\end{eqnarray*}

Consequently, the most common answer is correct with probabiliy at least

\[
1 - e^{-\frac{1}{30} Q}.
\]
}

\problempart {\bf (3 points)} How many times must the algorithm be
run to ensure that the most common answer is correct with probability
at least $1 - \frac{1}{n}$?  Give the smallest answer that you can
justify.

\solution{Suppose that we run the algorithm at least $30 \ln n$ times.
Then the probability that the most common answer is incorrect is at
most:

\begin{eqnarray*}
e^{-\frac{1}{30} \cdot 30 \ln n}
    & = &   e^{- \ln n} \\
    & = &   \frac{1}{n}
\end{eqnarray*}

Therefore, the most common answer is correct with probability at least
$1 - \frac{1}{n}$.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{20} \textbf {The Florida Election}

Suppose that in one Florida county populated exclusively with
probability theory enthusiasts, there are 10,000 people.  Every one of
them votes independently of one another, and they vote for Bush with
probability $2/5$ and for Gore with probability $3/5$.

\problempart {\bf (2 points)} Let $X$ be a random variable that
represents the number of votes Gore gets in this county.  What is the
expected value of $X$?

\solution{\bigskip {\bf Solution:}

6000.}

\problempart {\bf (3 points)} What is the variance of $X$?

\solution{\bigskip {\bf Solution:}

$V(X) = 10000(2/5)(3/5) = 2400$.
}

\smallspace

\problempart {\bf (5 points)} Using the Markov inequality, give an
upper bound for the probability that Gore gets at least 2600 more votes than
Bush.

\solution{\bigskip {\bf Solution:}

If Gore gets at least 2600 more votes than Bush in the county, then
$X$ must be at least 6300 (since $6300 - 3700 = 2600)$.  By Markov's
inequality,

$$Pr(X \geq 6300) \leq \frac{6000}{6300} = \frac{20}{21}$$
}

\smallspace

\problempart {\bf (5 points)} Using the Chebyshev inequality, give an
upper bound for the probability that Gore gets at least 2600
more votes than Bush.  

\solution{\bigskip {\bf Solution:}

Using the one-sided Chebyshev formula, 

$$Pr(X - Ex(X) \geq t) \leq \frac{V(X)}{V(X) + t^2}$$

with $t = 300$ gives an upper bound of $\frac{2400}{92400} = \frac{2}{77}.$

However, the two-sided Chebyshev inequality is almost as good.

$$Pr(X - Ex(X) \geq t) \leq Pr(|X - Ex(X)| \geq t) \leq \frac{V(X)}{t^2},$$

with $t = 300$ gives an upper bound of $\frac{2400}{90000} = \frac{2}{75}.$
}

\smallspace

\problempart {\bf (5 points)} Using the Chernoff inequality, give a
simplified upper bound for the probability that Gore gets at least 2600 more
votes than Bush, or explain why the Chernoff bound does not apply.  

\solution{\bigskip {\bf Solution:}

Since the 6300 votes Gore would need for this to happen is equal to
$21/20$ times 6000, the expected number of votes Gore gets, the
Chernoff inequality yields

$$Pr(X \geq (21/20)Ex(X)) \leq e^{-\alpha c Ex(X)}.$$

Plugging in $\alpha = \ln c + 1/c - 1$ and evaluating gives that

$e^{-\alpha c Ex(X)} \approx e^{-7.37} \approx 0.000625$.
}
