% Variants of this problem appeared in:
% SP 1998, PS 11, problem 11
% FA 1996, PS 12, problem 8
% FA 2001, Practice Problems 12, problem 2
\begin{problem}

Suppose you flip a fair coin 100 times.  The coin flips are all mutually independent.  
What is an upper bound on the probability
that the number of heads is at least 70\ldots
\begin{problemparts}

\problempart
\ldots according to Markov's Inequality?

\textbf{Solution}:
The expected number of heads of $50$.  So the probability that the
number of heads is at least $70$ is at most $50/70 = 0.71$.

\problempart
\ldots according to Chebyshev's Inequality?

\textbf{Solution}:
Let $X_i$ be the random variable whose value is $1$ if the $i$th coin
flip is heads.  Then $\Var[X_i] =  1/2 - (1/2)^2 = 1/4$.  So $\Var[X_1
+ \cdots + X_100] = 100/4 = 25$.
 The variance of the number of heads is $100/4 = 25$, so the standard
deviation is $5$.  So $70$ is four times the standard deviation from
the mean.  Since the distribution is symmetric, the
probability is at most $\frac{1}{2} \cdot \frac{1}{4^2} = \frac{1}{32}$


\problempart
\ldots according to Chernoff's Bound?

\textbf{Solution}:
We apply Chernoff`s bound with $c = 70/50 = 1.4$.  This gives us that
$\alpha = \ln(1.4) + 1/1.4 - 1 = 0.05076$ and that the probability is at most $e^{-0.05076 \cdot 1.4 \cdot 50} = 0.0286$.


%\problempart
%\ldots according to the upper bound for binomial distributions
%        derived in lecture?\\
%        (Get a strict upper bound by using the multiplicative factors
%of
%        $\frac{1-\alpha}{1-2\alpha}$ to account for the case that
%        there are strictly more than 70 heads,
%        and $(\frac{n}{e})^{\frac{1}{12n}}$ to adjust Stirling's
%        approximation.)
\end{problemparts}

\end{problem}
