        \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).
% Fall 01, tutorial 13
\begin{problem} 
Let $R$ be the sum of a finite number of Bernoulli variables.

\begin{problemparts}

\problempart For $y \geq \mu_R$, write formulas in terms of $y$, $\mu_R$ and
$\sigma_R$ for the Markov, one-sided Chebyshev, and Chernoff bounds on
$\pr{R \geq y}$.

\solution{
\begin{itemize}
\item the Markov bound is $\mu_R/y$, directly from~(lost reference).

\item the bound from the one-sided Chebyshev result is
\begin{align*}
\pr{R \geq y} & = \pr{R - \mu_R \geq y - \mu_R}\\
  & \leq \frac{\sigma_R^2}{(y - \mu_R)^2 + \sigma_R^2}.
\end{align*}

\item the bound from the Chernoff result is
\begin{align*}
\pr{R \geq y} & = \pr{R \geq \frac{y}{\mu_R}\mu_R}\\
              & \leq \text{exp}(- (\frac{y}{\mu_R}\ln \frac{y}{\mu_R} -
              \frac{y}{\mu_R} + 1) \mu_R)\\
              & = \text{exp}(- (y\ln \frac{y}{\mu_R} - y + \mu_R)).
\end{align*}

\end{itemize}
}

\problempart  Compare these bounds when $R$ is a single unbiased Bernoulli
variable and $y=1$.

\solution{In this case $\mu_R = 1/2$ and $\sigma_R^2 = 1/4$, so

\begin{itemize}

\item Markov gives $\mu_R/y = 1/2$ which is exactly right,

\item the bound from the one-sided Chebyshev result is
\[
\frac{\sigma_R^2}{(y - \mu_R)^2 + \sigma_R^2} = \frac{1/4}{(1-(1/2))^2
+ 1/4} = \frac{1}{2},
\]
and so is also exactly right,

\item the bound from the Chernoff result is
\[
\text{exp}(- (\ln (1/(1/2)) - 1 + 1/2)) = e^{1/2 - \ln 2} = \sqrt{e}/2 > 0.83,
\]
and so is a large over-estimate.

\end{itemize}}

Consider the case where $c$ is small, say $c=1+\epsilon$ and
$\epsilon <1$. The Markov bound is $\frac{1}{1+\epsilon}$.  If we further
assume that $\variance{R}=\expect{R}$, then the Chebyshev one-sided
bound becomes
\[
\pr{R-\expect{R} \geq \epsilon \expect{R}} \leq
\frac{\variance{R}}{\variance{R}+\epsilon^2 \expect{R}} =
\frac{1}{1+\epsilon^2}.
\]
Since $\frac{1}{1+\epsilon}< \frac{1}{1+\epsilon^2}$, the Markov bound is
tighter than the Chebyshev one-sided bound.

\problempart Discuss when the Chebyshev one-sided bound on $\pr{R >
c\expect{R}}$ is tighter than the Chernoff bound, where R is positive and
$c>1$. (Providing an example is sufficient.)

\solution{ Still consider the case where $c$ is small, that is,
$c=1+\epsilon$ and $\epsilon < 1$.  Assume that
$\variance{R}=\expect{R}=1$.  The Chernoff bound is $e^{-(c\ln{c}-c+1)}$.
Numerical experiments show that
\[
\frac{1}{1+\epsilon^2} < e^{-(c\ln{c}-c+1)}.
\]
Therefore, the Chebyshev one-sided bound on $\pr{R>c\expect{R}}$ is
tighter than the Chernoff bound.}

\end{problemparts}
\end{problem}



