\documentclass[11pt]{article}
%\usepackage{eepic}
\usepackage{psfig}
\usepackage{amsmath}
%\usepackage{graphics}
%\usepackage{eepic}
\input{macros-course}

\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersect}{\bigcap}

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

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


\begin{document}

\tutn{13}{5/7/99}{May 7, 1999}

\section{Review of Variance and Expectation}
\[
\expect{X} ::= \sum_{\mbox{sample points $s$}} X(s)\prob{s}
= \sum_{x \in  \mbox{range}(X)} x\prob{X=x}
\]

Linearity of expection:
\begin{eqnarray*}
\expect{X + Y} & = & \expect{X} + \expect{Y}\\
\expect{aX} & = & a \expect{X}
\end{eqnarray*}
for any $a \in \reals$.  More generally,
\[
\expect{\sum_{n=0}^\infty R_n} = \sum_{n=0}^\infty \expect{R_n}
\]
for any series $R_0 + R_1 + \dots$ of random variables which is absolutely
convergent at all sample points.

For random variable $X$ with mean $\mu$,
\[
\variance{X} ::= \expect{(X - \mu)^2} = \expect{X^2} - \expectsq{X}.
\]

For any $a,b \in \reals$,
\[
\variance{aX+b} = a^2\variance{X}.
\]

If $X,Y$ are independent,
\begin{eqnarray*}
\expect{X \cdot Y} & = & \expect{X} \cdot \expect{Y},\\
\variance{X + Y} & = & \variance{X} + \variance{Y}.
\end{eqnarray*}


\section{Markov and Chebyshev Bounds}
\subsection{Review}
The theorems of Markov and Chebyshev give upper bounds on the probability
that a random variable differs by a given amount from its mean.  The
Markov bound holds solely under the hypothesis that the variable is
nonegative and the expectation exists, i.e., is finite.  The Chebyshev
bound holds solely under the hypothesis that the variance exists.
(Remember that the variance can exist only if the expectation does.)

\begin{theorem}[Markov's Bound]\label{markov}
If R is a non-negative random variable with finite expectation, then for
all $x > 0$,
\[
\prob{R \geq x} \leq  \frac{\expect{R}}{x}
\]
\end{theorem}

Setting $x = c \cdot \expect{R}$ allows Markov's Theorem to be expressed
in an alternate form:

\begin{corollary}
If R is a non-negative random variable with finite expectation, then for all $c > 0$
\[
\prob{R \geq c \cdot \expect{R}}  \leq  \frac{1}{c}
\]
\end{corollary}

\begin{theorem}[Chebyshev's Bound]\label{chebyshev}
Let $R$ be a random variable with finite variance, and let $x$ be a
positive real number.  Then
\[
\prob{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
\end{theorem}

\subsection{One-sided Chebyshev Bound}
There is a version of the Chebyshev Bound which, like the Markov bound,
bounds the probability that a variable exceeds its mean:

\begin{lemma}[One-sided Chebyshev Bound] For any random variable $X$  and real number $c>0$,
\[\prob{X - \expect{X} \ge c} \le \frac{\variance{X}}{\variance{X} + c^2}.\]
\end{lemma}

The proof is similar to the way the standard Chebyshev bound of
Theorem~\ref{chebyshev} is proved from the Markov bound.

\begin{proof}
Let $\mu = \expect{X}$.
For any $d > 0$,
\[
X - \mu \ge c \mbox{  iff  } X - \mu + d \ge c + d,
\]
and since $c+d>0$, this last inequality implies $(X - \mu + d)^2 \ge (c + d)^2$.
Hence, 
\begin{eqnarray*}
\prob{X - \mu \ge c} & \leq & \prob{(X - \mu + d)^2 \ge (c + d)^2}\\
& \leq & \frac{\expect{(X - \mu + d)^2}}{(c + d)^2} \hspace{1in} \mbox{[by Markov]}\\
& = & \frac{\expect{(X - \mu)^2 + 2d(X- \mu) + d^2}}{(c + d)^2}\\
& = & \frac{\expect{(X - \mu)^2} + 2d(\expect{X} - \mu) + d^2}{(c + d)^2}
\hspace{0.3in} \mbox{[by linearity of $\expect{\cdot}$]}\\
& = & \frac{\variance{X} + d^2}{(c + d)^2} \hspace{0.8in} \mbox{[since $\expect{X} - \mu = 0$]}
\end{eqnarray*}

Letting $d=\variance{X}/c$---the value which minimizes this last
expression---gives
\begin{eqnarray*}
\prob{X - \mu \ge c} & \leq & \frac{\variance{X} + (\variance{X}/c)^2}{(c + \variance{X}/c)^2}\\
\iffalse
 & = & \frac{(c^2 \variance{X} + \varsq{X})/c^2}{((c^2 + \variance{X})/c)^2}\\
 & = & \frac{\variance{X}(c^2 + \variance{X})}{(c^2 + \variance{X})^2}\\
\fi
 & = & \frac{\variance{X}}{c^2 + \variance{X}}.
\end{eqnarray*}
\end{proof}

\section{Team Problems}

\begin{problems}

\problem An urn contains red and blue colored balls.  The fraction of red
balls is $r$ where $0 \leq r \leq 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}.

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 blue
ball, or two red balls in a row, are pulled.  For example, if the colors
of pulled balls are RBBBRBRR, then there are five tries which we indicate
with slashes: /RB/B/B/RB/RR/.  Note that each try consists of one or two
consecutive balls.

\bparts

\ppart What is the expected length of the $i$th try, assuming that there
are at least $i$ tries?

\solution{Given that there is an $i$th try, it is of length 1 iff it
starts with a blue ball.  It is of length 2 iff it consists of 2 red
balls.  Hence,
\[\expect{\mbox{length of $i$th try} \mid \mbox{there is an
$i$th try}} = 1\cdot (1-r) + 2 \cdot r = 1 + r.
\]}

\ppart What is the expected number of tries?

\solution{A series of tries ends iff only the last try consists
of two reds.  We know from lecture that the ``mean time to failure'' is
the reciprocal of the probability of failure, so $\expect{\mbox{num
tries}}$ is the $1/\pr{\mbox{2 reds}}= 1/r^2$.}

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

\solution{ Wald's Thm applies because $\expect{\mbox{length of $i$th try}
\mid \mbox{there is an $i$th try}}$ is the same expression from part
(a) for all $i$.  Hence,
\[
\expect{\mbox{num pulls}} = \expect{\mbox{pulls per
try}} \cdot \expect{\mbox{num tries}} = (1+r)\frac{1}{r^2}.
\]}

\eparts

\problem
Let $R_1,R_2,R_3$ be pairwise independent random variables.
Prove that
\[
\variance{R_1 + R_2 + R_3} = \variance{R_1} + \variance{R_2} + \variance{R_3}.
\]

\solution{Let $m_i = \expect{R_i}$ and $R=R_1+R_2+ R_3$, so $\expect{R} =
m_1+m_2+m_3$ by linearity of expectation.  Now
\begin{eqnarray*}
\lefteqn{\variance{R_1 + R_2+ R_3}}\\
 & = &  \expect{R^2} - \expectsq{R} \quad \mbox{[by formula for $\variance{R}$]}\\
 & = &  \expect{R_1^2 + R_2^2+ R_3^2 + 2(R_1R_2 + R_1R_3 + R_2R_3)} - (m_1
 + m_2 + m_3)^2\\
 & = &  \expect{R_1^2} + \expect{R_2^2}+ \expect{R_3^2} +
 2(\expect{R_1R_2} + \expect{R_1R_3} + \expect{R_2R_3}) - (m_1  + m_2 +
 m_3)^2\\
& & \hspace{1in} \mbox{[by
 linearity of $\expect{\cdot}$]}\\
 & = &  \expect{R_1^2} +\expect{R_2^2} +\expect{R_3^2} + 2(m_1m_2 +m_1m_3
 + m_2m_3) -(m_1 + m_2 + m_3)^2\\
&& \hspace{1in} \mbox{[because $\expect{XY}=\expect{X}\expect{Y}$ for independent $X,Y$]}\\
 & = & \expect{R_1^2} -m_1^2 + \expect{R_2^2} -m_2^2 + \expect{R_3^2}
 -m_3^2 \quad \mbox{[by algebra]}\\
 & = & \variance{R_1} + \variance{R_2} + \variance{R_3}
 \quad \mbox{[by formula for $\variance{R_i}$]}.
\end{eqnarray*}}


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

\bparts

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

\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 the lecture notes, 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.}

\ppart
Is the independence assumption reasonable?

\solution{No.  Some sociopaths may be bad liars and be detected by most
psychologists, and others may be such good liars, they are diagnosed as
normal by most psychologists.  Also, there may be several expert
psychologists whose diagnoses are more reliable than average; this implies
if one expert diagnoses ``normal,'' the diagnosis is likely to be correct,
making it more likely that another expert will also correctly diagnose
``normal,'' so their diagnoses will not be independent of each other.}

\eparts

\problem
Suppose you have learned that the average graduating MIT student's
total number of credits is 200.
\bparts

\ppart Knowing only this average, find a best possible 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 a
century---that is, assume that there is no theoretical upper bound on the
possible number of credits a student may earn.)

\solution{Use Markov's inequality $\prob{X \geq c} \leq \expect{X}/c$, with $c
= 235$, to obtain the upper bound $200/235 \approx 0.85$.}

\ppart \emph{(Added 5/7/99 10pm)} Suppose you are also told that no
student can graduate with fewer than 170 units.  How does this allow you
to improve your previous answer?

\solution{We can now apply Markov's inequality to the nonnegative variable
$X - 170$, obtaining $\prob{X \geq 235} = \prob{X - 170 \geq 235 - 170}
\leq \expect{X - 170}/(235 - 170) = 30/65 \approx 0.46$.}

\ppart Now suppose you further learn that the standard deviation of the
total credits per graduating student is~7.  Give a best possible bound on the
fraction of students who can graduate with at least 235 credits.

\solution{Use the one-way Chebyshev inequality $\prob{X \geq \expect{X}
+ c \sigma_X} \leq \frac{1 }{1+c^2}$ with $c = 5$ to get an upper bound of
$1/26$.}

\eparts

\end{problems}

\end{document}

