\message{ !name(H59-Notes24.tex)}
\message{ !name(H59-Notes24.tex) !offset(-2) }
\documentstyle[12pt,twoside,amsfonts, amssymb,amstex]{article}
\input{macros-course}

\parskip1.5ex
\parindent0pt

\newcommand{\var}[1]{{\rm Var}[#1]}

\begin{document}
\handout{notes24}{Notes 24}{December 5, 1995}

Last week we spent a lot of time talking about the expected values of
random variables.  One thing we saw is that it is possible for a
random variable to have expected value 1 even though it is never
actually anywhere near 1 (e.g., if I flip two coins that are tied
goether, what is the expected number of heads?).  This week, we are going to study {\em
  deviations from expectation.} We will study the likelihood that a
random variable has a value distant from its expectation and give
methods for proving that probability is small.

\section{Markov's Theorem}
\begin{theorem} If $R:S\rightarrow R^+$ is a random variable, then for all k,
\[Pr(R\geq  K)\leq \frac{E[R]}{K}. \]
\end{theorem}
In other words, if Exp is small, then R is not likely to be large.
\begin{corollary}
If  $R:S\rightarrow R^+$, then for all positive real number c,
\[Pr(R\geq  cE[R])\leq \frac{1}{c}. \]
\end{corollary}

\begin{proof} (of corollary) Just write K=cE[R] in the theorem. \end{proof}

As an example, if we know that the average person weights $140$ pounds,
then we know that at most half the people in the world weight over
$280$ pounds (maybe lots fewer, but this is all Markov's theorem tells
us).

\begin{proof} (of theorem)  \[E[R]=\sum_x xPr(R=x)\geq \sum_{x\geq K}
 xPr(R\geq x)\geq \]

\[\geq \sum_{x\geq K} KPr(R=x) =K\sum_{x\geq K}Pr(R=x)=KPr(R\geq K) \]
Comparing the first term of the first inequality and the last one of the second
we get the assertion of the theorem. \end{proof}

Another example: in the hat problem, what is the probability $k$ people
get their hats back?  At most $1/k$.



Note that Markov's theorem doesn't hold if $R$ can be negative.  For
example, consider a variable that is $\pm 1$ with probabilities $1/2$
each.  It's expectation is 0!  So Markov's theorem is clearly
violated.

There is a converse to Markov's Theorem for bounding hwo far {\em
  below} expectation yuo can go:
\begin{theorem}
If $\Pr[R>u] = 0$, then 
\[
\Pr[R > k] \ge \frac{E(R)-k}{u-k}
\]
Proof is like before.

As an example, if the average score on a test is $75\%$, then 
\[
\Pr[R>50] \ge \frac{75-50}{100-50}=1/2
\]


\section{Variance and Chebishev's theorem}

Markov's Theorem is very general but very weak.  When we flip $n$
coins, we expect $n/2$ heads.  But we know that the probability of $n$
heads is much less than the $50\%$ described by Markov' Theorem.  How
can we formalize this intuition?

Let's consider a random variable $R$ with mean $\mu$.  What we are
interested in is the deviation of the random variable from tis mean,
namely $R-\mu$.  This is a random variable, so there are are obvious
ways to study it.  For example, the most obvious measure of this
quantity is
\[
E[R-\mu].
\]
Unfortunately, $E[R-\mu] = E[R]-\mu = 0$, so the positive and negative
deviations cancel out and give us no information.  So perhaps the
thing to do is measure the average {\em magnitude} of the deviation
without worrying about its direction.  This suggests computing
$E[|X-\mu|]$.  However, absolute values are painful in analysis (not
differentiable, etc.) so another approach is more effective:

\begin{defin} The variance of R is 
\[\var{R}=E[(R-E[R])^2] .
\] 
\end{defin}

\subsection{Standard Deviation}

People often like to ``renormalize'' the variance:
\begin{defin} The standard deviation of R is  \[\sigma_R=\sqrt{Var(R)}.\]
\end{defin}
Thus the variance is the square of the standard deviation.  It follows
that the stanrdad deviation has the same units (days, people, etc.) as
the original random variable and its expectation.  On an {\em
  intuitive} level, the standard eviation measure $E[|X-\mu|]$.

You will often see a statement like ``the temperature tomorrow will be
$30^\circ\pm2^\circ$.  That ``plus-minus'' term is often a reference
to the standard deviation of the measurement under some probability
model.

Following standard practice, we will use $\sigma$ to denote the
standard deviation of a random variable.  The variance is then
$\sigma^2$.

\subsection{An Example}

The larger the variance is, the more likely R is to be far from E[R].
Consider two gambling games.
\begin{description}
\item[Game A.] With probability $2/3$. you win $2\$$.  Otherwise, lose
  $\1$$.
\item[Game B.] With probability $2/3$. you win $1002\$$.  Otherwise, lose
  $2001\$$.
\end{description}
Which would you play?  In a lot of ways they are the same:
\begin{itemize}
\item Each has $2/3$ probability of winning.
\item Each has expected winnings $1\$$.
\end{itemize}
However, the second game is ``riskier.''  Let's compute variances:
\begin{itemize}
\item Game A:
\begin{align*}
A-E[A] &=\begin{cases}
   1 &\text{with probability $2/3$}\\
   -2 &\text{with prob. $1/3$}
   \end{cases}
(A-E[A])^2 &=\begin{cases}
   1 &\text{with probability $2/3$}\\
   4 &\text{with prob. $1/3$}
   \end{cases}
\var{A} &= 1\cdot2/3+4\cdot1/3\\
&= 2
\end{align*}
\item Game A:
\begin{align*}
B-E[B] &=\begin{cases}
   1001 &\text{with probability $2/3$}\\
   -2002 &\text{with prob. $1/3$}
   \end{cases}
(A-E[A])^2 &=\begin{cases}
   1002001 &\text{with probability $2/3$}\\
   4008004 &\text{with prob. $1/3$}
   \end{cases}
\var{A} &= \frac23(1002001)+\frac13{4008004)
&=2004002
\end{align*}

In other words, playing a game with high variance is a serious risk:
we can win a lot, but we can loose a lot, too. Playing another game
with the same expectation of winnings but less variance we can hope
for the same average gains risking less.  In investments, many people
prefer bonds to stocks because, although the expected earnings in
bonds are lower, the variance is much lower too.  They are willing to
pay for risk-reduction.

\subsection{The Chebyshev Bound}

A variable with small variance is unlikely to be far from its mean.
With Markov's Theorem, we deduced that given a mean IG of 100, onlt
$/12$ the people can have IQ bigger than $200$.  But suppose we know
that the standard deviation in IQ is $10$.  Then intuitively, it
should quite rare to have an IQ bigger than $110$.  We can show that
in fact only $1/100$ people have IQ bigger than $200$.  


Chebishev's theorem formalizes this observation:
\begin{theorem}
For any random variable R, 
\[Pr(|R-E[R]|\geq c\sigma_R)\leq \frac{1}{c^2} .\] 
\end{theorem}

\begin{example}
In IQ, $\sigma_R=10$ while $\mu_R=100$.  Therefore, 
\begin{align*}
\Pr[R \ge 200] &=\Pr[(R-100)\ge100]\\
&=\Pr[|R-\mu_R| \ge 10\sigma_R
&\le 1/100
\end{align*}

\begin{proof}
  Clearly \[Pr(|R-E[R]| \geq c\sigma_R ) = Pr(|R-E[R]|^2 \geq
  c^2\sigma_R^2) .\] Let us apply the Markov theorem with
  $K=c^2\sigma_R^2$ on the right-hand-side to get
\[Pr(|R-E[R]| \geq c\sigma_R ) \leq \frac{Ex((R-E[R])^2)}{c^2\sigma_R^2}=\]
\[=\frac{Var(R)}{c^2Var(R)}=\frac{1}{c^2} .\]
\end{proof}

\begin{example} At most 1/4 of the students score more than 2 standard 
  deviations away from the mean, whatever the set of scores is.
  Indeed, if R is the score of a random student, then
\[Pr(|R-E(R)|\geq 2\sigma_R)\leq \frac{1}{4},\]
which means that at most 1/4 of all the scores can be that far from the
average.
\end{example}


Chebyshev's theorem holds for any distribution.  For some
distributions, you can prove a much better bound.  For example, if $R$
has a binomial distribution, we will see next time that
\[
\Pr[R-E[R] \ge c\sigma_R] =O(e^{-c^2/2})
\]
a much stronger bound than $1/c^2$.

\subsection{A Different Variance Formula}

\begin{theorem}
For all R, we have
\[Var(R)=E[R^2]-E[R]^2.\] \end{theorem}
\begin{proof}
\begin{align*}
Var(R)&=Ex((R-E[R])^2)\\
&=Ex(R^2-2RE[R]=E[R]^2) \\
&=E[R^2]-2E[R]E[R]+E[R]^2\\
&=E[R^2]-E[R]^2.
\end{align*}
 \end{proof}


This formula is often more useful to compute variances than the previous one.
For example, if $R$ is a regular die roll,
\begin{align*}
\var{R} &= \frac16(1+4+9+\cdots+36)-(3.5)^2\\
&= 15\frac16-12\frac14 = 2\frac{11}{12}
\end{align*}

This equation is useful computationally.  It means that you can
compute variance in a single pass through a stream of data, since you
can keep a running total for $X$ and $X^2$ and at the end, divide by
the number of sample points.  The other equation would require two
passes, one to get the mean and the next the variance.

\begin{corollary} For all R, $E(R^2)\geq E(R)^2$. \end{corollary}
\begin{proof} This follows of the previous theorem since Var(R) is always
nonnegative, being a square. \end{proof}


\subsection{Computing Variances}

\begin{theorem} If Var(R)=0, then R is a scalar.
\end{theorem}
\begin{proof} Suppose that \[Var(R)=Ex((R-E[R])^2)=0 .\]
Then $(R-E[R])^2$ must be always 0, thus R must always be equal to E[R].
\end{proof}

A Bernoulli Random variable with probability $p$ has variance
\[
p\cdot1^2+(1-p)\cdot 0^2-p^2 = p(1-p)
\]

What about the binomial distribution?  This is messy to do directly,
but easy if we figure out how to sum variances:

\begin{theorem}
If $X$ and $Y$ are {\em independent}, then 
\[
\var{X+Y}=\var{X}+\var{Y}
\]

Therefore, the variance of the binomial distribution on $n$ Bernoulli
trials with probability $p$ is $np(1-p)$.  It follows that the
standard deviation is $\sigma=\sqrt{np(1-p)}$.  As you determined in your
homework, this is about the amount of of the expected absolute
deviation from the mean in a binomial distribution. 

\section{Higher order statistics}

\begin{defin} $E[R^m] $ is the m-th moment of R. \end{defin}
Thus the first moment is the mean, the second one is the variance.
The more moments  we know, the more we know the distribution of R. In fact,
if you have all moments for some $R:S\rightarrow N$,
 then you can recover the underlying
distribution function for R. The method uses generating functions.
\begin{defin}
The moment generating function for R is
\[H_R(x)=\sum_n \frac{E[R^n]}{n!}x^n .\] \end{defin}
\begin{defin}
The probability  generating function for R is 
\[G_R(x)=\sum_nPr(R=n)x^n .\] \end{defin}

These generating functions are very closely related as the following theorem
shows: 
\begin{theorem}
If $R:S\rightarrow N$, then
\[H_R(t)=G_R(e^t).\] \end{theorem}
\begin{proof} 
\[H_R(t)=\sum_i \frac{E[R^i]}{i!}t^i=\sum_i \frac{t^i}{i!}\sum_n n^i Pr(R=n)
=\] 
\[=\sum_n Pr(R=n)\sum_i\frac{t^in^i}{i!}= \sum_nPr(R=n)e^{tn}=\]
\[=\sum_n Pr(R=n)(e^t)^n = G_R(e^t). \] 
\end{proof}


Going from G to H is similar to computing Laplace our Fourier transforms.
\begin{defin} The exponential transform of R is $Ex(e^{tr})$. \end{defin}
 
\end{document} 

\message{ !name(H59-Notes24.tex) !offset(-313) }
