Journal of Computational Finance

Risk.net

Path-dependent American options

Etienne Chevalier, Vathana Ly Vath and Mohamed Mnif

  • In this paper, we investigate a path-dependent American option problem and provide an efficient and implementable numerical scheme for the solution of its associated path-dependent variational inequality.
  • We obtain the viscosity characterization of our value function and suggest a monotone, stable and consistent numerical scheme, the convergence of which is proven thanks to the uniqueness property.
  • We further enrich our study by providing and implementing a numerical algorithm. Some numerical results are also included.

In this paper, we investigate a path-dependent American option problem and provide an efficient and implementable numerical scheme for the solution of its associated path-dependent variational inequality.We obtain the viscosity characterization of our value function and suggest a monotone, stable and consistent numerical scheme, the convergence of which is proven thanks to the uniqueness property.We further enrich our study by providing and implementing a numerical algorithm. Some numerical results are also included.

1 Introduction

The purpose of this paper is to investigate path-dependent American option problems. It is mainly about providing, in a general framework, an efficient and implementable numerical scheme for the solution of associated path-dependent variational inequalities. To our knowledge, in the literature, only numerical procedures adapted to particular cases have been studied. Moreover, the convergence of numerical scheme solutions to such path-dependent American options has been only empirically illustrated. Dai and Kwok (2005) and Lai and Lim (2004) examine the early exercise policies and pricing behaviors of a single-asset American option with lookback payoff structures. They give the variational inequality satisfied by the path-dependent value function. Implicitly, they assume that Itô’s calculus and the dynamic programming principle hold as in the Markovian context. Hull and White (1993) show how binomial and trinomial tree methods can be extended to value many types of options with path-dependent payoffs. As an example, the authors determine, thanks to their discrete model, the price of a lookback put option, whose payoff is a function of the maximum stock price realized during the option’s life. Babs (2000) adapts the binomial scheme to investigate its impact on the value of these options.

In the current paper, to tackle our optimal stopping time problem, we derive the following associated path-dependent variational inequality (PDVI):

  min[u(t,ω)-h(t,ω);-tu(t,ω)-12Tr(σσ*ωω2u)(t,ω)-λ(t,ω)ωu(t,ω)-f(t,ω)]=0  

on [0,T)×Ω, where T is a given terminal time; ωΩ is a continuous path from [0,T] to d, starting from the origin; the diffusion coefficient σ is a mapping from [0,T]×Ω to d×d, with σ* denoting its transpose; and the drift coefficient λ is a mapping from [0,T]×Ω to d. The unknown process {u(t,w),t[0,T]} is required to be continuous in (t,ω).

The definition of the derivatives tu, ωu and ωω2u, which appear in the above PDVI, is based on Dupire (2009), where a functional Itô formula is proved. We no longer assume the smoothness of the value function, which is not realistic in our case. The derivatives should be interpreted in the viscosity sense, which was first introduced by Ekren et al (2014) and later by Ren et al (2015) for path-dependent, semi-linear partial differential equations (PDEs). It is a powerful tool for this type of problem, since the derivatives are interpreted in a weak sense. This theory is an extension of the viscosity solutions in finite dimensional spaces introduced by Crandall and Lions (1983). In the infinite-dimensional case, we lose the property of local compactness of and the stopping times play a key role. The set of tested processes is enlarged since we consider all of the smooth processes, which are tangent in mean and not point-wise as in the finite-dimensional case.

It is well known that the PDVI satisfied by the value function of an optimal stopping problem is related to the solution of a reflected backward stochastic differentiable equation (RBSDE). This will enable us to prove the viscosity and uniqueness properties by adapting the arguments used in Ren et al (2015) to our optimal stopping case. In particular, it is easier to obtain a comparison result in this instance than in the finite-dimensional case since the set of test processes is larger. We also note that the optimal stopping problem is a degenerate optimal control problem since our only choice is to either stop and receive the payoff or keep the system evolving. As a consequence, we do not need the nonlinear expectations to catch all of the possible controls; this makes our proofs less technical than those of Ekren (2017), who studied the viscosity solutions of obstacle problems for fully nonlinear, path-dependent PDEs.

Once the viscosity characterization has been obtained, our second step is to obtain an efficient and implementable numerical scheme for the path-dependent optimal stopping problem. The convergence of such a scheme is ensured by the above uniqueness result. It is an extension of the convergence theorem of Barles and Souganidis (1991). The main difficulty lies in the space Ω, which is no longer locally compact. Recently, the convergence of numerical schemes for path-dependent PDEs were studied by Zhang and Zhuo (2014) and Ren and Tan (2017). They imposed some conditions which were stronger than those of Barles and Souganidis (1991) to show the monotonicity of the numerical scheme. In this paper, we follow in the footsteps of Barles and Souganidis (1991) and propose a convergent numerical scheme to price an American fixed strike lookback option whose payoff is path-dependent. In his seminal paper, Zhang (2004) studied numerical schemes for RBSDEs, where the forward component was Markovian and the backward component was non-Markovian. He proved the convergence of the numerical scheme in the L2 sense. In our paper, we study the case of a path-dependent forward component: an RBSDE with a path-dependent terminal condition. Thanks to the viscosity approach, we prove almost surely the convergence of the numerical scheme to the unique viscosity solution of the PDVI.

The remainder of this paper is organized as follows. In Sections 2 and 3, we formulate the path-dependent optimal stopping problem and the associated PDVI. We characterize the value function of the optimal stopping problem as the unique viscosity solutions of the associated PDVI. In Section 4, we suggest a monotone, stable and consistent approximation scheme. We prove the convergence of the numerical scheme to the solution of the PDVI. In Section 5, we give a numerical algorithm that we implement to get some numerical results on lookback options. We choose to apply our method to lookback options in order to have benchmark values and to be able to compare our method with existing numerical procedures.

2 Path-dependent optimal stopping problem

Let T>0 be a given finite maturity. We consider Ω:={ω?([0,T];d):ω0=0} the set of continuous paths starting from the origin, and Θ:=[0,T]×Ω. We denote by B the canonical process on Ω; by ?={t, 0tT} the canonical filtration; by ? the set of all ?-stopping times taking values in [0,T]; and by the Wiener measure on Ω. To simplify our notation, for any 0tT and any function u defined on Θ, we will denote by u(t,B) the random variable defined on Ω by u(t,B)(ω):=u(t,ω).

We shall study a path-dependent optimal stopping problem for all 0tT,

  Vt=esssupτ?t,T?[tτf(s,ω)ds+g(T,ω)?{τ=T}+h(τ,ω)?{τ<T}|t],   (2.1)

where f, g and h satisfy the following Assumption (?f,g,h).

Assumption 2.1 (Assumption (?f,g,h)).

We assume that f,g,h:(t,ω)ΘR are bounded by a positive constant and Lipschitz, ie, they satisfy the two following assertions:

  1. (i)

    sup(t,ω)Θ|f(t,ω)|+|g(t,ω)|+|h(t,ω)|<+; and

  2. (ii)

    there exists C0 such that, for all t, t[0,T], ω, ωΩ,

      |f(t,ω)-f(t,ω)|+|h(t,ω)-h(t,ω)|+|g(t,ω)-g(t,ω)|Cd((t,ω),(t,ω)),  

    where, following Dupire (2009), we have introduced the pseudo-distance d() on Θ:

      d((t,ω),(t,ω)):=|t-t|+ωt-ωtT,   (2.2)

    for all (t,ω),(t,ω)Θ2, with ωt:=sup0st|ωs| for all t[0,T].

Example 2.2.

Assumption (?f,g,h) is satisfied in the following example. We assume that X=(Xt)t[0,T] satisfies

  dXt=Xt(rdt+σdBt),X0=x0>0,   (2.3)

where r>0, σ>0. We are interested in pricing an American lookback put option, ie,

  g(T,ω) =e-rT(K-min0sTXs(ω))+,  
  h(t,ω) =e-rt(K-min0stXs(ω))+,  
  f(t,ω) =0.  

Let 0ttT and (ω,ω)Ω2; then,

  |h(t,ω)-h(t,ω)||h(t,ω)-h(t,ωt)|+|h(t,ωt)-h(t,ω)|.  

From the definition of h and the solution of the stochastic differential equation (SDE) (2.3), we have

  Δ1 :=|e-rt(K-min0stXs(ω))+-e-rt(K-min0stXs(ωt))+|  
    =|e-rt(K-min0stx0exp{(r-12σ2)s+σωs})+  
      -e-rt(K-min0stx0exp{rs-12σ2st+σωst})+|.  

Since the minimum on [0,t] of the functions se(r-(σ2/2))s+σωs and sers-(σ2/2)st+σωst are reached at the same point s*[0,t], and using the boundedness of the function x(K-x)+, we obtain

  Δ1K|t-t|.   (2.4)

The Lipschitz-continuity property of the function x(K-x)+ implies

  Δ2 :=|h(t,ωt)-h(t,ω)|  
    =|e-rt(K-min0stx0exp{rs-12σ2st+σωst})+  
        -e-rt(K-min0stx0exp{rs-12σ2s+σωs})+|  
    x0e-rt|exp{min0st{rs-12σ2st+σωst}}  
            -exp{min0st{rs-12σ2s+σωs}}|.  

As min0st{rs-12σ2st+σωst}0 and 1-e-yy on , we get

  Δ2 x0max0stσ|ωs-σωst|+12σ2|st-s|  
    (K+x0)(|t-t|+ωt-ωtT).  

This shows that

  |h(t,ω)-h(t,ω)|(|t-t|+ωt-ωtT).  

Our study of the optimal stopping problem (2.1) begins with the following remark. For t[k0,T], we consider the following RBSDE:

  Yt=g(T,B)+tTf(s,B)ds-tTZsdBs+KT-Kt,Yth(t,B),}   (2.5)

where g and h, respectively, belong to ?2 and f2, defined by

  2 ={(φt)0tT?-predictable process such that ?[0T|φt|2dt]<+},  
  ?2 ={(φt)0tT?-predictable process such that ?[sup0tT|φt|2]<+}.  

From El Karoui et al (1997), this RBSDE admits a unique solution (Y,Z,K) such that Y?2, Z2 and K is a continuous, nondecreasing process such that K0=0 and

  0T(Ys-h(s,B))dKs=0almost surely.   (2.6)

It is also shown in El Karoui et al (1997) that we have Vt=YtdtdP almost everywhere, and this gives our optimal stopping problem its characterization as a solution of an RBSDE.

Remark 2.3.

El Karoui et al (1997) obtained a more general result. They proved that if f2 and g and h belong to ?2, then the RBSDE (2.5) admits a unique solution (Y,Z,K) such that Y?2, Z2 and K is a continuous, nondecreasing process such that K0=0.

In the next section, we link the process (Yt)t[0,T] to the viscosity solution of the associated PDVI.

3 Path-dependent variational inequality

In this section, we introduce the notion of viscosity solutions for PDVIs, and we characterize the value function of the optimal stopping problem (2.1) as the unique viscosity solution of an associated PDVI. It will be crucial to build a convergent numerical scheme in Section 4.

We introduce the following PDVI:

  min[u(t,ω)-h(t,ω);-u(t,ω)-f(t,ω)]=0,(t,ω)[0,T)×Ω,u(T,ω)=g(T,ω),ωΩ.}   (3.1)

The precise meaning of u(t,ω) is given later (see Definition 3.2). Our setting is very general and may be illustrated by the following example.

Example 3.1.

Consider the Itô process X defined on (Ω,,?) by

  dXt=λ(t,B)dt+σ(t,B)dBt,X0=x0d,   (3.2)

where λ(t,ω)Θλ(t,ω)d and σ(t,ω)Θσ(t,ω)d×d() are continuous in t and Lipschitz continuous in ω uniformly in t, ie, there exists C0 such that

  |λ(t,ω)-λ(t,ω)|+σ(t,ω)-σ(t,ω)Cω-ωt  

for all t[0,T], ω, ωΩ. We also assume that |λ(t,0)|+σ(t,0)C for all t[0,T]. From Rogers and Williams (2000), Theorem 13.1, p. 136, under these assumptions, (3.2) admits a unique strong solution.

We now consider the optimal stopping problem

  Vt=esssupτ?t,T?[tτf^(s,Xs)ds+g^(T,XT)?{τ=T}+h^(τ,Xτ)?{τ<T}|t],  

where f^, g^ and h^ are such that

  (f,g,h):(t,ω)(f^(t,Xt(ω)),g^(t,Xt(ω)),h^(t,Xt(ω)))  

satisfies Assumption (?f,g,h).

Equation (3.1) can be written with a path-dependent infinitesimal generator of X:

  u(t,ω)=tu(t,ω)+12Tr(σσ*ωω2u)(t,ω)+λ(t,ω)ωu(t,ω),   (3.3)

where the meaning of the derivatives with respect to ω is the same as that presented in Dupire (2009).

Our aim is to relate the value function of the optimal stopping time problem (2.1) to the PDVI (3.1) via the notion of viscosity solutions, and then to derive a convergent numerical scheme inspired by (3.1) and (3.3).

3.1 Viscosity solutions of the PDVI

We start by recalling some notions and the notation necessary for defining path-dependent viscosity solutions.

Continuous process on Θ:

a process, valued , is in ?0(Θ) whenever it is continuous with respect to the pseudo-distance d defined by (2.2).

Spaces of processes:

similarly, L0(t) and L0(?), respectively, denote the set of t-measurable random variables and ?-progressively measurable processes. We remark that a continuous process is ?-progressively measurable.

Sets of stopping times:

we shall denote by ? the set of ?-stopping times, and by the set of all bounded exit times of the Brownian motion.

A stopping time H belongs to if and only if there exist t0(0,T] and O an open set of containing 0 such that

  H=inf{t:BtO}t0.   (3.4)

As noted in Ekren et al (2014), Remark 3.11(i) and Zhang and Zhuo (2014), if, for ε>0, we set

  Hε:=inf{s>0:|Bs|ε}ε,  

we have {Hε:ε>0}, and for any H, HεH for a small enough ε.

This property will be very useful in the proof of the convergence of our numerical scheme (see Remark 3.5).

Shifted spaces and filtrations:

we equally introduce shifted spaces,

  Ωt={ω?([t,T],d):ωt=0}.   (3.5)

We denote by ?t the filtration generated by the canonical process Bt on Ωt. We also let Θt:=[t,T]×Ωt.

Shifted probability measures:

t is the Wiener measure on Ωt, and we shall denote by ?t the expectation under t.

Shifted processes:

let u?0(Θ), (t,ω)Θ. We define the shifted process u(t,ω) on Θt in the following way. For all (s,ω)Θt,

  u(t,ω)(s,ω):=u(s,ωtω)with (ωtω)r=ωr?{rt}+(ωt+ωr)?{r>t}.   (3.6)

Note that ωtω is the concatenation of the path ω up to time t and ω. As in the case of nonshifted processes, we will simplify our notation and consider that for any (t,ω)Θ the process ωtBt is the process defined on Θt by ωtBt(s,ω):=(ωtω)s. In the same way, we use u(t,B) to denote the random variable taking values in ?0(Θt) such that [u(t,B)](ω)=u(t,ω).

Shifted sets of stopping times:

we define ?t as the set of ?t-stopping times larger than t. We equally define t as the subset of ?t containing exit times from open sets larger than t and the following stopping times, defined for ε>0,

  Hεt:=inf{s>t:|Bst|ε}(t+ε).  

We will now define the sets of test processes. First, following Ren et al (2015), we define a ?1,2 process as follows.

Definition 3.2.

Let u:Θ. Here, u is said to belong to ?1,2 if processes Λ and Z:=(Zi)1id exist such that (Λ,Z)(?0(Θ))d+1 and

  du(t,B)=Λ(t,B)dt+Z(t,B)dBt almost surely.  

In this case, we use the following notation:

  u(t,ω):=Λ(t,ω)andωu(t,ω):=Z(t,ω).  
Remark 3.3.

Unlike Dupire (2009), who defined tu and ωωu separately, we do not need to distinguish between them to define u as in (3.3).

We introduce the test process sets and then the notion of a viscosity solution. Let u?0(Θ) and (t,ω)Θ. We set

  ?¯u(t,ω) ={φ?1,2:Ht:maxτ?t?t[(φ-u)τH(t,ω)]=(φ-u)(t,ω)=0},   (3.7)
  ?¯u(t,ω) ={φ?1,2:Ht:minτ?t?t[(φ-u)τH(t,ω)]=(φ-u)(t,ω)=0}.   (3.8)

Thanks to this notation, we may define the notion of a viscosity solution of the PDVI (3.1).

Definition 3.4.

Let u?0(Θ).

  1. (i)

    u is a viscosity subsolution of (3.1) if, for all (t,ω)[0,T)×Ω and for all ϕ?¯u(t,ω), we have

      min[-ϕ(t,ω)-f(t,ω);ϕ(t,ω)-h(t,ω)]0.   (3.9)
  2. (ii)

    u is a viscosity supersolution of (3.1) if, for all (t,ω)[0,T)×Ω and for all ϕ?¯u(t,ω), we have

      min[-ϕ(t,ω)-f(t,ω);ϕ(t,ω)-h(t,ω)]0.   (3.10)
  3. (iii)

    u is a viscosity solution of (3.1) if it is both a viscosity subsolution and a viscosity supersolution.

Remark 3.5.

We could define a more restrictive notion of a viscosity solution by enlarging our test process sets. Indeed, we could replace t by ?t in the definition of ?¯u(t,ω) and ?¯u(t,ω). All of the results obtained in this paper would remain true except Theorem 4.6, where the convergence of a numerical scheme to the value function is stated. It relies on the proof that the limit of the numerical scheme is a viscosity solution of the PDVI (3.1).

Following the standard theory of viscosity solutions for PDEs, we may also define viscosity solutions via semijets.

Definition 3.6 (Semijets).

For uC0(Θ), the subjet and superjet of u at (t,ω) are defined as:

  J¯u(t,ω):={φ?¯u(t,ω):(α,β)d+1,φ(t,ω)=αt+βωtonΘ},  
  J¯u(t,ω):={φ?¯u(t,ω):(α,β)d+1,φ(t,ω)=αt+βωtonΘ}.  

The following proposition – proved in the case of a path-dependent, semi-linear PDE (see Ren et al 2015) – gives an equivalent formulation for the definition of a viscosity solution. It shows that restricting the set of test processes to linear processes gives an equivalent formulation for viscosity solutions.

Proposition 3.7.

Let uC0(Θ). The following are equivalent. For any (t,ω)[0,T)×Ω,

  1. (i)

    u is a viscosity subsolution at (t,ω),

  2. (ii)
      min[-φ(t,ω)-f(t,ω);φ(t,ω)-h(t,ω)]0for all φJ¯u(t,ω),   (3.11)

    and

  3. (iii)
      min[-φ(t,ω)-f(t,ω);φ(t,ω)-h(t,ω)]0for all φcl(J¯u(t,ω)),  

    where cl denotes the closure in the class of linear processes.

Proof.
(i) implies (ii).

If u is a viscosity subsolution of the PDVI (3.1) at (t,ω), then by taking the test process φJ¯u(t,ω), the inequality (3.11) holds.

(ii) implies (iii).

We consider φcl(J¯u(t,ω)), where φ(t,ω)=αt+βωt; there exists a sequence φnJ¯u(t,ω), where φn(t,ω)=αnt+βnωt and (αn,βn)(α,β) when n goes to infinity. By (ii), we have

  min[-φn(t,ω)-f(t,ω);φn(t,ω)-h(t,ω)]0.  

Sending n, we obtain (iii).

(iii) implies (i).

Let (t,ω)[0,T)×Ω and ϕ?¯u(t,ω) with a localizing time Ht. Without loss of generality, we take (ϕ-u)(t,ω)=0. Define

  α:=ϕ(t,ω),β:=ωϕ(t,ω).   (3.12)

For any n>0, as ϕ is smooth, by otherwise choosing a smaller H, we may assume that

  |ϕt,ω(s,Bt)-α|1n,|ωϕt,ω(s,Bt)-β|1n,tsH.   (3.13)

Let αn:=α+(1/n), φ(t,ω)=αt+βωt and φn(t,ω):=αnt+βωt. Then, for all stopping times tτH,

  (φn-u)(t,ω)-?t[(φn-u)(t,ω)(τ,Bt)]  
    =?t[(u-ϕ)(t,ω)(τ,Bt)]+?t[(ϕ-φn)(t,ω)(τ,Bt)-(ϕ-φn)(t,ω)],  
    ?t[tτ(ϕs-αn)ds+(ωϕs-β)dBs],  

where the last inequality holds because ϕ?¯u(t,ω). Note that

  ?t[tτ(ϕs-αn)ds+(ωϕs-β)dBs]  
    =?t[tτ(ϕs-α)ds+(ωϕs-β)dBs-1n(τ-t)]  
    ?t[tτ1nds-1n(τ-t)]=0.  

We see that

  (φn-u)(t,ω)-?t[(φn-u)(t,ω)(τ,Bt)]0.  

That is, φnJ¯u(t,ω), and so φcl(J¯u(t,ω)). It follows from (iii) and (3.12) that

  min[-ϕ(t,ω)-f(t,ω);ϕ(t,ω)-h(t,ω)]0;  

with (3.12), we obtain (i).

Remark 3.8.

We obtain a similar characterization for viscosity supersolutions to that in Proposition 3.7. That is, u is a viscosity supersolution of the PDVI (3.1) at (t,ω) if and only if

  min[-ϕ(t,ω)-f(t,ω);ϕ(t,ω)-h(t,ω)]0for all ϕJ¯u(t,ω).   (3.14)

3.2 RBSDE and viscosity solution of PDVI

In this subsection, we will characterize the value function of the optimal stopping time problem (2.1) as a viscosity solution of the PDVI (3.1).

Theorem 3.9.

Let (Y0,Z0,K0) be the unique solution of the RBSDE (2.5). The process defined by u0(t,ω)=Yt0,t,ω on Θ is a viscosity solution of the PDVI (3.1).

The proof of Theorem 3.9 is divided into three lemmas. We begin with the continuity of u0 and then prove that it is both a subsolution and a supersolution to the PDVI (3.1).

Lemma 3.10 (Continuity).

Under Assumption (?f,g,h), we have u0C0(Θ).

Proof.

Let (t,ω) and (t,ω)Θ such that tt. We have

  |u0(t,ω)-u0(t,ω)| =|?t[Yt0,t,ω-Yt0,t,ω]|  
    =|?t[Yt0,t,ω-Yt0,t,ω+ttft,ω(s,Bt)ds  
        -ttZs0,t,ω(Bt)dBst+Kt0,t,ω-Kt0,t,ω]|  
    δ1+δ2+δ3,  

where we have set

  δ1 :=?t[|Yt0,t,ω-Yt0,t,ω|],  
  δ2 :=?t[|ttft,ω(s,Bst)ds|],  
  δ3 :=?t[|Kt0,t,ω-Kt0,t,ω|].  

Since the solution (Yt)0tT of the RBSDE is the value function of an optimal stopping time problem, we have

  Yt0,t,ω =supτ?t,T?t[tτft,ωtBt(s,Bt)ds+gt,ωtBt(T,Bt)?{τ=T}  
                  +ht,ωtBt(τ,Bt)?{τ<T}],  
  Yt0,t,ω =supτ?t,T?t[tτft,ω(s,Bt)ds+gt,ω(T,Bt)?{τ=T}  
                  +ht,ω(τ,Bt)?{τ<T}].  

Therefore, we get

  δ1 ?t[?t[tT|ft,ωtBt(s,Bt)-ft,ω(s,Bt)|ds  
        +|gt,ωtBt(T,Bt)-gt,ω(T,Bt)|  
        +supτ?t,T|ht,ωtBt(τ,Bt)-ht,ω(τ,Bt)|?{τ<T}]]  
    (T-t)?t[?t[sups[t,T]|f(s,ωtBttBt)-f(s,ωtBt)|]]  
      +?t[?t[|g(T,ωtBttBt)-g(T,ωtBt)|]]  
      +?t[?t[supτ?t,T|h(τ,ωtBttBt)-h(τ,ωtBt)|]].  

Using the Lipschitz property of f, g and h (see Assumption (?f,g,h)), we obtain

  δ1 C?t[?t[(ωtBttBt)-(ωtBt)T]  
      +supτ?t,T?t[(ωtBttBt)-(ωtBt)τ]],  

where C is a positive constant. From the definition of the concatenation operator, we have, for all 0sU, where U=τ or U=T,

  (ωtBttBt)s-(ωtBt)s  
        =(ωs-ωs)?st+(ωt+Bst-ωt)?t<st  
          +(ωt+Btt+Bst-ωt-Btt-Bst)?t<sU,  

which implies

  δ1C(d((t,ω),(t,ω))+?t[|Bt|tt]),   (3.15)

where |Bt|tt:=suptst|Bst|. As f is bounded, we obviously get δ2C(t-t).

From the continuity of the process tKt0,t,ω (see El Karoui et al 1997), and using the dominated convergence theorem, we deduce that, when d((t,ω),(t,ω)) goes to 0, δ3 goes to 0. This completes the proof. ∎

Lemma 3.11 (Subsolution).

The process u0 is a viscosity subsolution of the PDVI (3.1).

Proof.

Let (t,ω)θ such that t<T. We argue by contradiction and assume that there exists φ?¯u0(t,ω) such that

  0<C:=min[φ(t,ω)-h(t,ω);-φ(t,ω)-f(t,ω)].   (3.16)

Recall that (Y0,Z0,K0) is the unique solution of the RBSDE (2.5). For s[t,T), we set

  Ysδ:=Y~s-Ys0,t,ωandZsδ:=Z~s-Zs0,t,ω,  

where we have set Y~s=φt,ω(s,Bst) and Z~s=ωφt,ω(s,Bst). As φ?1,2, we get

  d(Ysδ) =[φt,ω(s,Bs.t)+ft,ω(s,Bst)]ds+ωφt,ω(s,Bst)dBst  
                      -Zs0,t,ωdBst+dKs0,t,ω  
    =[φt,ω(s,Bst)+ft,ω(s,Bst)]ds+ZsδdBst+dKs0,t,ω.   (3.17)

We introduce the following stopping times:

  τt1 =inf{s>t:φt,ω(s,Bst)+ft,ω(s,Bst)-12C}T,  
  τt2 =inf{s>t:(φ-h)t,ω(s,Bst)12C}T,  
  τt =τt1τt2.  

As we have

  0=φ(t,ω)-u0(t,ω)=φt,ω(t,Btt)-Yt0,t,ω=Ytδ,   (3.18)

we obtain

  Yt0,t,ω-ht,ω(t,Btt)=Yt0,t,ω-φt,ω(t,Btt)+(φ-h)t,ω(t,Btt)C>0.  

Moreover, if we set H:=inf{st:YsδC4}τt1, it follows from the continuity of φt,ω(s,) and Ysδ on Ωt, for all s[t,T), that

  Ys0,t,ω-ht,ω(s,Bst)=φt,ω(s,Bst)-ht,ω(s,Bst)-Ysδ14Cfor all s[t,H].  

Hence, the stopping time t<Hτt almost surely is such that

  Ys0,t,ω>ht,ω(s,Bst)for all s[t,H],t almost surely.   (3.19)

The last equation together with (2.6) implies

  Ks0=Kt0for all s[t,H],t almost surely.   (3.20)

Integrating (3.17) between t and H, and using (3.19)–(3.20), we get

  0 =Ytδ  
    =YHδ-tHφt,ω(s,Bst)+ft,ω(s,Bst)ds+tHZsδdBs.  

Therefore, taking the expectation with respect to t, we get

  0 =?t[YHδ-tHφt,ω(s,Bst)+ft,ω(s,Bst)ds+tHZsδdBs]  
    =?t[(φ-u0)(t,ω)(H,BHt)]-Et[tHφt,ω(s,Bst)+ft,ω(s,Bst)ds]  
    ?t[(φ-u0)(t,ω)(H,BHt)]+12C?t[H-t].  

From the definition of the test processes ?¯(t,ω), we get

  0 =minτ?t?t[(φ-u0)(t,ω)(τH,BτHt)]  
    ?t[(φ-u0)(t,ω)(H,BHt)]  
    -12C?t[H-t]<0,  

which is false and so inequality (3.16) does not hold and the viscosity subsolution property is then proved. ∎

Lemma 3.12 (Supersolution).

The process u0 is a viscosity supersolution of the PDVI (3.1).

Proof.

By contradiction, we assume that there exists (t,ω)[0,T)×Ω and φ?¯u0(t,ω) such that

  0>-C:=min[φ(t,ω)-h(t,ω);-φ(t,ω)-f(t,ω)].   (3.21)

First, we note that we have

  φ(t,ω)=u0(t,ω)=Yt0,t,ωh(t,ω).  

Therefore, we get

  0>-C=-φ(t,ω)-f(t,ω).   (3.22)

For s[t,T), we consider, as in the previous proof of Lemma 3.11, the processes Yδ and Zδ. We define the following stopping time:

  τt=inf{s>t:-φt,ω(s,Bst)-ft,ω(s,Bst)-12C}T.  

From the continuity of φ and f, and inequality (3.21), we have τt>t t almost surely.

Following similar arguments than in the proof of Lemma 3.11, we may get Itô’s decomposition of Yδ and integrate between t and τt to get

  Yτtδ=tτtφt,ω(s,Bst)+ft,ω(s,Bst)ds-tτtZsδdBst+Kτt0,t,ω-Kt0,t,ω.  

As K0 is nondecreasing, by taking the expectation with respect to t, we obtain

  ?t[(φ-u0)(t,ω)(τt,Bτtt)]12C?t[τt-t].  

Therefore we finally obtain the following contradiction

  0 =maxτ?t?t[(φ-u0)(t,ω)(τH,BτHt)]  
    ?t[(φ-u0)(t,ω)(τt,Bτtt)]12C?t[τt-t]>0,  

where H is a positive stopping time. This shows that inequality (3.22) does not hold and so the viscosity supersolution is proved. ∎

3.3 Comparison principle

In this section, we prove a comparison theorem. We give an equivalent formulation for viscosity subsolutions and viscosity supersolutions by using the notion of regular submartingales and supermartingales. We start by recalling the following definition.

Definition 3.13.

Let u?0(Θ), uniformly bounded in (t,ω). The process u is said to be a regular submartingale (respectively, supermartingale) if, for all (t,ω)Θ and a stopping time H such that H>t, we have

  ?t[ut,ω(H,Bt)]u(t,ω)(respectively, ?t[ut,ω(H,Bt)]u(t,ω)).  
Proposition 3.14 (Supersolution characterization).

Let uC0(Θ), uniformly bounded in (t,ω). The process u is a viscosity supersolution of the PDVI (3.1) if and only if uh on Θ and the process u^, defined on Θ by

  u^(t,ω)=u(t,ω)+0tf(s,ω)ds,  

is a regular supermartingale.

Proof.

We first assume that u is a viscosity supersolution of (3.1). Then, for ε>0 and (t,ω)Θ we set

  u^ε(t,ω)=u^(t,ω)-εt.  

We just have to prove that u^ε is a regular supermartingale. Indeed, we already have uh on Θ and, in that case, for any stopping time Ht, we would have

  ?t[u^t,ω(H,Bt)]-ε?t[H-t]u^(t,ω),  

and we would obtain the result by letting ε go to 0.

We argue by contradiction and assume that there exist (t,ω)Θ and a stopping time H such that Ht with a positive probability and

  ?t[u^ε,t,ω(H,Bt)]>u^ε(t,ω).  

Note that this implies t(H>t)=1. We define the so-called Snell envelope ? of the process (-u^ε,t,ω(sH,Bt))tsT by

  ?s:=esssupν?s,T?s[-u^ε,t,ω(νH,Bt)].  

From the optimal stopping theory (see El Karoui 1981), we deduce that if we set

  ν*:=inf{st:?s=-u^ε,t,ω(sH,Bt)}T,  

then ν* is an optimal stopping time, ie, we have ?t=?t[-u^ε,t,ω(ν*H,Bt)]. It follows that t(-u^ε,t,ω(ν*,Bt)=?ν*)=1 and

  -?t[u^ε,t,ω(H,Bt)]<-u^ε(t,ω)?t=-?t[u^ε,t,ω(ν*H,Bt)].  

Therefore, we obtain t(ν*<H)>0. Hence, there exists ω*Ω such that t*:=ν*(ω*)<H(ω*). For any stopping time νt*, we then have

  u^ε,t,ω(t*,ω*)=-?t*(ω*)-?t*[?νH]?t*[u^ε,t,ω(νH,Bt*)].  

Hence, we have shown that 0?¯u^ε(t*,ω*) because we have

  0-u^ε,t,ω(t*,ω*)=maxν?t*,T?t*[0-u^ε,t,ω(νH,Bt)].   (3.23)

From the definition of u^ε, we have

  u(t,ω)=u^ε(t,ω)+εt-0tf(s,ω)ds.  

So, if we set φ(t,ω):=εt-0tf(s,ω)ds on Θ, then it follows from (3.23) that

  φ(t*,ω*)-u(t*,ω*)=maxν?t*,T?t*[(φt,ω-ut,ω)(νH,Bt)].   (3.24)

As u is a viscosity supersolution of (3.1), we have that

  -φ(t*,ω*)-f(t*,ω*)0.   (3.25)

As φ(t*,ω*)=ε-f(t*,ω*), we obtain the following contradiction: ε0.

We now assume that u^ is a regular supermartingale and prove that u is a viscosity supersolution. Let (t,ω)[0,T)×Ω and φ?¯u(t,ω). There exists a stopping time H>t such that, for any ν?t,T,

  (φ-u)(t,ω)?t[(φ-u)t,ω(νH,Bt)]?t[(φ-u)t,ω(νH,Bt)].   (3.26)

Let ε>0. We define the following stopping time:

  Hε(ω):=H(ω)inf{st:|ωs|ε}for all ωΩ.  

From the supermartingale property of u^, and then from (3.26) and Itô’s decomposition of φ, we deduce that

  0 u^(t,ω)-?t[u^t,ω(Hε,Bt)]  
    u(t,ω)-?t[ut,ω(Hε,Bt)+tHεft,ω(s,Bt)ds]  
    φ(t,ω)-?t[φt,ω(Hε,Bt)+tHεft,ω(s,Bt)ds]  
    =-?t[tHεφt,ω(s,Bt)+ft,ω(s,Bt)ds].  

Letting ε go to 0, we obtain -φ(t,ω)-f(t,ω)0. ∎

Proposition 3.15 (Subsolution characterization).

Let uC0(Θ), uniformly bounded in (t,ω). If the process u is a viscosity subsolution of the PDVI (3.1), then the process u¯, defined by

  u¯(t,ω)=u(tτ*,ω)+0tτ*f(s,ω)dswith τ*=inf{s0:u(s,ω)=h(s,ω)},   (3.27)

is a regular submartingale.

Proof.

We first assume that u is a viscosity subsolution of the PDVI (3.1), and for ε>0 and (t,ω)Θ we set

  u¯ε(t,ω)=u¯(t,ω)+εt.  

We just have to prove that u¯ε(t,ω) is a regular submartingale. Indeed, in that case, for any stopping time Ht, we would have

  ?t[u¯t,ω(H,Bt)]+ε?t[H-t]u¯(t,ω),  

and we would obtain the result by letting ε go to 0.

We argue by contradiction and assume that there exist (t,ω)Θ and a stopping time Ht such that

  ?t[u¯ε,t,ω(H,Bt)]<u¯ε(t,ω).  

We define the so-called upper Snell envelope ? of the process

  (u¯ε,t,ω(sH,Bt))tsT  

by

  ?s=esssupν?s,T?s[u¯ε,t,ω(νH,Bt)].  

From the optimal stopping theory (see El Karoui 1981), we deduce that if we set

  ν*:=inf{st:?s=u¯ε,t,ω(sH,Bt)}T,  

then ν* is an optimal stopping time, ie, we have ?t=?t[u¯ε,t,ω(ν*H,Bt)]. Therefore, we obtain

  ?t[u¯ε,t,ω(H,Bt)]<u¯ε(t,ω)?t=?t[u¯ε,t,ω(ν*H,Bt)],  

and it follows that (ν*<H)>0. Hence, there exists ω*Ω such that t*:=ν*(ω*)<H. For any stopping time νt*, as ? is a regular supermartingale (see Ren et al 2015; Ekren et al 2014), we then have

  u¯ε,t,ω(t*,ω*)=?t*(ω*)?t*[?νH]?t*[u¯ε,t,ω(νH,Bt)].  

We have then shown that 0?¯u¯(t*,ω*) because we have

  0-u¯ε,t,ω(t*,ω*)=minν?t*,T?t*[0-u¯ε,t,ω(νH,Bt)].  

As u¯ε is a viscosity subsolution of

  -φ(t,ω)+ε=0,   (3.28)

it leads to ϵ0, which is a contradiction. ∎

Theorem 3.16 (Comparison).

Let u (respectively, v) be a viscosity subsolution (respectively, supersolution) of the PDVI (3.1) such that uTvT. For all (t,ω)Θ, we have

  u(t,ω)v(t,ω).  
Proof.

Let (t,ω)Θ. Assume that u(t,ω)<h(t,ω); as v is a viscosity supersolution, we obviously have u(t,ω)<h(t,ω)v(t,ω).

Now, assume that u(t,ω)h(t,ω) and introduce the following stopping time:

  τt*:=inf{st:ut,ω(s,Bt)=ht,ω(s,Bt)}.  

We shall use notation introduced in Propositions 3.14 and 3.15. From these propositions, we deduce that, on {tτ*},

  u(t,ω) =u¯(t,ω)-0tf(s,ω)ds  
    ?t[u¯t,ω(T,Bt)]-0tf(s,ω)ds  
    =?t[ut,ω(T,Bt)?{τt*T}+ht,ω(τt*,Bt)?{τt*<T}+tTτt*ft,ω(s,Bt)ds]  
    ?t[vt,ω(T,Bt)?{τt*T}+vt,ω(τt*,Bt)?{τt*<T}+tTτt*ft,ω(s,Bt)ds]  
    =?t[v^t,ω(Tτt*,Bt)]-0tf(s,ω)ds  
    v^(t,ω)-0tf(s,ω)ds  
    =v(t,ω).  

By combining the previous results, we finally obtain the following characterization.

Corollary 3.17 (Uniqueness).

Let u1 and u2 denote two viscosity solutions of the PDVI (3.1) such that u1(T,)=u2(T,). We have

  u1(t,ω)=u2(t,ω)for all (t,ω)Θ.  

4 Approximation scheme and numerical algorithm

In this section, we introduce a numerical scheme that approximates the PDVI continuous operator, defined in (3.3), using a discrete one. This discrete operator is meant to converge toward the continuous operator as the discretization step goes to zero.

4.1 Approximation scheme

For a time step η>0 on the interval [0,T], let us consider the following approximation scheme:

  Sη(t,ω,vη(t,ω),vη)=0,(t,ω)[0,T]×Ω,   (4.1)

where Sη is defined by

  Sη(t,ω,Ψ,Φ):={min{Ψ(t,ω)-?t[Φt,ω(t+η,Bt)]-f(t,ω),[Ψ-h](t,ω)},t[0,T-η],(t,ω),t=(T-η,T],   (4.2)

for any (Ψ,Φ)×?0(Θ).

We define the following time-dependent discrete grid on [t,T]:

  ?t,T,η:={t+kη:k{0,,n}, where nη<T-t(n+1)η}{T},   (4.3)

and ?t,T,η is the set of stopping times taking values in ?t,T,η.

From the definition of the numerical scheme (4.1) and the Snell envelope properties, we have

  vη(t,ω) =supτ?t,T,η?t,ω[k=0(τ-t)/ηf(t+kη,ωtBt)  
          +h(τ,ωtBt)?{τT-η}+g(τ,ωtBt)?{τ>T-η}].   (4.4)

We will show that the numerical scheme (4.1) is monotone, consistent and stable. These results will lead to the main result of this section, Theorem (4.6), which states the convergence of the numerical scheme to the unique viscosity solution of the PDVI (3.1).

Proposition 4.1 (Monotonicity).

For all (t,ω)Θ, ΨR and Φ1,Φ2C0(Θt) such that Et[Φ1-Φ2]0, we have

  Sη(t,ω,Ψ,Φ1)Sη(t,ω,Ψ,Φ2).  
Proof.

This follows directly from Definition 4.2 of the scheme. ∎

Because of the definition of an equivalent formulation for viscosity solutions stated in Proposition 3.7, it is enough to know the consistency of the numerical scheme (4.1) for linear processes. This result, stated in the following proposition, directly follows from the continuity of f, g and h stated in Assumption (?f,g,h).

Proposition 4.2 (Consistency).

For all (t,ω)[0,T)×Ω and ϕ, a linear process, ie, ϕ(t,ω)=αt+βωt on Θ, where αR and βRd, we have

  lim(t,ω)(t,ω)min{ϕ(t,ω)-?t[ϕ(t,ω)(t+u,Bt)]u-f(t,ω);(ϕ-h)(t,ω)}  
    =min{-ϕ(t,ω)-f(t,ω),(ϕ-h)(t,ω)},  

for any 0<u<T-t.

Proof.

As φ is linear, we have

  dϕ(t,ω)=αdt+βdBt=ϕ(t,ω)dt+ωϕ(t,ω)dBt.  

The unicity of Itô’s decomposition implies that ϕ(t,ω)=α. However, for 0<u<T-t and t close enough to t, we have

  ϕ(t,ω)-?t[ϕ(t,ω)(t+u,Bt)]u=α.  

We may conclude the proof thanks to the continuity of f and h. ∎

Before proving the stability of our numerical scheme, we need to define a time monotonicity on stopped paths and assume the solutions of our scheme have this monotonicity property.

Definition 4.3 (Time monotonicity on stopped paths).

A process φ defined on Θ is nonincreasing in time on stopped paths if

  φ(t,ω)φ(t,ωt)for all tt,ωΩ.  
Example 4.4 (Value functions nonincreasing in time on stopped paths).
Markovian setting:

in a Markovian and time-homogeneous setting, we have

  v(t,ωt)v(t,ωt)when tt and ωΩ.  

This is a direct consequence of the fact that ?t,T?t,T.

Lookback option:

assume that X is a geometric Brownian motion and set

  f(t,ω)=0,  
  g(t,ω)=h(t,ω)=e-rt(K-min0stXs(ω))+for all (t,ω)Θ.  

From the definition of the numerical scheme (4.4), we have

  vη(t,ω)=supτ?t,T,η?t[h(τ,ωtBt)].  

From the definition of the payoff h, it follows that

  vη(t,ω)=supτ-t?0,T-t,η?t[e-r(τ-t)(K-mintτTXt exp{(r-12σ2)(τ-t)  
        +σ(Bτ-Bt)})+].  

Similarly, we have

  vη(t,ωt)  
  =supτ-t?0,T-t,η?t[e-r(τ-t)(K-mintτTXter(t-t)exp{(r-12σ2)(τ-t)  
                        +σ(Bτ-Bt)})+].  

Since ?0,T-t,η?0,T-t,η and er(t-t)1, we deduce that vη(t,ω)vη(t,ωt).

Proposition 4.5 (Stability).

There exists a unique solution vη to

  ?η(t,ω,vη(t,ω),vη)=0for all (t,ω)Θ.   (4.5)

Moreover, if vη is nonincreasing in time on stopped paths for any η>0, then (vη)η>0 is uniformly bounded in (t,ω) and uniformly continuous in (t,ω) uniformly in η.

Proof.

Let (t,ω) and (t,ω) in Θ such that t<t.

First step. From the Lipschitz property of f, g and h (see Assumption (?f,g,h)) and the definition of the numerical scheme (see (4.4)), we have

  |vη(t,ω)-vη(t,ωt)|C(?t[sup0sT|(ωtBt)s-(ωttBt)s|]).  

From the definition of the concatenated operator (see (3.6)), we have

  (ωtBt)s-(ωttBt)s=(ωs-ωs)?st+(ωs-ωt)?t<st+(ωt-ωt)?t<s,  

which implies

  |vη(t,ω)-vη(t,ωt)|Csup0sT|ωst-ωst|.   (4.6)

Second step. Assuming that vη is nonincreasing in time on stopped paths, we have

  0vη(t,ω)-vη(t,ωt).   (4.7)

From the definition of (4.4), we derive the dynamic programming principle for all ν? taking values in [t,T]:

  vη(t,ω) =supτ?t,T,η?t[k=0[(τ-t)(ν-t)]/ηf(t+kη,ωtBt)  
          +h(τ,(ωtBt)τ)?{τ<ν}?{νT-η}  
          +vη(ν,ωtBt)?{τν}?{T-ην}+vη(ν,ωtBt)?{ν>T-η}],  

which, for any t[t,T], leads to

  vη(t,ω) supτ?t,t,T,η?t[k=0[(τ-t)(ν-t)]/ηf(t+kη,ωtBt)  
          +h(τ,(ωtBt)τ)?{τ<ν}?{νT-η}  
          +vη(ν,ωtBt)?{τν}?{T-ην}+vη(ν,ωtBt)?{ν>T-η}],   (4.8)

where ?t,t,T,η=?t,T,η{t}. In particular, the inequality (4.8) holds for ν=t. From (4.7) and (4.8), we deduce that

  0 vη(t,ω)-vη(t,ωt)  
    supτ?t,t,T,η?t[k=0[(τ-t)(t-t)]/ηf(t+kη,ωtBt)  
          +(h(τ,(ωtBt)τ)-h(t,ωt))?{τ<t}?{tT-η}  
          +(h(t,ωt)-vη(t,ωt))?{τ<t}?{tT-η}  
          +(vη(t,ωtBt)-vη(t,ωt))?{τt}?{t(T-η)}  
              +(vη(t,ωtBt)-vη(t,ωt))?{t>T-η}].   (4.9)

From the Lipschitz property of the function h and the Doob inequality, we get

  ?t[|h(τ,ωtBt)-(h(t,ωt)|?{τ<t}]Ct-t.   (4.10)

Repeating the same argument as in inequality (4.6), from the definition of the concatenation operator, we have

  (ωtBttBt)s-(ωttBt)s  
    =(ωs-ωs)?st+(ωt+Bst-ωt)?t<st  
        +(ωt+Btt+Bst-ωt-Bst)?s>t=Bst?t<st+Btt?s>t.  

Since the increments of the Brownian motion are independent, and using the Doob inequality, we obtain

  |vη(t,ωtB)-vη(t,ωt)|Ct-t.   (4.11)

Plugging (4.10) and (4.11) into (4.9), using the boundedness of the functional f, and since h(t,ωt)vη(t,ωt), we obtain, for |t-t|1,

  vη(t,ω)-vη(t,ωt)Ct-t.   (4.12)

From the inequalities (4.6) and (4.12), we deduce

  |vη(t,ω)-vη(t,ω)|C(t-t+sup0sT|ωst-ωst|).  

This shows that vη is uniformly continuous in (t,ω) uniformly in η. The uniform boundedness of vη is a direct consequence from the uniform boundedness of f, g and h. ∎

Thanks to the monotonicity, the consistency and the stability of the numerical scheme (4.1), one can prove the convergence of the solution of the numerical scheme (4.1) to the unique viscosity solution of the PDVI (3.1) as in Barles and Souganidis (1991). In the proof, we adopt some arguments of Zhang and Zhuo (2014). In our case, the linear expectation is sufficient to catch all of the controls. This makes our proof less technical.

Theorem 4.6 (Convergence).

The solution vη of the numerical scheme (4.5) converges dtdP almost everywhere to the unique continuous viscosity solution of the PDVI (3.1) as η goes to 0.

Proof.

Let v¯ and v¯ be defined as

  v¯(t,ω)=lim supη0vη(t,ω)andv¯(t,ω)=lim infη0vη(t,ω).   (4.13)

We obviously have vη(T,ω)=g(T,ω) on Ω; therefore, we have

  v¯(T,ω)=g(T,ω)=v¯(T,ω)for any ωΩ.  

The functions v¯ and v¯ inherit the uniform modulus of continuity of vη. Assume that we are able to prove that v¯ (respectively, v¯) is a viscosity subsolution (respectively, supersolution) of the PDVI (3.1). Then, from the comparison principle stated in Theorem 3.16, we may get

  v¯(t,ω)v¯(t,ω)on Θ.   (4.14)

By the definition of v¯ and v¯, we obviously have v¯=v¯ on Θ. We thus conclude the proof of the theorem.

We now have to prove that v¯ (respectively, v¯) is a viscosity subsolution (respectively, supersolution) of the PDVI (3.1). We start by studying v¯.

We prove the result by contradiction and assume that there exist (t,ω)Θ, φ?¯v¯(t,ω) such that

  min[[φ-h](t,ω);-φ(t,ω)-f(t,ω)]:=-c0<0.  

First case: assume that [φ-h](t,ω)=-c0.

From the definition of vη in Proposition 4.5, we obviously get that [vη-h](t,ω)0; therefore, we have

  -c0=[φ-vη](t,ω)+[vη-h](t,ω)[φ-vη](t,ω).  

For η going to 0, we obtain the following contradiction:

  0=[φ-v¯](t,ω)-c0.  

Second case: assume that -φ(t,ω)-f(t,ω)=-c0.

We define φ~ by φ~(t,ω)=φ(t,ω)-12c0(t-t) on Θt. We obviously have -φ~(t,ω)-f(t,ω)=-12c0, and so

  min[[φ~-h](t,ω);-φ~(t,ω)-f(t,ω)]<0.  

Let η>0 and define the two following processes:

  X:=φ~-v¯andXη:=φ~-vη.   (4.15)

Let ε>0 and set

  Hεt=inf{st:|Bst|ε}(t+ε).   (4.16)

As Hεtt and φ?¯v¯(t,ω), we have

  Xt(ω)-?t[XHεt(ωtBt)]  
      :=[φ-v¯](t,ω)-?t[(φ-v¯)(t,ω)(Hεt,Bt)-12c0Hεt(ωtBt)]  
    c02?t[Hεt(ωtBt)].   (4.17)

From Doob’s maximal inequality, for sε, we have

  (Hεtt+s)=(max0us|Bt+ut|ε)4(Bt+stε)4e-ε2/2s.  

Using Markov’s inequality, we deduce for small enough ε that

  ?t[Hεt(ωtBt)]ε3(Hεtε3)=ε3(1-4e-1/2ε)15ε3.  

Therefore, from the inequality (4.17), we deduce that

  Xt(ω)-?t[XHεt(ωtBt)]cε:=110c0ε3>0.   (4.18)

Let (hk)k0 such that limk+vhk(t,ω)=v¯(t,ω), and use the following notation: vk:=vhk and Xk:=Xhk.

From the inequality (4.18), we have

  cε [φ-lim infη0vη](t,ω)-?t[(φ-lim infη0vη)(t,ω)(Hεt,Bt)]  
    [φ-limkvk](t,ω)-?t[(φ-lim infkvk)(t,ω)(Hεt,Bt)].  

By Fatou’s lemma, we deduce

  cε limk+[φ-vk](t,ω)-lim supk+?t[(φ-vk)(t,ω)(Hεt,Bt)]  
    =lim infk+(Xtk(ω)-?t[XHεtk(ωtBt)]).  

Then, for all small enough ε and large enough k,

  Xtk(ω)-?t[XHεtk(ωtBt)]12cε>0.  

We now define, for each k,

  Ytk(ω):=supτ?t?t[XτHεtk(ωtBt)],   (4.19)

and we introduce the following optimal stopping time:

  τk,εt:=inf{st:Ysk=Xsk}.  

We obviously have tτk,εtHεt and thus

  0<cε2 Xtk(ω)-?t[XHεtk(ωtBt)]  
    Ytk(ω)-?t[XHεtk(ωtBt)]  
    =?t[Xτk,εtk(ωtBt)]-?t[XHεtk(ωtBt)].  

Therefore, there exists ωk,εΩt such that tt*k,ε:=τk,εt(ωtωk,ε)<Hεk, where Hεk=Hεt*k,ε,ωk,ε. Letting ε go to 0, we then have Hεt going to 0, and therefore

  d((t,ω),(t*k,ε,ωtωk,ε))0.   (4.20)

From the definition of the optimal stopping problem (4.19), for any τ?t, we have

  Xt*k,εk(ωtωk,ε)=Yt*k,εk(ωtωk,ε)?t*k,ε[XτHεkk(ωtωk,εt*k,εBt*k,ε)].  

It follows from the definition of Xk that

  -ξk,ε:=(φ-vk)(t*k,ε,ωtωk,ε)?t*k,ε[(φ-vk)(t*k,ε,ωtωk,ε)(Hεk,Bt*k,ε)],  

and so

  ?t*k,ε[(vk)(t*k,ε,ωtωk,ε)(Hεk,Bt*k,ε)]?t*k,ε[φ(t*k,ε,ωtωk,ε)(Hεk,Bt*k,ε)]+ξk,ε.  

From the monotonicity property, established in Proposition (4.1), we deduce that

  0 =?k(t*k,ε,ωtωk,ε,vk(t*k,ε,ωtωk,ε),vk)  
    ?k(t*k,ε,ωtωk,ε,φ(t*k,ε,ωtωk,ε)+ξk,ε,φ+ξk,ε).  

Letting k go to infinity and ε go to 0, using (4.20) and applying the result of consistency (see Proposition 4.2), we get

  0 limk,ε0?k(t*k,ε,ωtωk,ε,φ(t*k,ε,ωtωk,ε)+ξk,ε,φ+ξk,ε)  
    min{-ϕ(t,ω)-f(t,ω),(ϕ-h)(t,ω)}  
    =-c0<0,  

which is false. ∎

5 Implementation and numerical tests

In this section, we are interested in implementing our numerical scheme. Our only aim is to empirically study its convergence. We leave a numerical analysis of the fully implementable algorithm to further research.

5.1 The algorithm based on price-process computation

We assume that the process X=(Xt)t[0,T] evolves according to the Black–Scholes process, ie, Xt=X0exp{(r-12σ2)t+σBt}, where X0 is the initial security price, r is the risk-free rate of return and σ is the standard deviation of the security’s return. We use a path-dependent algorithm to price an American lookback put option, ie,

  g(X(ω))=(K-min0sTXs(ω))+andh(Xt(ω))=(K-min0sTXts(ω))+.  

Let π:t0=0<t1<<tN=T be a regular partition of the time interval [0,T]. We approximate by a regression method the solution of the associated PDVI. We replace the conditional expectations at time tn, which appear in the numerical scheme, by L2(Ω,P) projections on the function basis approximating L2(Ω,tn). We compute vη(tn,Xtn.) in an explicit manner. For n=N, vη(tN,X(ω))=g(X(ω)), while for n<N,

  vη(tn,Xtn(ω))=max{e-r(tn+1-tn)?tn[vη(tn+1,X(wtnBtn))],h(tn,Xtn(ω))}.   (5.1)

5.1.1 Vector spaces of functions

At every tn, we select a deterministic functions basis (pn()), which is considered as a vector of functions of dimension Ln, and we look for approximations of ?tn[vη(tn+1,X(ωtnBtn))], which will be denoted by Vtnη(Xtn) in Pn(Xtn), the vector space spanned by the basis pn(Xtn).

In other words, Pn(Xtn)={αpn(Xtn),αLn}. As an example, we cite the basis hypercube (??) used in Gobet et al (2005). A domain D centered on X0=x, that is, D=(x-a,x+a], can be partitioned on small intervals of edge δ. Then, D=iDi, where Di=(x-a+iδ,x-a+(i+1)δ]. Finally, we define (pn()) as the indicator functions of this set of small intervals.

5.1.2 Monte Carlo simulations

To compute the projection coefficients α, we will use M independent Monte Carlo simulations of Xtn, which will be denoted by Xtnm.

5.1.3 Description of the algorithm

Initialization: for n=N, we set VtNη,M(Xm)=g(Xm).

Iteration: for n=N-1,,0,

we approximate the conditional expectation by computing

  αnM=arginfα1Mm=1M|Vtn+1η,M(Xtn+1m)-α.pn(Xtnm)|2;  

we set V~(Xtnm)tnη,M=(αnM.pn(Xtnm).

Finally, we define Vtnη,M() as

  Vtnη,M(Xtnm)=max{e-r(tn+1-tn)V~tnη,M(Xtnm),h(tn,Xtnm)}.  

5.1.4 Function bases

We use the basis (HC) defined above. So, we set

  d1=minn,mXtnm,d2=maxn,mXtnmandL=d2-d1δ,  

where δ is the edge of the small intervals (Dj)1jL, defined by Dj=[d1+(j-1)δ,d1+jδ), for all 1jL. The basis is defined by

  (pnm(Xtnm)) ={Mm=1M1Dj(Xtnm)Mm=1M1Dj(mins{t0,,tn}Xsm)  
      ×1Dj(Xtnm)1Dj(mins{t0,,tn}Xsm),1j,jL}.  

This system is orthonormal with respect to the empirical scalar product defined by

  ψ1,ψ2n,M:=1Mm=1Mψ1(XtnN,m)ψ2(XtnN,m).  

In this case, the solutions of our least squares problems are given by

  αnM=1Mm=1MVtn+1η,M(XtnN,m)pn(XtnN,m).  

5.2 The algorithm based on optimal exercise estimation

The algorithm corresponds to the approach developed by Longstaff and Schwartz in which the conditional expectation operators are estimated by nonparametric regression techniques with a monomial basis.

5.2.1 Description of the algorithm

Initialization: for n=N, we set VtNη,M(Xm)=g(Xm).

Iteration: for n=N-1,,0,

we approximate the optimal stopping time by computing

  τnη,M:=tn?Anη,M+τn+1η,M?(Anη,M)c,  

where

  Anη,M:={h(Xtnm(ω))?^tn[h(Xτn+1η,M)]}  

and ?^tn is an approximation of the true conditional expectation operator ?^tn using the nonparametric regression approach, ie, by solving a least squares problem;

we use the price estimator at 0:V0η,M(X0):=?^[g(Xτ0η,M)].

5.2.2 Function bases

Table 1: Price of an American lookback put option for different values of M and N, and δ=0.35.
  ?
   
  150 175 200 225 250 275 300 325
M=8 000 7.532 7.551 7.556 7.563 7.591 7.592 7.598 7.602
M=10 000 7.534 7.552 7.566 7.564 7.598 7.584 7.601 7.600
M=12 000 7.531 7.554 7.580 7.590 7.602 7.598 7.603 7.605
Price of an American lookback put option using the (HC) basis and delta=0.35.
Figure 1: Price of an American lookback put option using the (HC) basis and δ=0.35.
Table 2: Price of an American lookback put option using the Longstaff–Schwartz method for different values of N and M=10 000. [SD denotes standard deviation.]
  ?
   
  400 600 800 1000 1200 1400
Mean 7.592 7.528 7.591 7.600 7.597 7.594
SD 3.589 10-15 8.075 10-16 3.579 10-15 3.589 10-15 8.972 10-15 3.383 10-15
Table 3: Price of an American lookback put option using the Longstaff–Schwartz method for different values of N and M=12 000.
  ?
   
  400 600 800 1000 1200 1400
Mean 7.534 7.574 7.574 7.574 7.612 7.578
SD 4.486 10-15 6.280 10-15 4.486 10-15 6.280 10-15 8.075 10-15 3.589 10-15
Table 4: Price of an American lookback put option using the Longstaff–Schwartz method for different values of N and M=15 000.
  ?
   
  400 600 800 1000 1200 1400
Mean 7.518 7.587 7.585 7.599 7.601 7.598
SD 8.075 10-15 8.972 10-15 9.869 10-15 6.280 10-15 5.383 10-15 8.075 10-15
Pricing of an American lookback put option using the Longstaff--Schwartz method.
Figure 2: Pricing of an American lookback put option using the Longstaff–Schwartz method.

The idea of taking a monomial basis to price American options was introduced by Longstaff and Schwartz. Such an approach can be extended to Hermite and Chebyshev polynomials. In our case, since we are studying American lookback put options, our basis function should be path dependent. The basis of polynomials chosen for our paper is given by

  (pnm(XtnN,m)) =(1,XtnN,m,minti{0,,tn}XtiN,m,XtnN,mminti{0,,tn}XtiN,m,  
      (XtnN,m)2,(minti{0,,tn}XtiN,m)2,(XtnN,m)2(minti{0,,tn}XtiN,m)2).  
Remark 5.1.

Note that for each value of M, N and δ for the first algorithm, we launch the algorithm fifty times and we denote the set of collected values by (V0,mη,M)1m50. We then calculate the empirical mean V¯0η,M and the empirical standard deviation σN,M, defined by

  V¯0η,M=150m=150V0,mη,MandσN,M=149m=150|V0,mη,M-V¯0η,M|2.   (5.2)

5.3 Numerical results

We take the following values for our parameters: r=0.08, σ=0.2, T=0.25, K=45 and X0=40.

Table 1 shows the price of an American lookback put option for different values of N and M. We remark that the price is near 7.6, which is the value found by Lai and Lim (2004). Their method is based on summing the corresponding European value and an “early exercise premium”.

Tables 24 show the price (mean and standard deviation) of American lookback put options using the Longstaff–Schwartz method, where we vary the number of trajectories and the number of time discretization steps. In Figure 1, we plot the price of an American lookback put option using the hypercube method for different values of N and M, and δ=0.35. In Figure 2, we plot the price of an American lookback put option using the Longstaff–Scwhartz method for different values of N and M. Tables 14 show that the step discretization in time must be small enough. In fact, Asmussen (1995) proved that

  NlogNsupt[0,T]|Bt-BtN|2  

in distribution, where (BtN)t[0,T] is called a step process, defined by BtN=BtiN for all t[ti,ti+1), and 0iN-1 and (BtiN-Bti-1N)1itN-1 are independent Gaussian random variables satisfying var(BtiN-Bti-1N)=ti-ti-1. The last asymptotic property allows us to guess that the convergence of the numerical scheme to the value function is obtained when N is large enough; this is unlike the vanilla option, where we take N=50. One question that remains is the choice between N and M and the number of functions, should we have to achieve a given accuracy by a joint convergence of N, M, and the number of functions to infinity.

Declaration of interest

The authors report no conflicts of interest. The authors alone are responsible for the content and writing of the paper.

Acknowledgements

The support of the “Chair Markets in Transition” (Fédération Bancaire Française) is acknowledged.

References

Only users who have a paid subscription or are part of a corporate subscription are able to print or copy content.

To access these options, along with all other subscription benefits, please contact [email protected] or view our subscription options here: http://subscriptions.risk.net/subscribe

You are currently unable to copy this content. Please contact [email protected] to find out more.

You need to sign in to use this feature. If you don’t have a Risk.net account, please register for a trial.

Sign in
You are currently on corporate access.

To use this feature you will need an individual account. If you have one already please sign in.

Sign in.

Alternatively you can request an individual account here: