\documentclass[12pt]{article}
\usepackage{graphics,epsfig}

\usepackage{geometry} 

\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\newcommand{\myspan}{\mbox{span}}

\begin{document}

\title{CS 141: Advanced Topics in Algorithms \\ Spring 2006 \\ Homework Pyry and Topper}
\author{}
\date{Due:  Tuesday, April 18}
\maketitle

\begin{enumerate}

  \item \Points{$\mathcal{R}_{OBL}(ALG)$} \Name{Stock Market Crash Part II!}

The stock market problem is as follows: The stock market
will crash sometime within a span of 100 days, with the limitation
that it cannot crash on the first day, $t=1$.  There is only
one stock, and its price rises linearly, so that $P(t) = t$, and the
company ownes exactly one share.  Each day the algorithm is told whether
the market has crashed: if the market has crashed, and the algorithm has
not sold, it makes zero profit, and the game ends.
If the market has not crashed, the algorithm
has the option of selling the one share for a profit of $P(t) = t$,
at which point the game ends. 

\bigskip

We can use Yao's principle to determine a lower bound on the competitive
ratio of any algorithm:
\[
\mathcal{R}_{OBL}(ALG) \geq \max \left\{
\min_i \frac{\mathbf{E}_{y(j)}[OPT(\sigma_j)]}{\mathbf{E}_{y(j)}
[ALG_i(\sigma_j)]},
\min_i \frac{1}{\mathbf{E}_{y(j)} 
\left[ \frac{ALG_i(\sigma_j)}{OPT(\sigma_j)} \right]}
\right\}
\]
In class we found half of the solution by showing that
\[
\min_i \frac{1}{\mathbf{E}_{y(j)} 
\left[ \frac{ALG_i(\sigma_j)}{OPT(\sigma_j)} \right] } \geq 2.6
\]
with $y(j)$ being a unform distribution (that is, that the market is equally
likely to crash on any day except the first).

\bigskip

Complete the proof by evaluating
\[
\min_i \frac{\mathbf{E}_{y(j)}
[OPT(\sigma_j)]}{\mathbf{E}_{y(j)}[ALG_i(\sigma_j)]}
\]
once again assuming that $y(j)$ is the uniform distribution over
all possible crash days.

\end{enumerate}

\end{document}

