\documentclass[11pt]{article}
\usepackage{amsmath}
\input{macros-course}


\renewcommand{\solution}[1]{
  \medskip
  \textbf{Solution.} \par 
  #1
}

\begin{document}

\begin{problems}

\problem Interest and Annuities

Suppose you are going to start working for Makaeye, a hot new 
Internet startup.
Forgoing a petty salary, you are promised \$4000 in stock a month. 
What's more, the stock
is soaring in value, and raises in value by 20\% each month (so next
month, the stock you earned this month will be worth \$2400).

\begin{problemparts}
\problempart
How much will your compensation package be worth after one year, 
approximately, assuming you do not sell any of your shares?

\solution{
The applicable summation is:
\begin{eqnarray*}
\sum_{m=0}^{11} 4000 \cdot 1.20^{m}  
  & = & 4000 \cdot \sum_{m=0}^{11} 1.20^m \\
  & = & 4000 \cdot \frac{1 - 1.20^{12}}{1 - 1.20} \\
  & = & \$158,322
\end{eqnarray*}
If they do not have calculators, and we still use a question like
this, I propose that we include a table and perhaps make the problem
work out smoothly.
}

%Forgoing a petty salary, you are promised 200 shares of stock a month, 
%and the shares are worth \$20 each this month. What's more, the stock
%is soaring in value, and raises in value by 10\% each month (so next
%month, each share will be worth \$22).

%\begin{problemparts}
%\problempart
%How much will your compensation package be worth after one year, assuming
%you do not sell any of your shares?
%
%\solution{
%The applicable summation is:
%\begin{eqnarray*}
%20 \cdot 200 \cdot 12 \cdot 1.20^{11}  \\
%  & = & \$356,644
%\end{eqnarray*}
%}

\problempart
Unfortunately, things do not go as you had hoped. Immediately after
you join the startup, the stock begins dropping in value. Your favorable
calculations are shattered. Each month, the
stock is worth only $3/4$ what it was the previous month. While some employees
panic and leave the company, you are considering sticking it out.

Assume that you are loyal and do not sell any of your stock. Approximately
what value can you expect to have built up when you retire?

\solution{
\begin{eqnarray*}
\sum_{m=0}^{N} 4000 \cdot \left( \frac{3}{4} \right)^{m}  
  & = & 4000 \cdot \sum_{m=0}^{N} \left( \frac{3}{4} \right)^{m} \\
  & = & 4000 \cdot \frac{1 - \left( \frac{3}{4} \right)^{N+1}}{1 - \frac{3}{4}} \\
  & = & 16000 \cdot \left( 1 - \left( \frac{3}{4} \right)^{N+1} \right) \\
  & \approx & \$16,000
\end{eqnarray*}
For any moderately large values of $m$, this is about right. The stock
tanks quickly. You should recognize that there is an asymptotic limit
to the total value here.
}
\end{problemparts}


\problem Summations

\begin{problemparts}
\problempart
Find a closed form for the followng summation
(for $x \neq 1$):
\[
\sum_{i=-n}^{n} 
  \left[ \frac{1}{\sqrt{x^i}} \sum_{k=0}^{i-1} x^k \right]
\]

\solution{
\begin{eqnarray*}
\sum_{i=-n}^{n} 
  \left[ \frac{1}{\sqrt{x^i}} \sum_{k=0}^{i-1} x^k \right]
 & = &  \sum_{i=-n}^{n} 
  \left[ \frac{1}{\sqrt{x^i}} \frac{1-x^i}{1-x} \right]  \\
 & = &  \frac{1}{1-x} \sum_{i=-n}^{n} 
   \left[ \frac{1}{\sqrt{x^i}} (1-x^i) \right]  \\  
 & = &  \frac{1}{1-x} \sum_{i=-n}^{n} 
  \left[ \frac{1}{\sqrt{x^i}} (1-x^i) \right]  \\
 & = &  \frac{1}{1-x} \sum_{i=-n}^{n} 
   \left[ x^{\frac{-i}{2}} - x^{\frac{i}{2}} \right]  \\
 & = &  0  
\end{eqnarray*}
}

\problempart
Verify your closed form using induction.

\solution{
This doesn't apply well here. We would need a different 
problem if this is important.
}
\end{problemparts}

\problem Abstraction

I don't mind making a problem on this up, but it would take a
long time, so I'd like to know if we are using it. Unless we ask
something simple about an algorithm they already have, like 
caching...

%\problem Conditional Expectation
%
%Ugh. Is this needed separately from conditional probability?
%

\problem Random Variables (somewhat)
\begin{problemparts}
\problempart
Suppose you and a friend each roll a fair die. What is the probability
that you beat him by at least 2?

\problempart
Suppose you get to roll twice, and keep the best one. What is the 
probability now?

\problempart
Suppose you again roll twice, but this time you must take the average of
the two rolls. What is the new probability that you beat your friend (who
still only rolls once)?

\end{problemparts}

%\problem Binomial Distribution, Polling, Faults
% I hate polling. Do we want a generic question on it, though?

\problem Probabilistic Recurrances
You come home from your 6.042 final exam to find a disaster:
your entire CD collection has been destroyed by a freak
lightning strike. Luckily, you have made mp3 backups of all your
legally-purchased music and distributed them to friends. You
connect to the network and begin downloading your rightful property
from various friends.

However, your fate is not so simple. Given the MIT network these
days, every transfer has only a $2/3$ chance of succeeding. Even 
worse, the RIAA is watching the network and will detect any 
successful transfer $1/4$ of the time, and even unsucessful 
transfers $1/8$ of the time. When this happens, they will have MIT
immediately shut off your network access and you will get no more 
songs (although you get the current song, if the transfer is successful).

How many of your hard-earned songs can you expect to recover?

\solution{
A simple recurrance.
\begin{eqnarray*}
M  & = &  \frac{2}{3}\left( \frac{3}{4}(1 + M) + \frac{1}{4} \right)
          + \frac{1}{3} \left( \frac{7}{8}M \right)  \\
   & = & \frac{2}{3} + \frac{2}{3}M + \frac{7}{24}M  \\
   & = & 16
\end{eqnarray*} 
}
  
%\problem Games

%\problem Expectation

\problem Games, Expectation

You are given a checker on one end of a special checkered board
that is 8 squares long but infinitely wide.
On any given move, the piece is equally likely to move Forward,
Left, or Right (but never backwards).

\begin{problemparts}
\problempart
What is the expected time for the checker to reach the other side of
the board?

\solution{
21.

This can be solved a number of ways. The recurrance:
\[
T(n) = 1 + \frac{2}{3}T(n) + \frac{1}{3}T(n-1) \; , \; \; 
	T(0) = 0
\]
is easily solvable. You could also use linearity of expectation, noting
that the $\frac{1}{3}$ chance to move forward gives an expected time
to advance of 3 moves for each row.
}

\problempart
How far do you expect the piece to be offset laterally when it reaches
the other end?

\solution{
Clearly, symmetry says that the xpected value is zero, as does a nit-picky
calculation again using linearityof expectation. A more interesting
question might involve the variance or such.
}

\problempart
What is the probability that the checker will have moved laterally
(Left or Right)
exactly $n$ squares when it reaches the other side?

\solution{
This takes a little insight. The checker has a $2/3$ chance of moving
laterally and a $1/3$ chance of moving forward at any given move. Thus,
each sequence ending with $n$ lateral moves has a probability of the form
\[
\left( \frac{2}{3} \right) \cdot \left( \frac{2}{3} \right)
\cdot \left( \frac{1}{3} \right) \cdot \left( \frac{2}{3} \right)
\cdot \left( \frac{1}{3} \right) \ldots
\cdot \left( \frac{1}{3} \right)
\]
where there must be $7$ $\frac{1}{3}$ terms and $n$ $\frac{2}{3}$ terms,
and the last term must be $\frac{2}{3}$. Thus, the total probability
of having $n$ lateral moves is:
\[
\binom{n+6}{6} \left( \frac{2}{3} \right)^n \left( \frac{1}{3} \right)^7
\]
}

\problempart
What is the expected number of times that the checker will have  run of
two Forward moves in a row?

\solution{
Linearity of expectation is your friend. $1/3$ chance of this starting 
from any row from 1 to 6, so $2$.
}

\end{problemparts}

%% Note: the problems mix together these concepts a little.

\end{problems}

\end{document}

