=Paper=
{{Paper
|id=Vol-1726/paper-05
|storemode=property
|title=Solving Optimal Stopping Problem by Using Computer Algebra Systems
|pdfUrl=https://ceur-ws.org/Vol-1726/paper-05.pdf
|volume=Vol-1726
|authors=Vladimir M. Khametov,Elena A. Shelemekh,Evgeniy V. Yasonov
}}
==Solving Optimal Stopping Problem by Using Computer Algebra Systems==
https://ceur-ws.org/Vol-1726/paper-05.pdf
Solving Optimal Stopping Problem by Using
Computer Algebra Systems
Vladimir M. Khametov, Elena A. Shelemekh, and Evgeniy V. Yasonov
National Research University – Higher School of Economics, Moscow, Russia;
Central Economics and Mathematics Institute of RAS, Moscow, Russia
khametovvm@mail.ru, letis@mail.ru, evyasonov@gmail.com
Abstract. The article deals with optimal stopping problem for arbi-
trary sequence of bounded random values (finite horizon). We obtained
recurrent relations in the form of a Bellman equation and established
a criteria of optimality for a stopping moment. Using this results we
study how computer algebra systems can be applied to solve optimal
stopping problems. We used Maple 14 to solve optimal stopping prob-
lem for geometric random walk and managed to find explicit formulas
for this problem. Also for geometric random walk explicit solution for
any continuous piecewise linear convex downward reward function has
been found.
Keywords: optimal stopping problem, computer algebra systems, ran-
dom walk, explicit solution
1 Introdution
Optimal stopping problem arises in areas of statistics (sequential hypothesis
testing), mathematical finance (American options, the change-point problem)
and others fields (see [1–4,6–13]). In [2,4,6,7,12,13] the main results for problems
with infinite horizon were obtained. In this paper we consider optimal stopping
problem with finite horizon.
In [1] they suppose, that stopping region is separated from continuation re-
gion with one point only. Under the assumption optimal stopping problem is
solved with use of Wiener-Hopf factorization.
In [6] many examples of explicit solution for optimal stopping problems with
finite horizon can be found (see also [3, 4, 12]).
In [8, 9] they suppose, that: i) a Markov process is observed; ii) reward func-
tions are monotonic and convex downward. In this case sufficient conditions,
that stopping region is separated from continuation region with one point only,
are established.
In this work we obtain recurrent relations in the form of a Bellman equa-
tion (Theorem 3) and establish a criteria of optimality for a stopping moment
(Theorems 4 and 5). Note that in literature we found only sufficient conditions,
under which value function satisfies recurrent relations in the form of a Bellman
equation.
It’s well known that optimal stopping problem can be reduced to a free
boundary problem for a Bellman type equation [13]. But to solve a free bound-
ary problem is a challenging task itself. One of our purposes was to study how
computer algebra systems can be applied to solve optimal stopping problems.
We used Maple 14 to solve optimal stopping problem for geometric random walk
and managed to find explicit formulas for this problem. Also for geometric ran-
dom walk explicit solution for any continuous piecewise linear convex downward
reward function has been found.
2 The Optimal Stopping Problem
Suppose we have: i) (Ω, F, (Fn )n≥0 , P) – a stochastic basis [12]; ii) N ∈ N+ –
horizon; iii) TnN – set of stopping moments τ regarding the filtration (Fn )0≤n≤N
[12], with values in {n, . . . , N }; iv) (fn , Fn )0≤n≤N – sequence of bounded random
variables (in mathematical finance – utility of an observer); v) L0 (Ω, F0 ) – set
of all P-a. s. bounded F0 -measurable random variables [7, §A.7].
We will study the following problem
E[fτ ∧N |F0 ] → ess sup, (1)
τ ∈T0N
where E[ · |F0 ] is a conditional expectation taken regarding to σ-algebra F0 (see
definition in [7], definition of essential supremum can be found in [5, 7]).
The problem (1) is called optimal stopping problem (see [12]) where utility
of an observer is maximized.
We denote v0N , ess sup E[fτ ∧N |F0 ].
τ ∈T0N
Definition 1. A pair τ ∗ , v0N ∈ (T0N , L0 (Ω, F0 )) is said to be a solution of the
problem (1) if v0N = E[fτ ∗ ∧N |F0 ] P-a. s. Stopping moment τ ∗ ∈ T0N is called
an optimal stopping moment, F0 -measurable random variable v0N is called value
function at moment 0.
3 Recurrent Relations for Value Function. Criteria of
Optimality of a Stopping Moment
We use a stochastic dynamic programming method to obtain a value function.
For any n ∈ {1, . . . , N } we denote
vnN , ess sup E[fτ ∧N |Fn ]. (2)
τ ∈TnN
Definition 2 ([12]). vnN is called value function at a moment n.
We study value function properties below.
Theorem 1. Assume that supn∈N ||fn ||L0 (Ω,Fn ) ≤ C. Then |vnN | ≤ C P-a. s.
Proof. Obviously,
|vnN | ≤ ess sup E(|fτ | |Fn ) P-a. s. (3)
τ ∈TnN
N
P N
P
As fτ = fi 1{τ =i} , we have |fτ | ≤ |fi |1{τ =i} ≤ C P-a. s.
i=n i=n
Using previous preposition and (3) we obtain that |vnN | ≤ C P-a. s.
Theorem 2. Under assumptions of Theorem 1 sequence (vnN , Fn )0≤n≤N is a
supermartingale.
Proof. By definition of vnN we observe P-a. s.
vnN , ess sup E[fτ |Fn ] ≥ ess sup E[fτ |Fn ] = ess sup E(E[fτ |Fn+1 ]|Fn ). (4)
τ ∈TnN N
τ ∈Tn+1 N
τ ∈Tn+1
Using properties of essentual supremum for any n we obtain P-a. s.
vnN ≥ E(ess sup E[fτ |Fn+1 ]|Fn ) = E(vn+1
N
|Fn ). (5)
N
τ ∈Tn+1
The proof is complete.
Let us study a recurrent relations describing evolution of value function in
backward time.
Theorem 3. (vnN , Fn )0≤n≤N is a sequence of value functions if and only if it
satisfies recurrent relations P-a. s.
vnN = max fn ; E[vn+1
N
|Fn ] , vnN |n=N = fN .
(6)
Proof. Necessity. Let us derive that if (vnN , Fn )0≤n≤N is a sequence of value
functions, then recurrent relations (6) are satisfied.
First we will prove that for any n ∈ {0, . . . , N } the following inequality is
satisfied P-a. s.
vnN ≥ max fn ; E[vn+1
N
|Fn ] . (7)
Note, that:
– random variable 1{τ =n} fn is Fn -measurable;
– conditional expectation has a tower property. Due to the definition and prop-
erties of essentual supremum [5] for any n ∈ {0, . . . , N } we can conclude that
P-a. s.
" τ ∧N #
X
vnN = ess sup E 1{τ =i} fi Fn ≥
τ ∈TnN i=n
( " " τ ∧N # #)
X
≥ ess sup 1{τ =n} fn + 1{τ >n} E E 1{τ =i} fi Fn+1 Fn =
N
τ ∈Tn+1 i=n+1
= 1{τ =n} fn + 1{τ >n} ess sup E [E [fτ ∧N |Fn+1 ] |Fn ] =
N
τ ∈Tn+1
" #
= 1{τ =n} fn + 1{τ >n} E ess sup E [fτ ∧N |Fn+1 ] Fn =
N
τ ∈Tn+1
N
= 1{τ =n} fn + 1{τ >n} E vn+1 |Fn . (8)
Left part does not depend on a stopping moment τ ∈ TnN . If we apply ess sup
by τ ∈ TnN to a right part of (8), we will obtain (7).
Let us derive that the following inequality is satisfied P-a. s.
vnN ≤ max fn ; E[vn+1
N
|Fn ] . (9)
Due to the fact that random variable 1{τ =n} fn is Fn -measurable, definitions
N
of ess sup and vn+1 , tower property of conditional expectation we can conclude
that P-a. s.
vnN = ess sup 1{τ =n} fn + 1{τ >n} E [E [fτ ∧N |Fn+1 ] |Fn ] ≤
τ ∈TnN
( " #)
≤ ess sup 1{τ =n} fn + 1{τ >n} E ess sup E [fτ ∧N |Fn+1 ] Fn =
τ ∈TnN N
τ ∈Tn+1
N N
= ess sup 1{τ =n} fn + 1{τ >n} E vn+1 |Fn = max fn ; E[vn+1 |Fn ] . (10)
τ ∈TnN
Obviously, vnN |n=N = E[fN N
|FN ] = fN P-a. s. Hence with (7) and (9) we
obtain (6).
Sufficiency. Proof of sufficiency is well known and can be found in [2, 7, 13].
Remark 1. As we stated above, proof of sufficiency in Theorem 3 is well known.
Note, that necessity is new.
Using Theorem 3 we obtain necessary and sufficient conditions, under which
a pair τ ∗ , v0N ∈ (T0N , L0 (Ω, F0 )) is a solution of the problem (1).
Theorem 4. Stopping moment τ ∗ is an optimal stopping moment if and only
if τ ∗ = min 0 ≤ n ≤ N : fn = vnN .
Proof. Let us define τ ∗ = min 0 ≤ n ≤ N : vnN = fn . Obliviously, vτN∗ = fτ ∗
P-a. s. Suppose the stopping moment τ ∗ is not an optimal stopping moment, i. e.
there exists a stopping moment τ such that τ ≥ τ ∗ .
Note that sequence {vnN } is a supermartingale with respect to the measure
P (Theorem 2). Due to Doob-Meyer decomposition theorem for any n ∈ N0 it
follows that
vnN = v0 + Mn − An , (11)
where Mn is a martingale with respect
Pto the probability measurePP, An is an in-
N N
creasing sequence. Obviously, vτN∗ = i=0 viN 1{τ ∗ =i} and vτN = i=0 viN 1{τ =i} .
Hence with (11) we can conclude vτN∗ = v0 + Mτ ∗ − Aτ ∗ and vτN = v0 + Mτ − Aτ
P-a. s. From this two formulas we obtain
vτN = vτN∗ + (Mτ − Mτ ∗ ) − (Aτ − Aτ ∗ ) P-a. s. (12)
Due to the fact that Aτ − Aτ ∗ ≥ 0 and from (12) we can conclude immediately
that
vτN ≤ vτN∗ + (Mτ − Mτ ∗ ) P-a. s. (13)
Let us apply conditional expectation E [ · |Fn ] to (13). Thus we have P-a. s.
E vτN |Fn ≤ E N
τ ∗ |Fn = E [fτ ∗ |Fn ] . (14)
As E vτN |Fn ≥ E fτN |Fn from (14) for any τ we obtain
E fτN |Fn ≤ E fτN∗ |Fn .
(15)
Note, that (15) is a necessary and sufficient condition of optimality for the stop-
ping moment τ ∗ . The proof is complete.
Using theorems 3 and 4 we can derive another criterion of optimality for
stopping moment τ ∗ ∈ T0N .
Theorem 5. A pair τ ∗ , v0N ∈ (T0N , L0 (Ω, F0 )) is a solution of the problem (1)
if and only if:
1. sequence (vnN , Fn )0≤n≤τ ∗ ∧N is a martingale in respect to measure P;
2. vnN |n=τ ∗ ∧N = fτ ∗ ∧N P-a. s.
Proof. Sufficiency. Let (vnN , Fn )0≤n≤τ ∗ ∧N be a martingale with respect to mea-
sure P and vnN |n=τ ∗ ∧N = fτ ∗ ∧N P-a. s. Hence with solution definition we can
conclude required equalities
v0N = E vτN∗ ∧N |F0 = E [fτ ∗ ∧N |F0 ] .
(16)
Necessity. Let τ ∗ , v0N be a solution of the problem (1). From the proof of
Theorem 3 we conclude that P-a. s.
vnN = ess sup(1{τ =n} fn + 1{τ >n} E vn+1
N
|Fn ) =
τ ∈TnN
N
= 1{τ ∗ =n} fn + 1{τ ∗ >n} E vn+1 |Fn . (17)
As vτN∗ = fτ ∗ , we have 1{τ ∗ =n} vnN = 1{τ ∗ =n} fn . By (6) and (17) we may find
vnN = max fn ; E[vn+1
N N
|Fn ] ≥ E[vn+1 |Fn ] = E[ess sup E(fτ |Fn+1 )|Fn ] ≥
N
τ ∈Tn+1
≥ E[E(fτ ∗ |Fn+1 )|Fn ] = E[fτ ∗ |Fn ]. (18)
Let us apply conditional expectation E[ · |F0 ] to (18). Thus we have
E[vnN |F0 ] ≥ E[fτ ∗ |F0 ] = v0N . (19)
Moreover, v0N = ess sup E(fτ |F0 ) ≥ ess sup E(fτ |Fn ) = vnN . So, we have
τ ∈T0N τ ∈TnN
v0N ≥ E(vnN |F0 ). (20)
So, from (19) and (20) it follows that (vnN , Fn )0≤n≤τ ∗ ∧N is a martingale with
respect to the measure P.
Remark 2. Unlike [7] and others, Theorem 4 is a criterion for optimal stopping
moment.
4 Examples based on using Maple 14
Theorems 1–5 allow us to use computer algebra systems to solve the optimal
stopping problem. In this section we present some new examples of solutions for
optimal stopping problems based on using computer algebra system Maple 14.
Suppose that random sequence (Sn , Fn )0≤n≤N satisfies the recursive relation
Sn+1 = Sn (1 + ρn+1 ), Sn |n=0 = S0 P-a. s., where {ρn }0≤n≤N is a sequence of
jointly independent identically distributed random values taking values in the
compact set of {a, b}, a, b ∈ R1 , where −1 < a < 0 < b < ∞.
|a|
Let p∗ = |a|+b , q ∗ = 1 − p∗ . This means that random sequence {Sn }0≤n≤N
is a martingale with respect to the measure P and fintration (Fn )0≤n≤N , where
Fn = σ{S0 , . . . , Sn }.
We can prove easily that vnN is a Markov random function. There exists Borel
function vnN (x) such as vnN |x=Sn = vnN and it satisfies the following formula
vnN (x) = max(fn (x), vn+1
N
(x(1 + a))p∗ + vn+1
N
(x(1 + b))q ∗ ). (21)
Definition 3 ([12]). For any n ∈ {0, . . . , N } set Dn , x ∈ R+ : fn (x) = vnN (x)
is called stopping region at a moment n.
Example 1. Suppose that:
– for any n ∈ {0, . . . , N } there is function fn (x) = β n (x − K)+ , where K > 0,
0 < β ≤ 1;
– −1 < a < 0 < b < ∞;
Fig. 1. Functions f0 (x), v010 (x) and stopping region D0
– for any n ∈ {0, . . . , N } probabilities p∗ and q ∗ are known (i. e. {Sn }0≤n≤N
is a martingale with respect to P and filtration (Fn )0≤n≤N ).
This problem arises in trading of American options (see [1, 10, 13]).
Let K = 5, −a = b = 0.5, β = 0.9, N = 10. At Fig. 1 see plots of functions
f0 (x), v010 (x) and stopping region D0 .
We can conclude that in this example for any n ∈ {0, . . . , N } stopping region
has the following form: Dn = (0, x∗1,n ] ∪ [x∗2,n , ∞), where x∗1,n , x∗2,n ∈ R+ are
stopping region’s boundaries (see Fig. 2).
Example 2. Suppose for any n ∈ {0, . . . , N }:
0, x ≤ 1,
1, 1 < x ≤ 2,
fn (x) =
2, 2 < x ≤ 3,
3, x > 3.
Let a = −0.05, b = 0.05, p = q = 0.5, N = 10. At Fig. 3 there are plots of
functions f0 (x), v010 (x) and of stopping region D0 .
5 Optimal Stopping Problem Solution for Any Piecewise
Linear Continues Convex Downward Reward Function
In this section we solve optimal stopping problem with geometric random walk
in a case of piecewise linear continues convex downward reward functions.
Assumption 1. Let function f (x) = A0i x+Bi0 be continues, where x ∈ c0i , c0i+1 ,
i = 0, . . . , T0 and for every i: A0i ≤ A0i+1 . Let c00 = 0 and cT0 = ∞.
Fig. 2. Stopping regions in dependence of n
Fig. 3. Functions f0 (x), v010 (x) and stopping region D0
Theorem 6. Under Assumption 1 the following is true.
1. For any k ∈ {0, . . . , N }:
(a) functions vkN (x) are piecewise linear, continues, convex downward and
satisfy
N
(x) = Ak+1 x + Bjk+1 , x ∈ ck+1 , ck+1
vk+1 j j j+1
where
Ak+1
j = p∗ (1 + a)Aki−t + q ∗ (1 + b)Aki+m , Bjk+1 = p∗ Bi−t
k
+ q ∗ Bi+m
k
,
( ) ( )
cki−t cki+m cki−t+1 cki+m+1
ck+1
j = max ; , ck+1
j+1 = min ; ,
1+a 1+b 1+a 1+b
if ck+1
j ≤ ck+1
j+1 .
(b) Stopping region Dk contains not more then T0 intervals such that
c01 c0T0
0; , ;∞
(1 + b)k (1 + a)k
and
c0i−1 c0i
; , i = 2, . . . , T0
(1 + a)k (1 + b)k
and there exists a number k ∗ such that for any k ≥ k ∗ stopping region
c01 c0T
Dk = 0; ∪ ; ∞ .
(1 + b)k (1 + a)k
N
2. (a) v∞ (x) = A∞ x + B ∞ , where
min A0i ≤ A∞ ≤ max A0i , min Bi0 ≤ B ∞ ≤ max Bi0 ;
i=0,T0 i=0,T0 i=0,T0 i=0,T0
(b) D∞ = ∅.
The proof of the theorem is almost obvious, but large. That is why the paper
does not contain it.
References
1. Boyarchenko, S.I., Levandorskii, S.Z.: Non-Gaussian Merton-Black-Scholes Theory,
Advanced Series On Statistical Science and Applied Probability, vol. 9. World
Scientific, New Jersey, London, Singapore, Hong Kong (2011)
2. Chow, Y.S., Robbins, H., Siegmund, D.: Great Expectations: The Theory of Op-
timal Stopping. Houghton Mifflin Company, Boston (1977)
3. DeGroot, M.H.: Optimal Statistical Decisions. McGraw-Hill Company, New York
(1970)
4. Dynkin, E., Yushkevich, A.: Markov processes: theorems and problems. Plenum
Press (1969)
5. Elliott, R.J.: Stochastic Calculus and Applications. Springer (1982)
6. Ferguson, T.S.: Optimal stopping and applications (1992)
7. Follmer, H., Schied, A.: Stochastic Finance. An Introdaction in Discrete Time.
Walter de Gruyter, Berlin – New York (2004)
8. Jönsson, H., Kukush, A.G., Silvestrov, D.S.: Threshold structure of optimal stop-
ping strategies for american type option. I. Theory Probab. Math. Statist 71, 93–
103 (2005)
9. Jönsson, H., Kukush, A.G., Silvestrov, D.S.: Threshold structure of optimal stop-
ping strategies for american type option. II. Theory Probab. Math. Statist 72,
47–58 (2006)
10. Khametov, V.M., Shelemekh, E.A., Yasonov, E.V.: Minimax hedging of ameri-
can type option in incomplete market with finite horizon is an optimal stopping
problem. OP&PM Surveys Appl. Industr. Math. 20(2), 155–156 (2013)
11. Kukush, A.G., Silvestrov, D.S.: Optimal pricing of american type options with
descrete time. Theory Stoch. Proces. 10(1–2), 72–96 (2004)
12. Shiryaev, A.N.: Statistical sequential analysis. Optimal stopping rules. Nauka,
Moscow (1976)
13. Shiryaev, A.N.: Basics of stochastic financial mathematics, vol. 2. Fazis, Moscow
(1998)