Solving Optimal Stopping Problem by Using Computer Algebra Systems

Abstract

The article deals with optimal stopping problem for arbitrary sequence of bounded random values ( nite 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 problem for geometric random walk and managed to nd 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
• random walk
• explicit solution

-

Introdution Optimal stopping problem arises in areas of statistics (sequential hypothesis testing), mathematical nance (American options, the change-point problem) and others elds (see [1{4,6{13]). In [2,4,6,7,12,13] the main results for problems with in nite horizon were obtained. In this paper we consider optimal stopping problem with nite horizon.

In [1] they suppose, that stopping region is separated from continuation region 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 nite horizon can be found (see also [3, 4, 12]).

In [8, 9] they suppose, that: i) a Markov process is observed; ii) reward functions are monotonic and convex downward. In this case su cient 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 equation (Theorem 3) and establish a criteria of optimality for a stopping moment (Theorems 4 and 5). Note that in literature we found only su cient conditions, under which value function satis es 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 boundary 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 nd explicit formulas for this problem. Also for geometric random 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 2 N+ { horizon; iii) TnN { set of stopping moments regarding the ltration (Fn)0 n N [12], with values in fn; : : : ; N g; iv) (fn; Fn)0 n N { sequence of bounded random variables (in mathematical nance { utility of an observer); v) L0( ; F0) { set of all P-a. s. bounded F0-measurable random variables [7, xA.7].

We will study the following problem

E[f ^N jF0] ! ess sup; 2T0N where E[ jF0] is a conditional expectation taken regarding to -algebra F0 (see de nition in [7], de nition 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 jF0].

2T0N De nition 1. A pair ; v0N 2 (T0N ; L0( ; F0)) is said to be a solution of the problem ( 1 ) if v0N = E[f ^N jF0] P-a. s. Stopping moment 2 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 2 f1; : : : ; N g we denote vnN , ess sup E[f ^N jFn]:

2TnN De nition 2 ([12]). vnN is called value function at a moment n.

We study value function properties below.

Theorem 1. Assume that supn2N jjfnjjL0( ;Fn) C. Then jvnN j

( 1 ) ( 2 ) jvnN j ess sup E(jf j jFn) 2TnN

P-a. s.

N N As f = P fi1f =ig, we have jf j P jfij1f =ig i=n i=n

Using previous preposition and (3) we obtain that jvnN j

Theorem 2. Under assumptions of Theorem 1 sequence (vnN ; Fn)0 n N is a supermartingale.

Proof. By de nition of vnN we observe P-a. s.

vnN , ess sup E[f jFn] 2TnN ess sup E[f jFn] = ess sup E(E[f jFn+1]jFn):

2TnN+1 2TnN+1

Using properties of essentual supremum for any n we obtain P-a. s.

vN n

E(ess sup E[f jFn+1]jFn) = E(vnN+1jFn): 2TnN+1

The proof is complete.

( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 )

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 satis es recurrent relations P-a. s.

vnN = max fn; E[vnN+1jFn] ; vnN jn=N = fN : Proof. Necessity. Let us derive that if (vnN ; Fn)0 n N is a sequence of value functions, then recurrent relations ( 6 ) are satis ed.

First we will prove that for any n 2 f0; : : : ; N g the following inequality is satis ed P-a. s. { random variable 1f =ngfn is Fn-measurable; { conditional expectation has a tower property. Due to the de nition and properties of essentual supremum [5] for any n 2 f0; : : : ; N g we can conclude that P-a. s. vnN = ess sup E 2TnN " ^N

X 1f =igfi Fn i=n

# ( " " ^N ess sup 1f =ngfn + 1f >ngE E X 2TnN+1 i=n+1 1f =igfi Fn+1 #

#) Fn = = 1f =ngfn + 1f >ng ess sup E [E [f ^N jFn+1] jFn] = 2TnN+1 " # = 1f =ngfn + 1f >ngE ess sup E [f ^N jFn+1] Fn = 2TnN+1 = 1f =ngfn + 1f >ngE vnN+1jFn : ( 8 ) by

Left part does not depend on a stopping moment

2 TnN to a right part of (8), we will obtain (7).

Let us derive that the following inequality is satis ed P-a. s.

2 TnN . If we apply ess sup

vN n

Due to the fact that random variable 1f =ngfn is Fn-measurable, de nitions of ess sup and vnN+1, tower property of conditional expectation we can conclude that P-a. s.

vnN = ess sup 1f =ngfn + 1f >ngE [E [f ^N jFn+1] jFn] 2TnN

( " ess sup 1f =ngfn + 1f >ngE ess sup E [f ^N jFn+1] Fn 2TnN 2TnN+1 #) = = ess sup 1f =ngfn + 1f >ngE vnN+1jFn 2TnN = max fn; E[vnN+1jFn] : (10)

Obviously, vnN jn=N = E[fNN jFN ] = fN P-a. s. Hence with ( 7 ) and (9) we obtain ( 6 ).

Su ciency. Proof of su ciency is well known and can be found in [2, 7, 13]. Remark 1. As we stated above, proof of su ciency in Theorem 3 is well known.

Note, that necessity is new.

Using Theorem 3 we obtain necessary and su cient conditions, under which a pair ; v0N 2 (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 de ne = min 0 n N : vnN = fn . Obliviously, vN = f P-a. s. Suppose the stopping moment is not an optimal stopping moment, i. e. there exists a stopping moment such that .

vN = vN + (M

M ) (A

A )

0 and from (12) we can conclude immediately

Due to the fact that A that

Let us apply conditional expectation E [ jFn] to (13). Thus we have P-a. s.

E vN jFn

E N jFn = E [f jFn] : As E vN jFn

E f N jFn from (14) for any

we obtain vN

Note that sequence f n g is a supermartingale with respect to the measure P (Theorem 2). Due to Doob-Meyer decomposition theorem for any n 2 N0 it follows that vnN = v0 + Mn

An; where Mn is a martingale with respect to the probability measure P, An is an increasing sequence. Obviously, vN = PN i=0 viN 1f =ig.

i=0 viN 1f =ig and vN = PN Hence with (11) we can conclude vN = v0 + M A and vN = v0 + M A P-a. s. From this two formulas we obtain (11) (12) (13) (14) (15) (16) E f N jFn

E f N jFn : Note, that (15) is a necessary and su cient condition of optimality for the stopping moment . The proof is complete.

Using theorems 3 and 4 we can derive another criterion of optimality for stopping moment 2 T0N .

Theorem 5. A pair if and only if: ; v0N

2 (T0N ; L0( ; F0)) is a solution of the problem ( 1 ) 1. sequence (vnN ; Fn)0 n ^N is a martingale in respect to measure P; 2. vnN jn= ^N = f ^N P-a. s.

Proof. Su ciency. Let (vnN ; Fn)0 n ^N be a martingale with respect to measure P and vnN jn= ^N = f ^N P-a. s. Hence with solution de nition we can conclude required equalities v0N = E vN ^N jF0 = E [f ^N jF0] :

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(1f =ngfn + 1f >ngE vnN+1jFn ) = 2TnN

= 1f =ngfn + 1f >ngE vnN+1jFn : (17) As vN = f , we have 1f =ngvnN = 1f =ngfn. By ( 6 ) and (17) we may nd vnN = max fn; E[vnN+1jFn]

E[vnN+1jFn] = E[ess sup E(f jFn+1)jFn]

2TnN+1 E[E(f jFn+1)jFn] = E[f jFn]: (18) Let us apply conditional expectation E[ jF0] to (18). Thus we have Moreover, v0N = ess sup E(f jF0) 2T0N ess sup E(f jFn) = vnN . So, we have

2TnN E[vnN jF0]

E[f jF0] = v0N : vN 0

E(vnN jF0): (19) (20)

So, from (19) and (20) it follows that (vnN ; Fn)0 n

respect to the measure P. ^N is a martingale with 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 satis es the recursive relation Sn+1 = Sn(1 + n+1), Snjn=0 = S0 P-a. s., where f ng0 n N is a sequence of jointly independent identically distributed random values taking values in the compact set of fa; bg, a; b 2 R1, where 1 < a < 0 < b < 1.

Let p = jajja+j b , q = 1 p . This means that random sequence fSng0 n N is a martingale with respect to the measure P and ntration (Fn)0 n N , where Fn = fS0; : : : ; Sng.

We can prove easily that vnN is a Markov random function. There exists Borel function vnN (x) such as vnN jx=Sn = vnN and it satis es the following formula vnN (x) = max(fn(x); vnN+1(x(1 + a))p + vnN+1(x(1 + b))q ): (21) De nition 3 ([12]). For any n 2 f0; : : : ; N g set Dn , is called stopping region at a moment n.

Example 1. Suppose that:

{ for any n 2 f0; : : : ; N g there is function fn(x) =

0 < 1; { 1 < a < 0 < b < 1; x 2 R+ : fn(x) = vnN (x) n(x

K)+, where K > 0,

Example 2. Suppose for any n 2 f0; : : : ; N g: fn(x) = >8 0; x 1; >< 1; 1 < x > 2; 2 < x >: 3; x > 3: 2; 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) = Ai0x+Bi0 be continues, where x 2 ci0; ci0+1 , i = 0; : : : ; T0 and for every i: Ai0 Ai0+1. Let c00 = 0 and cT0 = 1. Theorem 6. Under Assumption 1 the following is true. 1. For any k 2 f0; : : : ; N g:

satisfy (a) functions vkN (x) are piecewise linear, continues, convex downward and vkN+1(x) = Ak+1x + Bk+1; x 2 ck+1; cjk++11

j j j where and if cjk+1

cjk++11.

Ak+1 = p (1 + a)Aik t + q (1 + b)Aik+m; j Bk+1 = p Bk j i t + q Bik+m; ck+1 = max ( cik t ; ci+m

k j 1 + a 1 + b ) ; cjk++11 = min ( k k ci t+1 ; ci+m+1 1 + a 1 + b ) ; (b) Stopping region Dk contains not more then T0 intervals such that 0;

The proof of the theorem is almost obvious, but large. That is why the paper does not contain it. 9. Jonsson, H., Kukush, A.G., Silvestrov, D.S.: Threshold structure of optimal stopping 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 american type option in incomplete market with nite 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 nancial mathematics, vol. 2. Fazis, Moscow (1998)

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 Scienti c, New Jersey, London, Singapore, Hong Kong ( 2011 )

2. Chow , Y.S. , Robbins , H. , Siegmund , D. : Great Expectations: The Theory of Optimal Stopping . Houghton Mi in 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. Jonsson, H., Kukush , A.G. , Silvestrov , D.S.: Threshold structure of optimal stopping strategies for american type option . I. Theory Probab. Math. Statist 71 , 93 { 103 ( 2005 )