
\documentstyle[12pt]{article}
\date{ }
\setlength{\textwidth}{6in}
\setlength{\textheight}{8in}
\setlength{\topmargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\newcommand{\vs}{\vspace{.15in}}
\newcommand{\hs}{\hspace{.35in}}
\newcommand{\ds}{\displaystyle}
\newcommand{\fn}{\footnote}
\newcommand{\noin}{\noindent}
\newcommand{\n}{\indent}
\newcommand{\scn}{\setcounter{equation}{0} \section}
\renewcommand{\theequation}{\thesection .\arabic{equation}}
\begin{document}

\title{Binomial Models of Russian Option}

\author{Robert W. Chen (Department of Mathematics) \\
Burton J. Rosenberg (Department of Computer Science) \\
Alan Zame (Department of Mathematics) \\
University of Miami \\
Coral Gables, Florida 33124 \\}

\date{}

\maketitle


\newpage

\begin{center}{\bf Abstract}\end{center} \vs

The well-known Russian lookback option offers the buyer reduced regret in paying 
the maximum price of the asset (discounted in time) at any execution time selected 
by the buyer. In the continuous case an exact formula is known for the fair price 
of the option when there is no limit on the expiration time (pertpetual case). In 
the more realistic case when the expiration time is fixed at $N,$ an exact formula 
is impossible but we give an elegant algorithm to compute the fair price and the 
optimal execution boundary in order $N$ computations. This is possible only because 
we prove that the optimal execution boundary must have a specific form which is 
exploited in our algorithm. We also give a fast algorithm to compute the fair prices 
of the option at all possible nodes in order $N^2$ computations. \vs

\newpage

As in [1], we consider a $N$-period binomial model of a security market, consisting 
of two assets: a "risk-free" savings account $\{B_n|0 \leq n \leq N \}$ and a "risky" 
security $\{S_n|0 \leq n \leq N\}$ whose price processes are given by the following 
recurrence relations:
$$B_n = (1+r)B_{n-1}, 1 \leq n \leq N, B_0 = 1,$$
$$S_n = (1+\rho)S_{n-1}, 1 \leq n \leq N, S_0 > 0,$$
where $r > 0$ is the risk free interest rate and $1+\rho =  u$ or $\frac {1}{u}$ for 
some constant $u > 1 + r.$ \vs

By [6], a "Russian option" (or a discounted look back option of American type) can be 
viewed as a contract between two parties, a buyer and a seller. Specified as data is 
the risky security price process $\{S_n|n = 0, 1, 2,..., N\}$. If they make an agreement
at time $n$ with price history $\{S_i|i = 0, 1, 2, ..., n\},$ the buyer pays the seller 
an amount $Z_n$ equal to the option fair price at time $n$ with the price history $\{S_i|
i = 0, 1, 2, ..., n\}.$ The buyer then has the right to exercise his option at any time 
$\tau,$ where $n \leq \tau \leq N.$ If the option is exercised at time $\tau,$ then the 
seller pays $\beta^{\tau}Y_{\tau}$ to the buyer, where $Y_\tau = max\{S_0, S_1, S_2, ...
, S_\tau\}$ is the maximum price of the risky security up to time $\tau $ and $\beta $ 
($0 < \beta \leq 1$) is the discounting factor agreed between the buyer and seller. \vs

Without loss of generality, we can and do assume $S_0 = 1.$ Since $S_n = uS_{n-1}$ or 
$S_{n-1}/u$ for all $n = 1, 2, ..., N,$ $S_n = u^j$ and $Y_n = u^k,$ where $0 \leq k 
\leq n,$ $j \leq k,$ and $j = 2k-n+2i$ for some non-negative integer $i.$ For each price 
history $\{S_0, S_1, S_2, ..., S_n\},$ there is a node (a triple) $(n,j,k)$ associated 
with this price history, where $S_n = u^j$ and $Y_n = u^k$. The option price at time 
$n$ with price history $\{S_0, S_1, S_2, ..., S_n\}$ is a function of $n, j, k.$ Let 
$E(n,j,k)$ denote the option price at node $(n,j,k)$. For the ease of presentation, we 
will call a node $(n,j,k)$ accessible if $0 \leq k \leq n,$ $j \leq k,$ and $j = 2k - n + 
2i$ for some non-negative integer $i.$ It is easy to see that there are O($n^2$) accessible 
nodes for each time $n$ and there are O($N^3$) accessible nodes in total. If we just use a 
backward induction procedure, it will take O($N^3$) computations to compute all option 
prices at all accessible nodes since we need them to determine the optimal execution 
boundary and the optimal execution time for the buyer. In this paper, we prove some 
theorems showing that the optimal execution boundary for the buyer of a Russian option is 
of a monotonic form and bounded, and the option fair price at time $0$ depends only on 
the specific values on and below this optimal execution boundary. By a backward induction 
procedure on these specific values, we can determine the optimal execution boundary and 
the option price at time $0$ in order $N$ computations. We can also compute the option 
prices at all O($N^3$) accessible nodes in order $N^2$ computations. This is possible only 
because we can prove that for each time $n,$ even though there are O($n^2$) possible nodes,
only O($n$) option prices are relevant. \vs

If the buyer has not exercised his option before the expiration time $N$, then he certainly 
should exercise his option at time $N$ and receives $\beta^Nu^k,$ where $S_N = u^j$ and 
$Y_N = u^k.$ Therefore, $E(N,j,k) = \beta^Nu^k$ if $(N,j,k)$ is accessible. For any time 
$n < N,$ if the buyer has not exercised his option before time $n$, then he will get 
$\beta^nu^k$ if he exercises his option now, where $S_n = u^j,$ $Y_n = u^k,$ and $(n,j,k)$ 
is accessible. If he still does not want to exercise his option now, then the expected 
value of his option at time $n+1$ 
will be 
$$pE(n+1,j+1, max(j+1,k)) + (1-p)E(n+1,j-1,k),$$
where $p = \{u(1+r)-1\}/\{u^2-1\}.$ Hence the value of the expected value of his option 
at time $n$ is 
$$\alpha \{pE(n+1,j+1,max(j+1,k))+(1-p)E(n+1,j-1,k)\},$$
here $\alpha = (1 + r)^{-1}.$ Therefore, for any accessible node $(n,j,k),$
$$E(n,j,k) = $$
 $$ max\{\beta^nu^k,\alpha \{pE(n+1,j+1,max(j+1,k)) + 
(1-p)E(n+1,j-1,k)\}\}.$$ \vs

$E(N-1,k,k) = \beta ^{N-1}u^k$ if $\beta \leq \{(u+1)(1+r)\}/\{(2+r)u\}$ and $(N-1,k,k)$ 
is accessible. By mathematical induction we can show that $E(n,j,k) = \beta ^nu^k$ for all 
accessible nodes $(n,j,k),$ i.e., the buyer will either not buy the contract or will buy 
the contract and then exercise his option right away. Therefore, we will assume in this 
paper that $\{(u+1)(1+r)\}/\{(2+r)u\} < \beta \leq 1.$ \vs

The following lemmas are useful for identifying the optimal execution boundary and the 
optimal execution time for the buyer. They are exploited in our algorithm which requires 
only O($N$) computations to compute the option price at time $0$, the optimal execution 
boundary, and the optimal execution time for the buyer. They are also exploited in another 
algorithm which requires only O($N^2$) computations to compute the option prices $E(n,j,k)$ 
for all O($N^3$) accessible nodes. Lemmas $1$ and $2$ can be easily proved by mathematical 
induction. For the ease of reference, we include them. \vs

\noindent {\bf Lemma 1. } For fixed $n$ and $k$, $E(n,j,k) \leq E(n,j+2,k)$ if $(n,j,k)$ 
and $(n,j+2,k)$ are accessible. Similarly, for fixed $n$ and $j$, $E(n,j,k) \leq E(n,j,k+1)$ 
if $(n,j,k)$ and $(n,j,k+1)$ are accessible. \vs

\noindent {\bf Lemma 2. } For all $n = 0, 1, 2, ..., N-1$ and $k = 0, 1, 2, ..., n,$ 
$E(n,k,k) > \beta ^n u^k$ if $(n,k,k)$ is accessible. \vs

Lemma 2 means that before the expiration time the buyer should never exercise his option 
at a situation in which the current security price is equal to the maximum security price 
up to now. \vs

\noindent {\bf Lemma 3.} For all $n = 0, 1, 2, ..., N$ and $k = 0, 1, 2, ..., n-2,$ 
$E(n,j+2,k+2) = \\$  $u^2E(n,j,k)$ if $(n,j,k,)$ and $(n,j+2,k+2)$ are accessible. \vs

\noindent {\bf Proof: } Suppose that $n = N, j \leq k,$ and $k \leq N-2,$ then it is easy 
to see that Lemma 3 holds. Assuming that Lemma 3 holds for $n \geq m+1$ and suppose that 
$n = m.$ Then, by Lemma 2, 
$$u^2E(m,k,k) = u^2\{\alpha [pE(m+1,k+1,k+1) + qE(m+1,k-1,k)]\}$$
$$= \alpha \{pu^2E(m+1,k+1,k+1) + qu^2E(m+1,k-1,k)\}$$
$$= \alpha \{pE(m+1,k+3,k+3) + qE(m+1,k+1,k+2)\} = E(m,k+2,k+2).$$
So Lemma 3 holds for $n = m, k \leq n - 2,$ and $j = k.$ Now suppose that $n = m, k \leq 
n - 2,$ and $j < k$, then 
$$u^2E(m,j,k) = u^2 max\{\beta ^mu^k, \alpha [pE(m+1,j+1,k) + qE(m+1,j-1,k)] \}$$
$$= max\{\beta ^mu^{k+2}, \alpha [pu^2E(m+1,j+1,k) + qu^2E(m+1,j-1,k)] \}$$
$$= max\{\beta ^mu^{k+2}, \alpha[pE(m+1,j+3,k+2) + qE(m+1,j+1,k+2)] \} = E(m,j+2,k+2).$$
By mathematical induction, Lemma 3 holds. \vs

\noindent {\bf Lemma 4. } For $n = 1, 2, ..., N$ and $k = 1, 2, ..., n,$ $E(n,j,k) 
\geq uE(n,j-2,k-1)$ if $(n,j,k)$ is accessible. \vs

\noindent {\bf Proof: }  It is easy to check that Lemma 4 holds if $n = N.$ Suppose 
that Lemma 4 holds for $n = m+1, m+2, ..., N, k = 1, 2, ..., n,$ and accessible 
$(n,j,k).$ Now suppose that $n = m, 1 \leq k \leq m,$ and $(m,j,k)$ accessible. If 
$j < k,$ then
$$uE(m,j-2,k-1) = u\{max\{\beta ^mu^{k-1}, \alpha [pE(m+1,j-1,k-1) + qE(m+1,j-3,k-1)]\}\}$$
$$= max\{\beta ^mu^k, \alpha [puE(m+1,j-1,k-1) + quE(m+1,j-3,k-1)]\}$$
$$\leq max\{\beta ^mu^k, \alpha [pE(m+1,j+1,k) + qE(m+1,j-1,k)]\} = E(m,j,k).$$
If $j = k,$ then
$$uE(m,k-2,k-1) = u\{max\{\beta ^mu^{k-1}, \alpha [pE(m+1,k-1,k-1) + qE(m+1,k-3,k-1)]\}\}$$
$$= max\{\beta ^mu^k, \alpha [puE(m+1,k-1,k-1) + quE(m+1,k-3,k-1)]\}$$
$$\leq max\{\beta ^mu^k, \alpha [pu^2E(m+1,k-1,k-1) +quE(m+1,k-3,k-1)]\}$$
$$\leq max\{\beta ^mu^k, \alpha [pE(m+1,k+1,k+1) + qE(m+1,k-1,k)]\} = E(m,k,k)$$
since $u > 1,$ $E(m+1,k-1,k-1) > 0,$ $u^2E(m+1,k-1,k-1) = E(m+1,k+1,k+1),$ and 
$uE(m+1,k-3,k-1) \leq E(m+1,k-1,k).$ Therefore, Lemma 4 holds for $n = m, k = 1, 2, 
..., m,$ and $(n,j,k)$ accessible. By mathematical induction, Lemma 4 holds. \vs

\noindent {\bf Lemma 5. } For $n = 0, 1, 2, ..., N-1,$ $E(n+1,j+1,k+1) \leq \beta
uE(n,j,k)$ if $(n,j,k)$ is accessible. \vs

\noindent {\bf Proof: } If $n = N-1,$ then
$$\beta uE(N-1,j,k) \geq \beta u(\beta ^{N-1} u^k) = \beta ^N u^{k+1} = E(N,j+1,k+1).$$  
Suppose that Lemma 5 holds for $n = m+1, m+2, ..., N-1, k = 0, 1, 2, ..., n,$ and 
$(n,j,k)$ accessible. Now suppose that $n = m.$ If $j = k,$ then by Lemma 2,
$$\beta uE(m,k,k) = \beta u\{\alpha pE(m+1,k+1,k+1) + \alpha qE(m+1,k-1,k)\}$$
$$= \alpha p[\beta uE(m+1,k+1,k+1)] + \alpha q[\beta uE(m+1,k-1,k)]$$
$$ \geq \alpha pE(m+2,k+2,k+2) + \alpha qE(m+2,k,k+1) = E(m+1,k+1,k+1).$$
If $j < k,$ then
$$\beta uE(m,j,k) = \beta u max\{\beta ^m u^k, \alpha [pE(m+1,j+1,k) + 
qE(m+1,j-1,k)]\}$$
$$= max \{\beta ^{m+1} u^{k+1}, \alpha [p \beta uE(m+1,j+1,k) + q \beta uE(m+1,j-1,k)] 
\}$$
$$ \geq max \{\beta ^{m+1} u^{k+1}, \alpha [pE(m+2,j+2,k+1) + qE(m+2,j,k+1)]\} =
E(m+1,j+1,k+1).$$
Therefore, Lemma 5 holds for $n = m.$ By mathematical induction, Lemma 5 holds. \vs

\noindent {\bf Theorem 1. } Suppose that $(n,j,k)$ and $(n,j',k')$ are accessible. Then 
$E(n,j,k) = \beta ^nu^k$ implies that $E(n,j',k') = \beta ^nu^{k'}$ if $k - j \leq k' - 
j'.$ \vs

\noindent {\bf Proof: } By Lemma 3, we can and do assume that $k = 0$ or $1$ and $k' 
= 0$ 
or $1.$ If $k = k'$ and $k - j \leq k' - j',$ then $j' \leq j$. By Lemma 1, $E(n,j',k')
= E(n,j',k) \leq E(n,j,k).$ Therefore, Theorem 1 holds. If $k = 1$ and $k' = 0,$ then 
$j' \leq j - 1$. Since $(n,j,1)$ and $(n,j',0)$ are accessible, $j = 2 - n + 2i$ for 
some non-negative integer $i$ and $j' = 0 - n + 2i'$ for some non-negative integer $i'.$ 
Since $j' \leq j - 1,$ $2i' \leq 1 + 2i.$ Since $i$ and $i'$ are non-negative integers,
$i' \leq i$ and $j' \leq j - 2.$ By Lemma 1, we can assume that $j' = j -2.$ By Lemma 4, 
$E(n,j',0) = E(n,j-2,0) \leq E(n,j,1)/u.$ Therefore, Theorem 1 holds. If $k = 0$ and 
$k' = 1,$ then $j' \leq j + 1.$ Since $(n,j,0)$ and $(n,j',1)$ are accessible, 
$j = 0 - n + 2i$ for some non-negative integer $i$ and $j' = 2 - n + 2i'$ for some 
non-negative integer $i'.$ Since $j' \leq j + 1,$ $2i' \leq 2i -1.$ Since $i'$ and $i$ are 
non-negative integers, $i' \leq i - 1$ and $j' \leq 2 - n + 2(i - 1) = j.$ By Lemmas 1 and 
4, $E(n,j',1) \leq E(n,j,1) \leq E(n,j+2,2)/u.$ By Lemma 2, $E(n,j+2,2) = u^2E(n,j,0).$ 
Hence $E(n,j',1) \leq uE(n,j,0).$ Therefore, Theorem 1 holds. \vs 

For each expiration time $N,$ let $n_N = min\{n|1 \leq n \leq N, E(n,j,k) = \beta ^n u^k$ 
for some accessible node $(n,j,k)\}.$ Since $E(N,j,k) = \beta ^N u^k$ for any accessible 
node $(N,j,k),$ $n_N$ is well-defined. For each $n = n_N, n_N+1, ..., N-1,$ let $t_n$ be 
the smallest positive integer such that $E(n,j,k) = \beta ^nu^k$ if $(n,j,k)$ is 
accessible and $k-j \geq t_n.$ By Lemma 2 and Theorem 1, $t_n$ is well defined for all 
$n = n_N, n_N+1,..., N-1.$ For the ease of presentation, we will let $t_N = 0$ and 
$t_n = t_{n_N}$ for all $n = 0, 1, 2, ..., n_N-1.$ \vs

\noindent {\bf Theorem 2. } For $n = 0, 1, ..., N-1,$ $t_n$ is decreasing in $n,$ 
$t_{N-1} = 1,$ and $t_n \leq t_{n+1} + 1.$ \vs

\noindent {\bf Proof: } Suppose that $n = n_N, ,n_N+1, ..., N-2,$ $(n,j,k)$ is accessible, 
and $E(n,j,k)$ $ = \beta ^n u^k,$ by Lemma 5, $E(n+1,j+1,k+1) \leq \beta uE(n,j,k) = 
\beta ^{n+1} u^{k+1}.$ Since $E(n+1,j+1,k+1) \geq \beta ^{n+1} u^{k+1},$ $E(n+1,j+1,k+1) =
\beta ^{n+1} u^{k+1}.$ By Theorem 1, we can conclude that $t_{n+1} \leq t_n$ for all $n 
= n_N, n_N+1, ..., N-1.$ It is also easy to check that $t_{N-1} = 1.$ \vs 

To show that $t_n \leq t_{n+1} + 1,$ by Lemma 4, it suffices to show that if $\beta 
^nu^k = E(n,j,k) $ and $\beta ^nu^{k-1} < E(n,j,k-1),$ then $E(n+1,j+1,k-1) > \beta 
^{n+1}u^{k-1}$ if $(n,j,k)$ is accessible. If $E(n+1,j+1,k-1) = \beta ^{n+1}u^{k-1},$ 
then by Lemma 1, $E(n+1,j-1,k-1) = \beta ^{n+1}u^{k-1}.$ If $j \leq k - 2,$ then $\alpha 
[pE(n+1,j+1,k-1) + qE(n+1,j-1,k-1)] = \alpha \beta ^{n+1} u^{k-1} < \beta ^nu^{k-1}$ 
since $0 < \alpha < 1$ and $0 <\beta \leq 1.$ Hence $E(n,j,k-1) = max\{\beta ^n 
u^{k-1}, \alpha[pE(n+1,j+1,k-1) + qE(n+1,j-1,k-1)]\} = \beta ^n u^{k-1}$ and we get a 
contradiction. Therefore, $t_n \leq t_{n+1} + 1$ for all $n = n_N, n_N+1, ..., N-1.$ 
Since $t_n = t_{n_N}$ for all $n = 0, 1, 2, ..., n_N-1$ and $t_N = 0,$ Theorem 2 holds 
for $n = 0, 1, ..., N-1.$ \vs

For all $n = 0, 1, 2, ..., N,$ let $X_n = Y_n/S_n$ and $\tau _{N,n}$ be the optimal 
execution time for the buyer if he bought the option at time $n.$ \vs

\noindent {\bf Theorem 3. } For each security price process $\{S_0, S_1, S_2, ...,S_N\}$ 
and each $n = 0, 1,$ $2, ..., N,$ the optimal execution time $\tau _{N,n}$ is given by 
$\tau _{N,n}(S_0, S_1, ..., S_N)$ $= min \{m | m \geq n, X_m \geq u^{t_m}\}.$ Moreover, 
the optimal execution boundary is $\{u^{t_0}, u^{t_1},$ $ u^{t_2}, ..., u^{t_{N-1}}, 
u^{t_N}\}.$ \vs

In [5], Peskir studied this problem in a continuous time setting. He (Theorem 3.1 of 
[5]) showed that the optimal execution boundary is the unique continuous decreasing 
solution of a nonlinear integral equation. The results of Theorems 2 and 3 here are 
consistent with his result in a discrete time setting. \vs

In [4], Kramkov and Shiryaev studied this problem in a different approach which can be
stated as follows: For each $n = 1, 2, ..., N$, $\epsilon _n$ is a random variable and 
takes two values $+1, -1.$ So $S_n = S_0u^{\epsilon _1+\epsilon _2+...+\epsilon _n}$ 
for all $n = 1, 2, ..., N.$ If the buyer exercises his option at time $n$, then his payoff 
is $\beta ^nY_n.$ From the general pricing theory of American type options, the option fair 
price at time $0$ is 
$$V_N(1) = max\{E(\alpha ^{\tau} \beta ^{\tau} Y_{\tau})|0 \leq \tau \leq N\},$$
where $\tau $ is a stopping time and E is the expectation with respect to the martingale 
measure, i.e., $\epsilon _1, \epsilon _2, ..., \epsilon _N$ are i.i.d. random variables
such that  
$$E(\alpha u^{\epsilon _i}) = p\alpha u + (1 - p)\alpha /u = 1.$$
Since $X_n = Y_n/S_n,$ it is easy to see that $X_n$ takes values in the set $\{1, u, u^2, 
..., u^n\}$ and 
$$V_N(1) = max\{E^*(\beta ^{\tau }X_{\tau }|X_0 = 1)|0 \leq \tau \leq N\},$$
where $E^*$ is the expectation with respect to the new probability measure $P^*$.
With respect to this new probability measure $P^*,$ $\epsilon _1, \epsilon _2, ..., 
\epsilon _N$ are i.i.d. random variables such that $P^*(\epsilon _i = 1) = p^* = \alpha 
up$ and $P^*(\epsilon _i = -1) = 1 - p* = \alpha (1-p)/u.$ It is easy to check that 
$p^* = \alpha up = (u - \alpha)/(u - 1/u) > 1/2$ since $u > 1 + r = 1/\alpha.$ \vs

Notice that $X_{n+1} = max\{X_n/u^{\epsilon _{n+1}},1\}$ for all $n = 0, 1, 2, ..., N-1.$
So we can compute $V_N(1)$ by the following backward induction procedure: For $n = 0, 1, 2, 
..., N$ and $k = 0, 1, 2, ..., n,$ let 
$$G_N(n,k) = max\{E^*(\beta ^nX_n|X_n = u^k), E^*(\beta ^{\tau} X_{\tau}|n \leq \tau 
\leq N, X_n = u^k)\}.$$
Since $G_N(N,k) = \beta ^Nu^k$ for all $k = 0, 1, 2, ..., N.$ For all 
$n = 0, 1, 2, ..., N-1$ and $k = 0, 1, 2, ..., n,$ 
$$G_N(n,k) = max\{\beta ^nu^k, p^*G_N(n+1,max(0,k-1)) + (1-p^*)G_N(n+1,k+1)\}.$$
It is clear that $V_N(1) = G_N(0,0)$ since we assume that $S_0 = 1.$ This procedure 
requires O($N^2$) computations to compute the option price $G_N(0,0)$ at time $0$ (the 
node $(0,0,0)).$ However, this procedure can not produce the option prices at other 
accessible nodes.  Theorem 5 below gives an elegant algorithm which computes the 
optimal execution boundary and the option price at time $0$ in order $N$ computations. 
Theorem 6 below gives another algorithm which computes the option prices at all possible 
accessible nodes time in order $N^2$ computations. \vs

To determine the optimal execution time for the buyer who bought the option at time $0$, 
Kramkov and Shiryaev gave the following algorithm. For each $n = 1, 2, ..., $ each 
$x$ in the set $H = \{1, u, u^2, ..., \},$ and each function f defined on $H$ let
$Q_{\beta }f(x) = $ $ max\{f(x), \beta [p^*f(max(1,x/u)) + (1-p^*)f(xu)]\},$ and let
$Q^n_{\beta }f(x) = Q_{\beta }[Q^{n-1}_{\beta }f(x)].$ Then $V_n(x) = Q^n_{\beta }g(x)$, 
where $g(x) = x.$ The optimal execution time $\tau _{N,0}$ for the buyer who bought the 
option at time $0$ is given by $\tau _{N,0} = min\{n|0 \leq n \leq N, V_{N-n}(X_n) = X_n\}.$ 
This procedure is complicated and slow. The procedure given in Theorem 5 below is much
easier and faster. \vs 

For each $x$ in H, let $V(x) = lim_{n \rightarrow \infty }V_n(x).$  Kramkov and Shiryaev 
showed that $V(x) = sup\{E^*_x(\beta ^{\tau }X_{\tau }) | 0 \leq \tau < \infty \}$ and 
that there exists a $x_0 = u^{k_0}$ such that $V(x) = x$ for all $x$ in H and $x \geq x_0.$ 
Since $Q_{\beta }f(x) \geq f(x)$, $V_{n+1}(x) = Q_{\beta }[V_n(x)] \geq V_n(x) \geq x$ 
for all $x$ in H. Since $V(x) = lim_{n \rightarrow \infty }V_n(x),$ $V_n(x) = x$ for all
$x \geq x_0$ and all $n = 1, 2, .. .$ Hence $E(n,-k_0,0) = \beta ^n$ for all $n \geq 
k_0.$ Based on this observation and Theorem 2, we have the following theorem. \vs

\noindent {\bf Theorem 4. } There exists a positive integer $k_0$ which depends only on 
$\beta, r,$ and $u$ such that for any positive integer $N,$ $t_n \leq k_0$ for all $n 
 = 1, 2, 3, ..., N.$ \vs 

Notice that $G_N(n,k) = \beta ^nu^k$ if and only if $k \geq t_n.$ Based on Theorem 2, we can 
use the following backward induction procedure to compute $t_{N-1}, t_{N-2}, ..., t_1$ 
and $V_N(1).$ First let $t_{N-1} = 1$, $G_N(N-1,0) = p^*\beta ^N + (1-p^*)\beta ^Nu,$
and  $G_N(N-1,1) = \beta ^{N-1}u.$ Next let $t_{N-2} = t_{N-1}$ if $\beta ^{N-2}u \geq 
p^*G_N(N-1,0) + (1-p^*)\beta ^{N-1}u^2,$ $t_{N-2} = t_{N-1} + 1$ otherwise. Let 
$G_N(N-2,k) = p^*G_N(N-1,max(0,k-1)) + (1-p^*)G_N(N-1,k+1)$ for $k = 0, t_{N-2} - 1$ and 
$G_N(N-2,t_{N-2}) = \beta ^{N-2}u^{t_{N-2}}.$ Now suppose that we have computed $1 = 
t_{N-1} \leq t_{N-2} \leq ... \leq t_{n+1}$ for some positive integer $n_N \leq n \leq 
N - 2$ and have computed all $G_N(m,k)$ for all $m = n+1, n+2, ..., N-1$ and $k = 0, 1, 2, ..., t_m.$ 
Let $t_n = t_{n+1}$ if $\beta ^nu^{t_{n+1}} \geq p^*G_N(n+1,t_{n+1}-1) + (1-p^*)\beta 
^{n+1}u^{t_{n+1}+1},$ $t_n = t_{n+1} + 1$ otherwise. Let $G_N(n,k) = p^*G_N(n+1,
max(0,k-1)) + (1-p^*)G_N(n+1,k+1)$ for all $k = 0, 1, 2, ..., t_n-1$ and $G_N(n,t_n) = 
\beta ^n u^{t_n}.$ By this procedure, we will construct the the sequence $\{t_{n_N}, 
t_{n_N+1}, ..., t_{N-1}\}.$ For $n = 0, 1, 2, ..., n_N-1,$ let $G_N(n,k) = p^*G_N(n+1,
max(0,k-1)) + (1-p^*)G_N(n+1,k+1)$ for all $k = 0, 1, 2, ..., n.$ The option price 
$V_N(1)$ at time $0$ is equal to $G_N(0,0),$ the optimal execution boundary for the 
buyer will be  $\{u^{t_0}, u^{t_1}, u^{t_2}, ..., u^{t_{N-1}}, 1\}.$ Notice that $n < 
t_n$ for $n = 0, 1, 2, ..., n_N-1.$ Since $t_n$ is bounded for all $n = 1, 2, ..., N-1,$ 
and on each step, we need only at most $t_n+2$ computations, the total computations will 
be O($N$). Therefore, we have the following theorem. \vs

\noindent {\bf Theorem 5. } The procedure described above requires in order $N$ 
computations to compute the optimal execution boundary $\{u^{t_0}, u^{t_1}, u^{t_2}, 
..., u^{t_{N-1}}, u^{t_N}\}$ and the option price $V_N(1)$ at time $0.$ \vs

Based on Theorems $4$ and $5,$ we can use the following algorithm to compute $E(n,j,k)$ 
for all accessible nodes $(n,j,k).$ First let $E(N,j,k) = \beta ^Nu^k$ for all $k = 0, 1, 2, 
..., N$ and $j = 2k - N, 2k - N + 2, ...,  \leq k.$ Then for $n  = 0, 1, 2, ..., N - 1$ and 
$k = 0, 1, 2, ..., n,$ let $E(n,j,k) = \beta ^nu^k$ for all $j = 2k-n, 2k-n+2, ..., \leq 
k-t_n$ and $E(n,j,k) = \alpha[p(n+1,j+1,max(j+1,k)) + qE(n+1,j-1,k)]$
for all $k-t_n < j \leq k$ and accessible $(n,j,k).$ For $n = 0, 1, 2, ..., N-1,$ there are 
only $n(t_n+2)/2$ computations. Since $t_0, t_1, t_2, ..., t_{N-1}$ are bounded, we need 
only O($N^2$) computations to compute $E(n,j,k)$ for all O($N^3$) accessible nodes. 
Therefore, we have the following theorem. \vs

\noindent {\bf Theorem 6. } The procedure described above requires only O($N^2$) 
computations to compute all option values $E(n,j,k)$ at all O($N^3$) accessible nodes. \vs

Theorems 3 and 5 show that for fixed $\beta , r, $ and $u,$ the optimal execution time
depends only on $n$ and $X_n$ and the optimal execution boundary is of a monotonic form
and bounded. These facts are exploited in our algorithms for computing the option 
prices and the optimal execution boundary. \vs 

Notice that for each $n = 0, 1, 2, ..., N$, there are $n+1$ possible values for $X_n$. So 
there are $(N+1)(N+2)/2$ entries for the whole table $V_{N-n}(X_n), X_n = 1, u, u^2, ..., 
u^n,$ and $n = 0, 1, 2, ..., N.$ We either use this table to find the optimal execution 
time for each price process $\{S_0, S_1, S_2, ..., S_N\}$. Or we compute $V_{N-n}(X_n)$ each 
time when we get a new $X_n,$ suppose we did not exercise the option yet, then check whether
$V_{N-n}(X_n) = X_n$ or not. It requires O($(N-n)^2/2$) computations. In this respect, our 
approach is faster and simpler since we need only keep $N+1$ entries of $u^{t_n}.$ For each 
price process $\{S_0, S_1, S_2, ..., S_N\},$ we can update $X_n$ easily, then decide we 
should exercise the option or not right away. \vs

In fact, noticing that if $x = u^k$ for some non-negative integer $k,$ $V_{N-n}(x) = 
max\{E^*(\beta ^\tau X_{\tau }|X_0 = x) | 0 \leq \tau \leq N-n\}$ $= G_{N-n}(0,k).$ By 
Theorem 5, we can have a procedure which requires only O($N-n$) computations to 
compute $V_{N-n}(x).$ It will be more efficient than the procedure $V_{N-n}(x) = 
Q_{\beta }^{N-n}g(x)$ which requires O($(N-n)^2/2$) computations. \vs


Suppose that we have computed the set $\{t_1, t_2, ..., t_N\}$ by the backward induction
procedure described in Theorem 5 for the option with expiration time $N$ and let 
$\{t'_1, t'_2, ..., t'_{N+M}\}$ be the counter part for the option with expiration 
time $N+M,$ where $M$ is a positive integer. Do we have to compute the entire set 
$\{t'_1, t'_2, ..., t'_{N+M}\}?$ The following theorem reveals that there is a 
relationship between the set  $\{t_1, t_2, ..., t_N\}$ and the set $\{t'_1, t'_2, ..., 
t'_{N+M}\}.$ \vs

\noindent {\bf Theorem 7.} Let $\{t_1, t_2, ..., t_N\}$ and  $\{t'_1, t'_2, 
..., t'_{N+M}\}$ be as defined above. Then $t'_{N+M-j}$ $ = t_{N-j}$ for all $j = 0, 1, 
2, 
..., N-n_N.$  \vs

\noindent {\bf Proof: } We will prove Theorem 7 when $M = 1.$ The general case can be 
proved by mathematical induction. \vs

Notice that $G_{N+1}(N+1,k) = \beta ^{N+1} u^k$ and $G_N(N,k) =
\beta ^N u^k$ for all $k = 0, 1, 2, ..., N.$ Also notice that 
$$G_N(n,k) = max\{ \beta ^n u^k, p^*G_N(n+1, max(0,k-1)) + (1-p^*)G_N(n+1,k+1)\}$$
and
$$G_{N+1}(n+1,k) $$
$$= max\{\beta ^{n+1} u^k, p^*G_{N+1}(n+2, max(0,k-1)) + (1-p^*)G_{N+1}(n+2,k+1)\}$$
for all $k = 0, 1, 2, ..., N$ and $n = 0, 1, 2, ..., N-1.$ By mathematical induction, 
it is easy to see that $G_{N+1}(n+1,k) = \beta G_N(n,k)$ for all $k = 0, 1, 2, ..., n$ 
and $n = n_N, n_N+1, ..., N.$ $G_N(n,k) = \beta ^n u^k$ if and only if $G_{N+1}(n+1,k) 
= \beta ^{n+1} u^k$ for $n = n_N, n_N+1, ....$ It implies that $t_N  = t'_{N+M}, 
t_{N-1} = t'_{N+M-1}, ..., t_{n_N} = t'_{n_N+M}.$ \vs

Based on Theorem 7, we can use the optimal execution boundary of an option and some 
additional computations to get the optimal execution boundary for a new option with 
a longer expiration time. Conversely we can use the tail segment of the 
optimal execution boundary of an option for the optimal execution boundary of a new 
option with a shorter expiration time. This is another nice property of the approach
presented in this paper. Theorem 7 also confirms that if the time horizon is infinite, 
then the optimal execution boundary is a horizontal line and the optimal execution time 
for the buyer is the first $n$ such that $X_n = u^{t_1}$ since $t_1 = t_2 = ... = b $
for some positive constant $b$ if the time horizon is infinite. The results presented 
in this paper are consistent with the results in [6] by Shepp and Shiryaev. \vs


\newpage

\begin{center} {\bf REFERENCES} \end{center} \vs
\begin{enumerate}
\item Cox, J.C., Ross, R.A., and Rubinstein, M., Option Pricing: A Simplified Approach, J.
Financial Economics, 7 (1979), pp. 229-263.
\item Duffie, J.D. and Harrison, J.M., Arbitrage Pricing of Russian Options and Perpetual
Lookback Options, Ann. Appl. Probab., 3 (1993), 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., On the Rational Pricing of the "Russian Option" for
the Symmetrical Binomial Model of a (B,S)-Market, Theory Probab. Appl., 39 (1994), pp. 
153-162.
\item Peskir, G., The Russian Option: Finite Horizon. (to appear in Finance and 
Stochastics, 2003)
\item Shepp, L.A. and Shiryaev, A.N., The Russian Option: Reduced Regret, Ann. Appl. Probab.,
3 (1993), pp. 631-640.
\end{enumerate}
\end{document}
