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)