\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems
%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000  PS 11.5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem
% [[[random walks]]]
%[[[Here's an idea; it needs polishing, solving, etc.]]]

The latest recount of the Florida votes has yielded exactly 3 million
votes for each.
The Florida Supreme Court has decided to allow repeated 
recounts of all the votes in Florida, until the difference between the
two is at least 1000 votes.

It turns out that recounting of votes has the odd property that it can
be modeled by a random walk.
Specifically, each recount has probability .4 of yielding exactly 100
more votes for Bush than the previous count, 
and exactly .6 of giving 100 more votes for Gore. (Unlike the current election, in this scenario, 
the total number of votes after each recount is constant.)

\bparts
\ppart
What is the probability of Bush eventually winning?
Of Gore eventually winning?  Of neither eventually winning (that is,
recounts go on forever)?

\solution{
\medskip
\textbf{Solution:}
Let $P_n$ be the probability that Bush wins the election where $n$ represents
the net number of recounts won by Bush (for example, if Bush wins the first
one and then loses the second and third, $n=-1$).  Bush wins if he gets 1000
more votes (n=10) and loses if Gore gets 1000 more votes (n=-10).  So, we can write
the following recurrence for $P_n$.

\[
P_n = \left\{
\begin{array}{cl}
0 & \text{if $n = -10$} \\
1 & \text{if $n = 10$} \\
.4*P_{n+1} + .6*P_{n-1} & \text{if $-10 < n < 10$}
\end{array}
\right.
\]

This leads to the recurrence 
\[ .4*P_{n+1}-P(n)+.6*P{n-1}=0, \] 
which has the
characteristic equation $r^2-2.5*r+1.5=0$, where $P_{10}=1$ and $P_{-10}=0$.
Using the quadratic formula, we find that the roots are r=1.5 and r=1.  
This gives us the solution:

\begin{eqnarray*}
P_n     & = &   A * \left( \frac{3}{2} \right)^n + B * (1)^n
\end{eqnarray*}

Using the boundary conditions, $P_{10}=1$ and $P_{-10}=0$, we can find the constants $A$ and $B$.  Substituting these two conditions into the general form gives:

\begin{eqnarray*}
0       & = &   A*1.5^{10} + B\\
1       & = &   A*1.5^{-10} + B
\end{eqnarray*}

Solving this system, we get $A=.0173$, $B=-3*10^{-4}$. Finally, solving for $P_0$, the probability that
Bush eventually wins the election:
\begin{eqnarray*}
P_0     & = &   .0173*(1.5)^0 + -3*10^{-4}*(1)^0\\
    & = &   .0170
\end{eqnarray*}
So, the probability Bush wins is .017.  By the analysis of theorem 3.1 in Lecture 26, the probability that no one ever wins is 0, and so the probability that Gore eventually wins is 1-.017 = .983
}


\ppart 
What is the expected duration of the election (assume one recount per day)?

\solution{
\medskip
\textbf{Solution:}

By the analysis from Section 3 of Lecture 26, we have the following formula for $E_n$, the expected number of recounts of the election, given Bush is currently ahead by $n$ recounts (note that $n$ can range from -10 to 10).  

\[
E_n = \left\{
\begin{array}{cl}
0 & \text{if $n = -10$} \\
0 & \text{if $n = 10$} \\
1 + .4*E_{n+1} + .6*E_{n-1} & \text{if $-10 < n < 10$}
\end{array}
\right.
\]

Solving the homogeneous part of this recurrence gives the equation

\begin{eqnarray*}
E_n     & = &   A * \left( \frac{1-.4}{.4} \right)^n + B\\
    & = &   A*1.5^n + B
\end{eqnarray*}

Solving the particular part of the recurrences gives us $E_n = \frac{n}{1-(2*.4)}$.  Adding the two parts together gives a complete solution of the form:

\begin{eqnarray*}
E_n     & = &   A*(1.5)^n + B + \frac{n}{.2}
\end{eqnarray*}

Using the boundary conditions $E_{-10} = E_{10} = 0$, we get the system of equations:

\begin{eqnarray*}
0 & = & A*(1.5)^{10} + B + \frac{10}{.2}\\
0 & = & A*(1.5)^{-10} + B - \frac{10}{.2}
\end{eqnarray*}

This gives $A=-1.73467$, $B=50.03008$.  Finally, solving the equation given that $n=0$ gives us the desired answer.  $E_0 = -1.73467*(1.5)^n + 50 + \frac{0}{.2} = 48.3$ days until a winner is declared.
\\
}

%%% BEGIN COMMENTING OUT LAST PART!  
%%% using \iffalse \fi construct to do so...

\iffalse

\ppart 
Gore has decided that if Bush wins according to this process, he
(Gore) will throw in the towel.
Bush, however, has decided that if Gore wins according to this
process, he (Bush) will insist on continuing the recounts forever until he
(Bush) has a 1000 vote margin.  
Now assume that Gore wins, according to this process.

i) How many recounts would be expected to occur until Bush wins?\\
ii) What is the probability that Bush eventually wins?

\fi

%% END COMMENTING OUT.

\eparts

%%%%%%%%%%%%%%
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



