\documentclass[12pt]{6042}
\usepackage{psfig}

\begin{document}

\handout{positive-chebyshev}{A One-Sided Chebyshev Bound}{May 8, 1998}

We prove the following Lemma which was stated without proof in the notes
for Fall '97, Lecture 24, \S3.2

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

\begin{proof}
Let $V ::= X - \expect{X}$, so $\pr{X - \expect{X} \ge c} = \pr{V \ge
c}$.  Also $\expect{V} = 0$ and
\[\begin{array}{rclcl}\label{varV}
\variance{X} & = & \variance{V} & = & \expect{V^2}.
\end{array}\]

Let $p::= \pr{V \ge c}$.  We want an upper bound on $p$.  If $p = 0$, the
upper bound of the Lemma is immediate.  Also, if $p = 1$, then $\expect{V}
\ge c > 0$, contradicting the fact that $\expect{V}=0$.

So we may assume $0 < p < 1$.  Now the conditional expectations $\expect{V
\mid V \ge c}$ and $\expect{V \mid V < c}$ will be finite, and we can
apply a standard identity which holds for any $V$ and $c$:
\begin{eqnarray}\label{0EV}
\expect{V} & =  & \expect{V \mid V \ge c}p + \expect{V \mid V < c}(1 - p).
\end{eqnarray}

From the definition of conditional expectation, we have
\begin{eqnarray}\label{VVkk}
\expect{V \mid V \ge c} & \ge & c,
\end{eqnarray}
and from~(\ref{0EV}),~(\ref{VVkk}), and the fact that $\expect{V} = 0$, we
obtain
\[0 \ge cp + \expect{V \mid V < c}(1 - p),\]
so
\begin{eqnarray}\label{V<k}
- \expect{V \mid V < c} & \ge & \frac{cp}{1-p}.
\end{eqnarray}

Applying the standard identity again to $V^2$, we have
\begin{eqnarray}\label{EV2}
\expect{V^2} & = & \expect{V^2 \mid V \ge c}p + \expect{V^2 \mid V < c}(1-p),
\end{eqnarray}
but
\begin{eqnarray}\label{V2k2}
\expect{V^2 \mid V \ge c} & \ge  & c^2,
\end{eqnarray}
and since the expectation of the square is at least the square of the
expectation, we also have
\begin{eqnarray}\label{EV2E2V}
\expect{V^2 \mid V < c} & \ge & \expectsq{V \mid V < c}.
\end{eqnarray}

Combining~(\ref{EV2}), ~(\ref{V2k2}),~(\ref{EV2E2V}), and~(\ref{V<k}) gives
\begin{eqnarray*}
\expect{V^2} & \ge & c^2 p +\left(\frac{cp}{1-p}\right)^2(1-p), 
\end{eqnarray*}
and solving for $p$ yields
\[p \le \frac{\expect{V^2}}{\expect{V^2} + c^2} = \frac{\variance{V}}{\variance{V} + c^2}\]
as desired.

\end{proof}

\textbf{Exercise}: For each $\sigma > 0$, show that there is a random
variable, $V$, with expectation zero and variance $\sigma^2$, for which
the bound of the Lemma is tight.  \hint $X$ need only take two values.

\end{document}
