\problemdata                                                             
        {Voting in Florida} % latex-friendly label for the prob.
        {Bounds - Markov, Chebyshev, Chernoff} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 13, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
The U.S. Supreme Court has mandated a re-vote in Florida.
All 6,000,000 people who voted earlier will get to vote again.
They are going to vote randomly, using a strategy that guarantees that
the expected value of the number of votes for Bush is exactly
3,000,000.
We don't know what the strategy is, though.  
(For example, \\
1. Each voter might toss a fair coin independently.\\
2. The Florida Supreme Court may toss one fair coin, and give all the
votes to one candidate or the other based on the result.\\
3. 1/4 of the voters decide to vote for Bush, 1/4 for Gore, and the other
half toss independent fair coins.\\
Etc.)

\begin{problemparts}

\problempart What do Markov bounds tell us about the probability that Bush gets
at least 6,000 more votes than Gore?

\solution{
Let R be the random variable which is equal to the number of votes that Bush gets.  Note that for Bush to get at least 6,000 more votes than Gore, Bush only needs to increase his vote total to 3,000 above the expected value.  Then, by Markov, $\Pr{(R \geq 3,003,000)} \leq \frac{Ex[R]}{3,000} = \frac{3,000,000}{3,003,000} = .9990$
}

\problempart Now assume also that the standard deviation of the experiment is 2000.
What do Chebyshev bounds tell us about the probability that Bush gets
at least 6,000 more votes than Gore?

\solution{
According to Mr. Chebyshev, $\Pr{(|R-Ex[R]| \geq x)} \leq \frac{Var(R)}{x^2}$.  Let R be the same random variable as in part a.  Plugging in $x=3,000$, $Ex[R]=3,000,000$, \\
and $Var[R]$ = (standard dev)$^2=4,000,000$ we get:
\begin{eqnarray*}
Pr{(R-3,000,000 \geq 3,000)} & \leq &   \frac{4,000,000}{3,000^2}\\
        & = &   \frac{4}{9} =  .444444
\end{eqnarray*}
}

\problempart Now assume that we know the experiment.  Specifically, one quarter of the
voters decide ahead of time on Gore, one quarter decide on Bush, and the other half
flip fair coins, independently.
(This doesn't have a standard deviation of 2000.)
What do Chernoff bounds tell us about the probability that Bush gets
at least 6,000 more votes than Gore?

\solution{
This time we'll need to compute the variance on our own before we can apply Mr. Chernoff.  Let $R$ be defined as above.   Then, let's let $R_1$ be the random variable corresponding to the number of people who vote for Bush non-randomly, and let $R_2$ correspond to the number of votes for Bush obtained by the coin-flipping half.  These two random variables are independent, so $Var(R)=Var(R_1+R_2)=Var(R_1) + Var(R_2)$. Additionally, $Var(R_1)=0$, since $R_1=Ex(R_1)$ for all possible outcomes of this experiment.  
\\
Since $R_2$ represents a binomial distribution, we know from last tutorial and from Rosen that it has a variance $npq = \frac{n}{4}$.  In this case, $n$ is the number of coin-flippers = $3,000,000$.  Putting this all together, we have:

\begin{eqnarray*}
Pr{(R-Ex[R] \geq x)} & \leq & \frac{Var(R)}{x^2}\\
Pr{(R-Ex[R] \geq 3,000)} & \leq & \frac{Var(R_1)}{3,000^2} + \frac{Var(R_2)}{3,000^2}\\
        & = &   0 + \frac{3,000,000}{4}*\frac{1}{9,000,000}\\
        & = & .083333   
\end{eqnarray*}
}

\end{problemparts}
\end{problem}
                                 