\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{amssymb}

\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

%% double space
\usepackage{setspace}
\setstretch{1.5}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}

\date{}

\title{Optimal exercise of russian options in the binomial model}
\author{Robert Chen\\ {\em Department of Mathematics}\\
{\em University of Miami}\\
~\\
Burton Rosenberg \\ {\em Department of Computer Science}\\
{\em University of Miami}}

\begin{document}
\maketitle

\abstract{
The Russian Option is a two-party contract 
which creates a liability for the option seller to pay the
option buyer an amount equal to the maximum
price attained by a security over a specific time
period, discounted for the option's age.
The Russian option was proposed by Shepp and Shiryaev (1993). 
Kramkov and Shiryaev (1994) first examined the option in the binomial model.
We improve upon their results and give a near-optimal algorithm 
for price determination.
\\~
{\bf Keywords:} Russian option, binomial model, dynamic programming.
}

\section{Introduction}

The Russian Option is a two-party contract 
which creates a liability for the option seller to pay the
option buyer an amount equal to the maximum
price attained by a security over a specific time
period, discounted for the option's age. For an $N+1$ step
time period $0, 1,  2, \ldots, N$, the option seller's liability
at time step $n$, $0\le n \le N$, is,
\[
     L(n) = \beta^n \max_{0\le t\le n}  s_t
\]
where $s_t$ is the security price at time $t$ and $\beta$
is the discount factor. In this paper we consider the value
of this option under a standard binomial model of
security prices, and give efficient algorithms for value calculation.

The Russian option was proposed by Shepp and Shiryaev (1993). 
At this time it is not traded. Their work gives the optimal expected
present value and the optimal exercise strategy under the Black-Scholes
market model. 
Kramkov and Shiryaev (1994) first examined the option in the binomial model
of Cox, Rubinstein and Ross (1979). They present an $O(N^2)$ algorithm for
calculating option price at the first time step.

This work gives an $O(N)$ algorithm determining the option price
at all time steps as well as optimal
execution and the execution boundary. 
We also present an $O(N^2)$ 
algorithm for general determination of option value 
given option structure and security price history up to time $n$, 
$0\le n \le N$.

%================================

\section{Definitions and basic facts}

The binomial model, introduced by Cox, Ross and Rubinstein (1979), assumes discrete
price announcements at equal time intervals with each price related
to the previous price by either an up-step
or down-step, according to a random process.
For $s_i$ the security price at time $i$, the price process is given by,
\[
       s_{i+1} = u^{\epsilon_i}s_i, \;\; \epsilon_i \in \{\, 1, -1 \,\},
\]
with $u>1$.
The probability of an up-step, $\epsilon_i=1$,  is $p$, independent of $i$.
The probability of a down-step is $q=1-p$.
The existence of a risk-free bond is also assumed,
\[
     b_{i+1} = (1+r) b_i,
\]
where $r>0$ is the bond's interest rate.

The rational markets theory stipulates that the price sequence $s_i$ is a martingale,
\[
     E(s_{i+1}\,|\,s_i) = (1+r)E(s_i).
\]
This determines the martingale measure for the random process,
\[
   p = \frac{u(1+r)-1}{u^2-1}.
\]
Note that this implies $u\ge (1+r)$, that is, that the risky security must return at least the risk-free
rate in order that the martingale measure exist.

The option value and liability depends only on the current time step $n$, the 
current security price $s_n$, and the maximum value $s^*_n$ attained by the
security in the time period $0$ up to $n$. The current and maximum price
can be expressed as integers $j$ and $k$ such that $s_n= u^js_0, s^*_n=u^ks_0$.
Without loss of generality we assume $s_0=1$.
Hence the process can be modeled as a graph $V$ whose nodes are 3-tuples
$(n,j,k)$, indicating time step $n$, current price $u^j$ and maximum price $u^k$,
and whose edges indicate up-steps and down-steps labeled with probabilities
$p$ and $q$, respectively.

\begin{figure}[h]
\[
\begin{array}{rcl}
     & & (n,j+1,\max(k,j+1)) \\
     & \stackrel{p}{\nearrow} & \\
(n,j,k) & & \\
     & \stackrel{q}{\searrow} & \\
    & & ( n,j-1,k)
\end{array}
\]
\caption{Example subgraph of $V$.}
\end{figure}

The liability at any node $(n,j,k)\in V$ is $L(n,j,k)=\beta^n u^k$. At each time step
but the last, the option's
owner can either exercise and receive the liability or hold. The 
expected value of the option at node $(n,j,k)$
is therefore given by the backwards recurrence,
\[
    E(n,j,k) = \max \bigl( \beta^n u^k, \alpha ( p E(n+1,j+1, \max(k, j+1)) + q E(n+1,j-1,k))\bigr )
\] 
where $\alpha =1/(1+r)$ is the discount to present value for one time step. 
At the last time step, the owner must exercise. This
gives the boundary condition $E(N,j,k)=\beta^N u^k$, for all $j$ and $k$.

This recurrence defines values only for those
nodes reachable in the graph $V$ starting from node $(0,0,0)$.
These are called {\em accessible nodes.} Inaccessible nodes are of
no importance and their values are ignored. 
%
\begin{lemma}[Node accessibility]
The nodes $(n,j,k)$ is accessible if and only if,
\[
   0\le k \le n\le N,\; -n\le j \le k,
   \mbox{ and }  j+n = 2(k+i)
\]
for some non-negative integer $i$.
\end{lemma}
%
{\em Proof:}
Let $e_u$ be the number of up-steps and $e_d$ be the number of down steps,
\[
      n = e_u + e_d,\; j = e_u - e_d,\mbox{ therefore } n + j = 2 e_u = 2(k+i).
\]
The integer $i$ is the number of up-steps which do not contribute to attaining
the maximum $k$. Given appropriate $n,j,k$ and $i$, access the node $(n,j,k)$ by
first taking $k$ up-steps, then $n-k-i$ down-steps, and finally $i$ up-steps.
Since $n+j \le 2n$, then $k+i\le n$. Therefore the construction is well defined.

We assume that $\beta<1$, else the incentive to hold the option is too strong.
The recurrence insures that for accessible nodes, $E(n,j,k)\ge \beta^n u^k$.
If it is not true that for accessible nodes this inequality is strict when $j=k$,
then the incentive to hold the option would be too weak. Assuming the contrary,
\begin{eqnarray*}
    \beta^n u^k &<& E(n,k,k) \\
                          &=& \alpha ( p E(n+1,k+1,k+1) + q E(n+1,k-1,k)) \\
                          &<&\alpha( p \beta^{n+1}u^{k+1} + q \beta^{n+1} u^ k).
\end{eqnarray*}
Using the martingale measure for $p$, this reduces to the following constraints on $\beta$,
\[
      \frac{(1+u)(1+r)}{u(2+r)} < \beta < 1
\]
We have thus proved the following lemma,
\begin{lemma}[Option viability]
Let
$(1+u)(1+r)/(u(2+r)) < \beta < 1, $ $p$ be the martingale measure, and $(n,k.k)$ be
an accessible node. Then $\beta^n u^k<E(n,k,k)$ for $n<N$.
\end{lemma}
%
For the remainder of this paper, we will assume that $\beta$ is as required
for option viability and $p$ is the martingale measure.
%
\begin{lemma}[Option monotonicity]
%This is only needed for the variant of induction theorem three including a lower bound.
Assuming nodes are accessible, 
$E(n,j,k)\le E(n,j',k)$ if $j\le j'$ and $E(n,j,k)\le E(n,j,k')$ if $k\le k'$.
\end{lemma}

{\bf Proof:} Use induction starting at $n=N$ and working towards smaller $n$.
Note that for $(n,j,k)$ and $(n,j',k)$ to both be accessible, $j'-j$ must be even.

%================================

\section{Analysis of the Russian option}

We first prove some technical theorems and they apply them to 
determine the exercise boundary. Finally, an efficient algorithm is
given to determine the boundary.

\subsection{Induction theorems concerning option value}

%
\begin{theorem}[First induction theorem]
Suppose $(n,j,k)$ is accessible and $l$ is an integer satisfying $0\le k+2l\le n$.
Then $(n,j+2l,k+2l)$ is accessible and $u^{2l} E(n,j,k) = E(n,j+2l,k+2l).$
\end{theorem}
%
{\bf Proof:}
%
We begin by proving that 
if $(n,j,k)$ is accessible and $l$ is an integer $0\le k+2l\le n$ then $(n,j+2l,k+2l)$
is accessible.

Reduce to the case $l=1$. Hence $k+2\le n$. Since $(n,j,k)$ is
accessible, $0\le k\le n\le N,\; -n\le j\le k$ and $n+j=2(k+i)$ for a non-negative integer $i$.
In fact, because $k+2\le n, i$ must be positive.
Therefore $0\le k+2\le n\le N, \; -n\le j+2\le k+2$ and $n+j+2=2(k+2+i')$ where $i'=i-1\ge0$. 

We now prove the equality.
Reduce to the case $l=1$ and proceed by induction on $n$.
For $n=N$, the result is immediate, since $E(N,j,k)=\beta^N u^k$.

Assume the theorem for $n+1$. We first consider the case $E(n,k,k)$.
The option viability lemma allows us to insert and remove the $\max()$
operation in the following calculation,
%
\begin{eqnarray*}
    u^2 E(n,k,k) &=& u^2 \max \bigl( \beta^n u^k, 
                                       \alpha ( p E(n+1,k+1, k+1) + q E(n+1,k-1,k))\bigr ) \\
       &=& u^2 \bigl( \alpha ( p E(n+1,k+1, k+1) + q E(n+1,k-1,k) \bigr ) \\
       &=& \alpha \bigl ( p E(n+1,k+3,k+3) + q E(n+1,k+1,k+2) \bigr ) \\
       &=& \max\bigl( \beta^nu^{k+2}, \alpha( p E(n+1,k+3,k+3) + q E(n+1,k+1,k+3)) \bigr ) \\
       &=& E(n,k+2,k+2).
\end{eqnarray*}
%
We consider the final case, $E(n,j,k)$ where $j<k$,
\begin{eqnarray*}
  u^2 E(n,j,k) &=&  u^2 \max \bigl( \beta^n u^k, 
             \alpha ( p E(n+1,j+1, \max(k, j+1)) + q E(n+1,j-1,k))\bigr ) \\
     &=&  u^2 \max \bigl( \beta^n u^k, 
             \alpha ( p E(n+1,j+1, k) + q E(n+1,j-1,k))\bigr ) \\
     &=&  \max \bigl( \beta^n u^{k+2}, 
             \alpha ( p E(n+1,j+3, k+2) + q E(n+1,j+1,k+2))\bigr ) \\
     &=&  \max \bigl( \beta^n u^{k+2}, 
             \alpha ( p E(n+1,j+3, \max(k+2,j+3)) + q E(n+1,j+1,k+2))\bigr ) \\
     &=& E(n,j+2,k+2).
\end{eqnarray*}
%
This completes the induction and the proof.

\begin{theorem}[Second induction theorem]
Suppose $(n,j,k)$ is accessible
and $l$ is an integer satisfying $(N-n)\ge l\ge 0$.
Then $(n+l,j+l,k+l)$ is accessible and $(\beta u)^l E(n,j,k)\ge E(n+l,j+l,k+l)$.
\end{theorem}
%
{\bf Proof:}  
We begin by proving that
if $(n,j,k)$ is accessible and $l$ is an integer $0\le l\le N-n$ then $(n+l,j+l,k+l)$
is accessible.

Reduce to the case $l=1$. Hence $n+1\le N$.
Since $(n,j,k)$ is accessible, $0\le k \le n \le N,\; -n\le j\le k$ and $n+j = 2(k+i)$
for a non-negative integer $i$. Therefore $0\le k+1\le n+1 \le N,\; -n \le j+1 \le k+1$
and $n+1+j+2 = 2(k+1+i)$.

We now prove the inequality.
We reduce to the case $l=1$ and proceed by induction on $n$.
The similarity with the proceeding proof allows us to omit some steps.

For $n=N-1$,
\begin{eqnarray*}
    \beta u E(N-1,j,k) &=& \beta u \max\bigl(\beta^{N-1}u^k,
          \alpha( p E(N,j+1,\max(k,j+1)) + qE(N,j-1,k) ) \bigr) \\
       &\ge& \beta u (\beta^{N-1}u^k) \\
      &=& E(N,j+1,k+1).
\end{eqnarray*}
%
Assume the theorem for $n+1$. We first consider the case $E(n,k,k)$,
%The option viability lemma allows us to insert and remove the $\max()$
%operation in the following calculation,
%
\begin{eqnarray*}
    \beta u E(n,k,k) &=& \beta u \max \bigl( \beta^n u^k, 
                                       \alpha ( p E(n+1,k+1, k+1) + q E(n+1,k-1,k))\bigr ) \\
%       &=& \beta u \bigl( \alpha ( p E(n+1,k+1, k+1) + q E(n+1,k-1,k) \bigr ) \\
       &\ge&  \alpha \bigl ( p E(n+2,k+2,k+2) + q E(n+2,k,k+1) \bigr ) \\
%       &=& \max\bigl( \beta^{n+1}u^{k+1}, \alpha( p E(n+2,k+2,k+2) + q E(n+2,k,k+1)) \bigr ) \\
       &=& E(n+1,k+1,k+1).
\end{eqnarray*}
%
We consider the final case, $E(n,j,k)$ where $j<k$,
%
\begin{eqnarray*}
  \beta u E(n,j,k) &=&  \beta u \max \bigl( \beta^n u^k, 
             \alpha ( p E(n+1,j+1, \max(k, j+1)) + q E(n+1,j-1,k))\bigr ) \\
 % &=&  \beta u \max \bigl( \beta^n u^k, \alpha ( p E(n+1,j+1, k) + q E(n+1,j-1,k))\bigr ) \\
  &\ge&  \max \bigl( \beta^{n+1} u^{k+1}, 
             \alpha ( p E(n+2,j+2, k+1) + q E(n+2,j,k+1))\bigr ) \\
 % &=&  \max \bigl( \beta^{n+1} u^{k+1}, \alpha ( p E(n+2,j+2, \max(k+1,j+2)) + q E(n+2,j,k+1))\bigr ) \\
     &=& E(n+1,j+1,k+1).
\end{eqnarray*}
%
This completes the induction and the proof.
%
\begin{theorem}[Third induction theorem]
Suppose $(n,j,k)$ is an accessible node with $k>0$. Then $(n,j-2,k-1)$ is accessible and
%$E(n,j,k)/u \le 
$u E(n,j-2,k-1) \le E(n,j,k)$.
\end{theorem}
%
{\bf Proof:} 
We begin by proving that
if $(n,j,k)$ is accessible and $k>0$ then $(n,j-2,k-1)$ is accessible.

Since $(n,j,k)$ is accessible, $0\le k\le n \le N,\; -n\le j\le k$ and $n+j=2(k+i)$ for a
non-negative integer $i$. Since $k>0$ then $n+j-2\ge 0$. Therefore
$0\le k-1 \le n\le N,\; -n \le j-2 \le k-1$ and $n+j-2=2(k-1+i)$.

We now prove the inequality.
%The first inequality follows from  option monotonicity and
%the first induction theorem,
%\[
%   E(n,j,k) = u^2 E(n,j-2,k-2)\le u^2 E(n,j-2,k-1). 
%\]
The proof is by induction on $n$. 
For $n=N$ the result is immediate.

Assume the theorem for $n+1$.
We first consider the case $E(n,j,k)$ where $j<k$,
\begin{eqnarray*}
  u E(n,j-2,k-1) &=& u \max\bigl( \beta^n u^{k-1}, \alpha(pE(n+1,j-1,k-1)+qE(n+1,j-3,k-1)) \bigr) \\
     &\le& \max\bigl( \beta^n u^k,\alpha(pE(n+1,j+1,k)+qE(n+1,j-1,k))\bigr) \\
     &=& E(n,j,k).
\end{eqnarray*}
%
For $j=k$,
\begin{eqnarray*}
    u E(n,k-2,k-1) &=&  u \max\bigl( \beta^n u^{k-1}, \alpha(pE(n+1,k-1,k-1)+qE(n+1,k-3,k-1)) \bigr) \\
     &\le& \max\bigl( \beta^n u^k,\alpha(puE(n+1,k-1,k-1)+qE(n+1,k-1,k))\bigr), \\
\end{eqnarray*}
using the first induction theorem,
\[
uE(n+1,k-1,k-1) < u^2 E(n+1,k-1,k-1) = E(n+1,k+1,k+1),
\]
so,
\begin{eqnarray*}
    u E(n,k-2,k-1) 
     &\le& \max\bigl( \beta^n u^k,\alpha(pE(n+1,k+1,k+1)+qE(n+1,k-1,k))\bigr) \\
     &=& E(n,k,k).
\end{eqnarray*}
%
This completes the induction and the proof.
%

%================================

\subsection{Determining the exercise boundary}

In this section we show that the value of a russian option obtains its
liability value once the difference between the peak security price
and current security price, $k-j$, differ by at least an integer $h_n$, 
this integer depending on $n$. 
This integer is called the {\em exercise boundary}.
The examination of the exercise boundary leads to an optimal strategy
for exercise of russian options.

\begin{lemma}
Suppose $(n,j,k)$ and $(n,j',k')$ are accessible and $k-j\le k'-j'$.
Then $E(n,j,k)=\beta^n u^k$ implies $E(n,j',k') = \beta^n u^{k'}$.
\end{lemma}
%
{\bf Proof:}
Various cases are argued. First, assume $k-j=k'-j'.$ Since $j$ and $j'$ must
agree with $n$ mod 2, $2|(j'-j)$. 
The result follows by using the first induction theorem with $l=(j-j')/2$.

Now assume $k-j<k'-j'$. If $2|(k'-k)$ use the first induction theorem with $l=(k'-k)/2$,
\[
      u^{2l}E(n,j,k) = E(n,j+2l,k+2l) = E(n,j+2l,k').
\]
Note $k-j=k'-(j+2l)<k'-j'$ so $j'<j+2l$. Using option monotonicity, 
\[
     E(n,j',k') \le E(n,j+2l,k') = \beta^n u^{k+2l} = \beta^n u^{k'}.
\]
The definition of $E(n,j',k')$ implies a lower bound $\beta^n u^{k'}\le E(n,j',k')$.
Hence equality holds.

Now assume $k-j<k'-j'$ and $2|(k'-k+1)$. If $k>0$ apply the third induction theorem,
then the first induction theorem with $l=(k'-k+1)/2$,
\[
             u^{2l} E(n,j,k) \ge  u^{2l} u E(n,j-2,k-1) = u E(n,j-2+2l,k-1+2l) = u E(n,j-2+2l,k'). 
\]
Note $k-j=(k'-2l+1)-j < k'-j'$ so $j'\le j-2+2l$. Using option monotonicity, 
\[
    E(n,j',k') \le E(n,j-2+2l,k') \le u^{2l-1} E(n,j,k) = \beta^n u^{k+2l-1} = \beta^n u^{k'}.
\]
Matching the lower bound on $E(n,j',k')$. Hence equality holds.

If $k=0$ we must assume $n\ge 2$. For the remaining cases, $n=0,1$ the theorem is
trivial. We apply the first induction theorem with $l=1$ and the third induction theorem,
\[
    u^2 E(n,j,0) = E(n,j+2,2) \ge u E(n,j,1).
\]
We apply the first induction theorem with $l=(k'-1)/2$ and, since 
$k-j=-j<k'-j'=2l+1-j'$ implies
$j'-2l \le j$, we can apply option monotonicity,
\[
     E(n,j',k') = E(n,j',2l+1) = u^{2l} E(n,j'-2l,1) \le u^{2l} E(n,j,1) \le u^{2l+1}E(n,j,0) = \beta^n u^{k'},
\]
Matching the lower bound on $E(n,j',k')$. Hence equality holds.

This concludes consideration of all cases.
%
\begin{definition}
The {\em exercise boundary at $n$} is the least integer $h_n$ such that $E(n,k-h_n,k)$ obtains its liability value $\beta^n u^k$, if such an integer exists. The {\em execution boundary} is the
maximal sequence of execution boundaries at $n$ starting from some $n_o$ and 
continuing in consecutive $n$ up to $N$.
\end{definition}
%
The consequence of the previous lemma is that if the execution boundary at $n$
exists, then $E(n,j,k)=\beta^nu^k$ whenever $k-j\ge h_n$.
%
\begin{lemma}
If $h_n$ exists then $h_{n'}$ exists for all $n\le n'\le N$ and $h_{n'}\le h_n$. 
\end{lemma}
%
{\em Proof:} Directly from the second induction theorem.
%
\begin{lemma}
If $h_n$ exists and $n<N$, then $h_{n+1}$ exists and $0\le h_n - h_{n+1} \le 1$.
%Furthermore $h_{N-1}$ exists and $h_{N-1}-h_N=1$.
\end{lemma}
%
{\em Proof:} 
For $h_n=1$ or $0$ there is nothing to show. We assume $h_n\ge 2$.

Since $k-j\ge 2$ and $(n,j,k)$ is accessible, so are $(n,j,k-1)$ and
$(n+1,j+1,k-1)$. It is sufficient to show that if $E(n,j,k)=\beta^nu^k$ 
and $E(n,j,k-1)>\beta^nu^{k-1}$
then $E(n+1,j+1,k-1)> \beta^{n+1}u^{j-1}$.

Arguing by contradiction, assume $E(n+1,j+1,k-1)=\beta^{n+1}u^{k-1}$.
By option monotonicity, $E (n+1,j-1,k-1)=E(n+1,j+1,k-1)$ and,
\begin{eqnarray*}
  E(n,j,k-1) &=& \max\bigl( \beta^n u^{k-1}, \alpha( p E(n+1,j+1,k-1) + q E(n+1,j-1,k-1))\bigr ) \\
                   &=& \alpha( p E(n+1,j+1,k-1) + q E(n+1,j-1,k-1)) \\
                    &=& \alpha \beta^{n+1}u^{k-1} \\
                  &<& \beta^nu^{k-1},
\end{eqnarray*}
where the last inequality is justified by $\beta < 1 \le 1+r = \alpha^{-1}$.
The contradiction completes the proof.

%
\begin{theorem}[Execution boundary]
Let,
\[
   n_o = \min\{\, n \,|\, E(n,j,k)= \beta^n u^k \mbox{ for some accessible $(n,j,k)$}\,\}.
\]
The set is non-empty hence the execution boundary exists and is,
\[
     h_{n_o}\ge h_{n_o+1}\ge \ldots \ge h_{N-1}=1 > h_N = 0
\]
where $0\le h_n-h_{n+1}\le 1$.
\end{theorem}
%
{\em Proof:} Since $E(N,j,k)=\beta^Nu^k$ the set is non-empty. It is easy
to show from the definition of $E(N-1,k-1,k)$
and the inequality $\alpha\beta<1$
 that $E(N-1,k-1,k)=\beta^{N-1} u^{k}$. Hence $h_{N-1}$ is at least, and at most, $1$.
%

%================================

\subsection{Efficient algorithms for optimal exercise}

%Note that $\pi(i)\equiv \pi(i,0)$ is an indicator function for the parity of $i$.

\begin{lemma}[Canonical node]
Let $\pi(i,j)$ equal 0 or 1 depending on whether $i$ and $j$ agree modulo 2 or not,
respectively.
For every accessible node $(n,j,k)$ there is an accessible
node $\kappa(n,j,k)$, said to be canonical, defined by,
\[
\kappa(n,j,k) = (n,\pi(n,\delta)-\delta, \pi(n,\delta)) \mbox{ where }
\delta = k-j.
\]
Furthermore, $E(n,j,k)/ E(\kappa(n,j,k)) = u^{k-\pi(n,\delta)} $, where $k-\pi(n,\delta)$ is
an even, non-negative integer.
Conversely,  for each value of $\delta$, $0\le \delta\le n$, there is a canonical node.
\end{lemma}
%
{\em Proof:} 
Either $\delta$ or $\delta-1$ agrees with $n$ modulo 2, so at most one of
$(n,-\delta,0)$ and $(n,1-\delta,1)$  can be accessible.
Rearranging one of the accessibility conditions,
$\delta=n-k-2i$ for some non-negative integer $i$. Setting $i=\lfloor \delta/2 \rfloor$ and $k=\pi(n,\delta)$ gives any $\delta$ provided $0 \le \delta \le n$.

Starting from an arbitrary accessible node $(n,j,k)$, use the first induction theorem to
shift $j$ and $k$ down by an even integer $l$ such that $k-l$ is either 0 or 1. Since
$\delta=k-j$ is invariant, $k-l=\pi(n,\delta)$, so $l=k-\pi(n,\delta)$.
This proves the lemma.

The practical consequence of this lemma is that
for the purpose of tabulating values of $E$ we can arrange nodes in a 
triangular table table indexed by $n$, $0\le n\le N$,
and $\delta$, $0\le \delta\le n$. As an improvement, the table
can be truncated by returning a calculated value for $E$ whenever $\delta$ is greater
than or equal to the exercise boundary.
%
\begin{figure}[t]
\begin{verbatim}
    getValue(n, j, k)
        delta := k - j ;
        if n >= n_o and delta >= h[n] then return beta^n * u^k ;
        l = k - pi(n,delta) ;
        return u^l * E[n,delta] ;

    initValues(N)
        h[N] = 0 ;
        n_o = N ;
        for n = N-1 downto 0
          for delta = 0 to n
              k = pi(n,delta) ;
              j = k - delta ;
              e = alpha * ( p * getValue(n+1,j+1,max(j+1,k)) 
                          + q * getValue(n+1,j-1,k) ) ;
              if e < ( beta^n * u^k ) then
                  h[n] = delta ;
                  n_o = n ;
                  break ; // next n 
              E[n,delta] = e ;
          // end for delta
        // end for n
\end{verbatim}
\caption{Dynamic programming algorithm for $E(n,j,k)$.}
\end{figure}
%
\begin{theorem}
The algorithm given (see Figure 2) is an
$O(N^2)$ dynamic programming algorithm determining
$E(n,j,k)$ for all accessible $(n,j,k)$. Since there are $\Omega(N^2)$ nodes to
determine, the algorithm is optimal. The algorithm gives the optimal exercise
strategy. It is possible to give only the optimal exercise strategy using this
algorithm in $O(N)$ time.
\end{theorem}
%
{\em Proof:}
The algorithm's correctness and efficiency are easy to show.

When the option reaches its liability value, that is, it touches the exercise
boundary, exercise the option. Since by the maximum, the option is worth
more exercised than held.

Only the option boundary is needed to decide the optimal exercise strategy.
In an appendix we show that $h_{n_o}$ is independent of $N$, and only a
function of the market structure: $\alpha, \beta$ and $u$. Hence a variation 
of the algorithm which terminates once $n_o$ has been found runs in 
time $O(N)$.

%================================

\section{Conclusions}

We have given a near optimal algorithm for the pricing of Russian options under
the binomial model. We have also given some insight into the price process 
which these options follow. For such options to be traded, a risk-neutral hedging strategy
must be found, and this is an interesting area for future research.

%========================
% full paper: comment out following line
% abstract: do not comment out the following line
% \end{document}
%========================

\section{Appendix: $n_o$ is a function of $\beta, \alpha$ and $u$.}

Kramkov and Shiryaev (1994) studied the Russian option in the binomial model using
a different  approach, which we follow for this result.

Let $S_n=S_0u^{\epsilon_1+\ldots+\epsilon_n}$ be the option price, where
$\epsilon_i\in\{\,+1,-1\,\}$ is a random variable. Let $Y_\tau=\max_{0\le t\le \tau}\{\,S_t\,\}$
be the option pay-out. Define $X_n=Y_n/S_n$. Note that the range of $X_n$ is 
in the set $H=\{\,1,u,u^2,\ldots,u^n\,\}$. 
For all $x\in H$ let,
\[
   V_n(x) = \max\{\, E^*_x(\beta^\tau X_\tau)\,|\,0\le \tau\le n\,\}
\]
for $n=0,\ldots,N$ and $E^*_x(\beta^\tau X_\tau)$ is the conditional expectation
of $\beta^\tau X_\tau$ with respect the the probability measure $P^*$ given
$X_0=x$. Note $X_{n+1} = \max\{\, 1, X_n/u^{\epsilon_{n+1}}\,\}$ for $n=0,\ldots, N-1$.
Then the optimal stopping time $\tau_N$ for the buyer of the option at time $0$ is,
\[
\tau_N = \min\{\, n\,|\,     
             0\le n\le N,\; V_{N-n}(X_n)=X_n
\,\}.
\]
Kramkov and Shiryaev (1994) gave the following algorithm to compute $V_n(x)$. For all
$n=0,1,\ldots$ and $x\in H$, for all functions $f$ defined on $H$,
\[
Q_\beta f(x) = \max \{\,
      f(x) , \beta\bigl(p^* f(\max\{1,x/u\})+(1-p^*)f(xu)\bigr)
\,\}.
\]
Then $V_n(x) = Q^n_\beta g(x)$ where $g(x)=x$ and $Q^n_\beta g(x)$ is the $n$-th
degree operator $Q_\beta$ applied to the function $g(x)$.

For all $x\in H$, let $V(x)=\lim_{n\rightarrow\infty}V_n(x)$. It is easy to see that,
\[
   V(x) = \sup\{\,
    E^*_x(\beta^\tau X_\tau) \,|\,  0\le \tau < \infty
\,\}
\]
Kramkov and Shiryaev (1994) show that there exists an $x_0 = u^{k_0}$ such that $V(x)=x$
for all $x\in H$ such that $x\ge x_0$. This implies that $E(n,-k_0,0)=\beta^n$ for all
$n\ge k_0$. The value $k_0$ depends only on $\beta, \alpha$ and $u$, hence the
length of the chain 
\[
1=h_{N-1}\le h_{N-2}\le \ldots \le h_{n_o}\le k_0
\]
is likewise bounded.
 
%================================

\section*{References}

\begin{enumerate}
\item[] Cox, J.C., Ross, R.A., and Rubinstein, M. (1979), {\em Option Pricing: A Simplified Approach}\/, J.
Financial Economics, {\bf 7}, pp. 229--263.
\item[] Duffie, J.D. and Harrison, J.M. (1993), {\em Arbitrage Pricing of Russian Options and Perpetual
Lookback Options}\/, Ann. Appl. Probab., {\bf 3}, pp. 641--651.
%\item Hull, John C. Options, Futures, and Other Derivatives, 3rd Edition, (1997),
%Prentice-Hall, NJ
\item[] Kramkov, D.O. and Shiryaev, A.N. (1994), {\em On the Rational Pricing of the "Russian Option" for
the Symmetrical Binomial Model of a (B,S)-Market}\/, Theory Probab. Appl., {\bf 39}, pp. 153--162.
\item[] Shepp, L.A. and Shiryaev, A.N. (1993), {\em The Russian Option: Reduced Regret}\/, Ann. Appl. Probab., {\bf 3}, pp. 631--640.
\end{enumerate}


\end{document}