        \problemdata       % Takes 5 *mandatory* arguments
        {variance-6}             % latex-friendly label for the prob.
        {variance}               % The topic of the problem content.
        {Velleman}               % Source (if known)
        {S98 PS11-7; F97 PS11-8} % Usage (list ones you are aware of).
        {Theory Pig, S02}        % Last revision info (author, date).

% FA 2001, tutorial 13
\begin{problem} 
\textbf{One-sided Chebyshev Bound.}  Prove the one-sided
Chebyshev bound.  \hint $R-\mu_R \geq x$ implies $(R-\mu_R + a)^2 \geq (x
+ a)^2$ for all nonnegative $a \in \reals$.  By Markov,
\[
\pr{(R-\mu_R + a)^2 \geq (x + a)^2} \leq \frac{\expect{(R-\mu_R + a)^2}}{(x+a)^2}.
\]
Choose $a$ to minimize this last bound.

\solution{
\begin{proof}

\begin{align}
\pr{R-\mu_R \geq x} & \leq \pr{(R-\mu_R + a)^2 \geq (x + a)^2}
                          & \text{(from the hint)} \notag\\
   & \leq \frac{\expect{(R-\mu_R + a)^2}}{(x+a)^2}
                          & \text{(Markov  bound)} \notag\\
   & =  \frac{\expect{(R-\mu_R)^2} +2a(\expect{R}-\mu_R) + a^2}{(x+a)^2}
                & \text{(linearity of expectation)} \notag\\
   & =  \frac{\expect{(R-\mu_R)^2} + a^2}{(x+a)^2} & (\expect{R} = \mu_R) \notag\\
   & =  \frac{\variance{R} + a^2}{(x+a)^2} & \text{(def of variance)\label{Va}}.
\end{align}

Setting the derivative of~(\ref{Va}) with respect to $a$ to zero, we find
that $a = \variance{R}/x$ minimizes~(\ref{Va}).  Plugging in this value for
$a$, we have
\begin{align*}
\pr{R-\mu_R \geq x} & \leq \frac{\variance{R} +
\left(\variance{R}/x\right)^2}{\left(x+ \variance{R}/x\right)^2}
    & \text{($a = \variance{R}/x$ in~(\ref{Va}))}\\
    & = \frac{\variance{R}x^2 + \varsq{R}}{\left(x^2+
         \variance{R}\right)^2}
       & \text{(multiply by $x^2/x^2$)}\\
    & = \frac{\variance{R}(x^2 + \variance{R})}{\left(x^2+
\variance{R}\right)^2}\\
    & = \frac{\variance{R}}{x^2+ \variance{R}}.
\end{align*}

\end{proof}
}

\end{problem}
