\problemdata       % Takes 5 *mandatory* arguments
  {chebyshev-from-markov}  % latex-friendly label for the prob.
  {variance,Chebyshev,Markov}  % The topic(s) of the problem content.
  {}                       % Source (if known)
  {S02 cp12M-3}            % Usage (list ones you are aware of).
  {Nick Matsakis, S02}     % Last revision info (author, date).
\begin{problem}
In this problem we will derive Chebyshev's Theorem from a corollary of
Markov's Theorem.

\begin{problemparts}
\problempart Explain why the following corollary of Markov's theorem holds:
\begin{corollary}
For any random variable~$R$, any positive integer~$k$, and any $x > 0$,
\[
\pr{\abs{R} \geq x} \leq \frac{\expect{\abs{R}^k}}{x^k}.
\]
\end{corollary}

\solution{This can be seen by letting the random variable in Markov's theorem be $\abs{R}^k$, which is nonnegative for any random variable $R$ and positive integer $k$. Notice as well that since $\abs{R} \geq x$ iff $\abs{R}^k \geq x^k$, the probabilities of the two events are the same.  Combining these facts we get, 
\[
\pr{\abs{R} \geq x} = \pr{\abs{R}^k \geq x^k} \leq \frac{\expect{\abs{R}^k}}{x^k}.
\]

\textbf{Note:} Even though Markov's theorem applies only to nonnegative random variables, this corollary applies to \emph{all} random variables.  This implies that Chebyshev's theorem, derived in the next part, also applies to all random variables.
}


\problempart Use the above corollary to prove the following:

\begin{theorem}[Chebyshev]
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
\end{theorem}

(Hint: Consider the case where $k=2$).

\solution{
The special case of this corollary when $k=2$ can be applied to bound the
random variable, $\abs{R - \expect{R}}$, that measures $R$'s
deviation from its mean.  Namely
\begin{equation}\label{chebE2}
\pr{\abs{R - \expect{R}} \geq x}
  = \pr{(R - \expect{R})^2 \geq x^2} \leq \frac{\expect{(R - \expect{R})^2}}{x^2},
\end{equation}
where the inequality follows from the corollary applied
to the random variable, $\abs{R - \expect{R}}$.  So we can bound the
probability that the random variable~$R$ deviates from its mean by
more than~$x$ by an expression decreasing as $1/x^2$ multiplied by the
constant $\expect{(R - \expect{R})^2}$.  This constant is the
\emph{variance of~$R$}. Hence,

\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
}

\end{problemparts}
\end{problem}
