An Exact Sub exp onential-Time Lattice Algorithm for Asian Options Tian-Shyr Dai Abstract Asian options are path-dependent derivatives. How to price them efficiently and accurately has been a longstanding research and practical problem. Asian options can be priced on the lattice. But only exponential-time algorithms are currently known if such options are to be priced on a lattice without approximation. Although efficient approximation methods are available, most of them lack accuracy guarantees. This paper proposes a novel lattice for pricing Asian options. The resulting exact pricing algorithm runs in subexponential time. This is the first exact lattice algorithm to break the exponential-time barrier. Because this lattice converges to the continuous-time stock price process, the proposed algorithm is guaranteed to converge to the desired continuous-time option value. 1 Intro duction Path-dependent derivatives are derivatives whose payoff depends nontrivially on the price history of a stock. Path-dependent derivatives play an important role in financial markets. Unfortunately, some of them are known to be difficult to price in terms of speed and/or accuracy, the Asian option being the most prominent example. An Asian option is an option whose payoff depends on the arithmetic average price of the stock. It is useful for hedging transactions whose cost is related to the average price of the stock (such as crude oil). Its price is also less sub ject to price manipulation; hence the average-price feature is popular in many thinly-traded markets. There are no exact simple closed-form solutions for Asian option prices. Approximate closed-form solutions are suggested in [17, 21, 24]. Geman and Yor derive an Department of Computer Science & Information Engineering, National Taiwan University, Taipei, Taiwan. E-mail: camel@turing.csie.ntu.edu.tw. The author was supported in part by NSC grant 92-2213-E-002-016. Department of Finance and Department of Computer Science & Information Engineering (preferred address), National Taiwan University, No. 1, Sec. 4, Roosevelt Rd., Taipei, Taiwan. E-mail: lyuu@csie.ntu.edu.tw. The author was supported in part by NSC grant 92-2213-E-002-016. Yuh-Dauh Lyuu analytical expression for the Laplace transform of the Asian call in [13]. Numerical inversion of this transform is considered in [12] and [23]. Some inversion algorithms based on the Euler and Post-Widder methods can be found in [1]. Most closed-form formulas lack accuracy guarantees. Indeed, some produce large pricing errors in extreme cases [11]. Since no simple closed-form solutions exist yet for the Asian option, the development of efficient numerical algorithms becomes critical. First, there are the popular Monte Carlo and quasi-Monte Carlo methods [3, 4, 5, 16]. Both the Monte Carlo approach and the analytical approach suffer from the inability to price American-style Asian options without bias. (Europeanstyle and American-style options will be defined later. Basically, European-style options do not allow early exercise, whereas American-style options do.) Recently, a least-squares Monte Carlo approach to address this problem is proposed [18]. Another problem of Monte Carlo method is that it is inefficient and the result is probabilistic. An alternative approach is the lattice and the related discretized partial-differential-equation method. This approach can handle early exercise. A lattice consists of nodes and edges connecting them. The lattice divides a time interval into n equal time steps. If the stock price process simulated by the lattice converges to the continuous-time stock price process as n , then the option value priced on this lattice by the so-called backward induction (to be introduced later) also converges to desired continuous-time option value [9]. The difficulty in pricing Asian options is evidenced by the fact that only exponential-time lattice pricing algorithms are known if approximation is not used in backward induction. We call a lattice algorithm exact if it does not adopt approximation in backward induction. (In this paper, a polynomial-time algorithm means that the running time is polynomial in n. The same convention is adopted for exponential-time and subexponential-time algorithms.) To reduce the complexity, Hull and White propose an efficient approximation algorithm in [14]. Their influential paradigm is followed by many such as [15, 22, 25]. The ma jor prob- Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 710 lem with the Hull-White paradigm is the convergence guarantee. Specifically, assume that the pricing error between the approximate and the exact algorithms is denoted by e. An approximation lattice algorithm converges to the desired option value if e 0 as n . Unfortunately, most Hull-White-type algorithms lack such convergence guarantees. In fact, improper approximations result in divergence or convergence to a wrong value [10]. Aingworth et al. and Dai et al. provide efficient approximation algorithms that have convergence guarantees for the European-style Asian options [2, 7]. Unfortunately, neither has convergence guarantees for American-style Asian options.1 Another paradigm due to Dai and Lyuu [8] constructs a lattice called the multiresolution lattice. It converges to the desired option value as it is exact. Numerical results show that the method works for n up to 160 under some cases. Note that an exponential-time algorithm cannot work with an n that high. There are two drawbacks with the multiresolution lattice. First, no proof is offered to show that this algorithm runs in subexponential time. Second, the multiresolution lattice is constructed by an ad hoc local search, and no proof exists to guarantee that the lattice can always be constructed successfully. Our paper will propose the first exact pricing algorithm that provably breaks the exponential-time barrier. Here is the rough overview. We construct a new lattice composed of integral stock prices. The stock price sum of a price path on the lattice is therefore an integer. This critical property is used to ensure that no approximations are needed in backward induction, making the algorithm exact and convergent. We also prove that the time complexity is subexponential in n. The homogeneous property of the option value is crucial to the construction of the said lattice. Suppose we multiply the stock prices by a constant K before pricing the option. The homogeneous property says that this option value divided by K gives the originally desired option value [20]. In our paper, a K is found that guarantees that an integral lattice can be constructed. To ensure that the pricing results based on our lattice converge to the desired continuous-time option value, we have to make sure that our lattice converges to the continuous-time stock price process. The conditions are that the lattice should match the mean and the variance of the stock price process at each time step [9]. It will be proved that an integral price that satisfies the above conditions exists for every node on the lattice. The paper is organized as follows. The mathemat1 Aingworth et al. give an incorrect convergence pro of for their American-style Asian option pricing algorithm [7]. ical model is described in section 2. We will review how a lattice is constructed and how the Asian option is priced on the lattice in section 3. In section 4, we will show how to construct the proposed lattice. Rigorous proofs given in section 5 shows that our pricing algorithm is the first exact pricing algorithm that breaks the exponential-time barrier. Section 6 concludes that paper. 2 Mo deling and Definitions Assume that an Asian option initiates at 0 (in years) and matures at T (in years). Define S (t) as the price of the stock at year t. The stock price is assumed to follow the continuous-time log-normal diffusion process: (2.1) S (t + dt) = S (t)exp[(r - 0.5 2 )dt + dWt ], where Wt is the standard Wiener process, r is the risk-free interest rate per annum, and is the annual volatility. It is useful to think of dWt as normally distributed with mean 0 and variance dt. In the discretetime approximation, the time between year 0 and year T is partitioned into n time steps. The length of each time step t is equal to T /n. For convenience, all the time notations in this paper are expressed in terms of the number of time steps unless stated otherwise. Let Si denote the stock price at (discrete) time i, which corresponds to S (it) in the continuous-time model. Define the sum of a partial price path started at time 0 j and ended at time j , S0 S1 · · · Sj , as i=0 Si . We call this sum prefix sum. The payoff of an Asian option depends on the average of the stock prices. The price average is defined as Aavg (i) S0 + S1 + · · · + Si . i+1 The payoff for a European-style Asian option at maturity date is A for a call, avg (n) - X , (2.2) exercise value = X - Aavg (n), for a put, where X is called the exercise price. Our task is to compute e-nrt E (max(Aavg (n) - X, 0)) and e-nrt E (max(X - Aavg (n), 0)) in such a way that the value converges to the continuous-time limits T 1 e-rT E [ max( T 0 S (t) dt - X, 0) ] and e-rT E [ max(X - T 1 T 0 S (t) dt, 0) ], resp ectively, as n increases. An American-style option gives the owner the right to exercise the option before maturity, thus an earlier payoff. The exercise value for an American-style option at time i is A for a call, avg (i) - X , (2.3) exercise value = X - Aavg (i), for a put. 711 An option will be exercised early by the owner if the option's continuation value (the value to hold the option) is smaller than its exercise value. 3 Preliminaries Before introducing our new lattice, we first review how a lattice is constructed so that it converges to the lognormal price process. Next we will show how to price an Asian option on a lattice. This part will demonstrate why the typical exact pricing algorithm explodes exponentially and why the approximation approach of Hull and White [14] is problematic. Finally, we will review the ideas of the integral lattice that will be useful later. S0u Pu S0u 3 S 0u 2 S0u S0 Pd S0d S0 S0d Sd 2 S0 d 3 0 1 2 3 3.1 How To Construct a Lattice We use the wellknown Cox-Ross-Rubinstein (CRR) binomial lattice [6] to illustrate how a lattice is constructed in principle. A Figure 1: A 3-time-Step CRR Binomial Lattice. 3-time-step CRR binomial lattice is illustrated in Fig. 1. At each time step, the stock price S can either become S u--the up move--with probability Pu or S d-- Note that 2 degrees of freedoms are provided by an the down move--with probability Pd 1 - Pu . The -nomial lattice. They include price multiplicative relation factors (like u and d in the CRR binomial lattice) and branching probabilities (like Pu and Pd in the (3.4) ud = 1 CRR binomial lattice). These branching probabilities must be between 0 and 1 to meet the no-arbitrage is enforced by the CRR binomial lattice. The logarithrequirements. We need 2 independent equations to mic stock price mean (µ) and variance (Var) one time determine these 2 variables uniquely. The calibration step from now are derived from Eq. (2.1) as of mean and variance gives 2 equations. The branching 2 probabilities sum to 1, giving another one. Additional (3.5) µ (r - 0.5 )t, 2 - 3 equations must be added. For example, Eq. (3.4) Var 2 t. (3.6) is the extra equation used in the CRR binomial model. To make sure that the lattice converges to the This paper will construct a trinomial lattice ( = 3). continuous-time stock price process, the mean and the variance of the logarithmic price process should be cal- 3.2 Pricing Asian Options on a Trinomial Latibrated by the matching those of the lattice and those tice We now show how to price an Asian call with a trinomial lattice. In a trinomial lattice, each node can of the continuous-time model: branch to three successor nodes in next time step. Let Si,j denotes (j + 1)th largest stock price of the nodes (3.7) Pu ln u + Pd ln d = µ, at time i. A 2-time-step trinomial tree is illustrated in (3.8) Pu (ln u - µ)2 + Pd (ln d - µ)2 = Var. Fig. 2. Take the root node as an example. Its stock price is S0,0 . The stock price can move upward to S1,0 Note that with probability Pu , move flatly to S1,1 with probability Pm , and move downward to S1,2 with probability (3.9) Pu + Pd = 1. Pd . The branching probabilities will vary for different The 4 parameters (Pu , Pd , u, and d) are uniquely ob- nodes. There are 2 + 1 nodes at time . tained by solving Eqs. (3.4), (3.7)­(3.9). The branching Note that the option value of a partial price path is probabilities Pu and Pd should be between 0 and 1 to influenced by the prefix sum of this partial price path. meet the no-arbitrage requirements. In the CRR lattice, To price an Asian option exactly, enough number of this demand can always be met by suitably increasing states are required at each node to keep the option n [19]. values corresponding to different prefix sums. The If each node in a lattice can branch to nodes at the option value at time n can be calculated by Eq. (2.2). next time step, we call it an -nomial lattice. The above Define V(S, C ) as the option value whose corresponding idea can be applied to construct an -nomial lattice. prefix sum is C and whose stock price is S . Again, let 712 S2,0 S1,0 Pu S0,0 Pm Pd S1,2 S1,1 S2,1 S2,2 S2,3 S2,4 0 1 2 time of O(k n2 ). However, it is problematic since interpolation errors are introduced and accumulated at each time step. The Hull-White approach therefore may not converge to the desired option value as n . Aingworth et al. [2] and Dai et al. [7] also use interpolation in their approximation algorithms. Their algorithms provide convergence guarantees for Europeanstyle Asian options. This relies on the observation that V (S, C ) can be evaluated by a simple formula if C nX . They can then focus on evaluating V (N , C ) for C < nX by using Eq. (3.10) and interpolation. However, no efficient approximation algorithms have convergence guarantees for pricing American-style Asian options. 3.3 An Integral Lattice Reducing the number of prefix sums by restricting the possible stock price of each node in the lattice is first suggested by Dai and Lyuu [8]. In our paper, we will construct a trinomial lattice composed of integral stock prices. Note that if the stock price of each node in the lattice is an integer, all possible prefix sums must be integers since integers are closed under additions. A proof to show that the time complexity of the algorithm is subexponential in n will be given later. Note that the stock price at the root node S is not required to be an integer. S is a rational number when storing in the computer. Thus S can be represented as S + a for some integer S 0 and some rational number a where 0 a < 1. Assume that the maximum prefix sum in the lattice is F . Any possible prefix sum must belong to the set {X : X F, X = I + a, I is a nonnegative integer.}. The key to show that our algorithm breaks exponential time barrier is to prove that the number of elements in this set is bounded by a subexponential function in n. 4 Lattice Construction Figure 2: A 2-Time-Step Trinomial Lattice. The initial stock price is S0,0 . Si,j denotes the (j + 1)th largest stock price at time i. Pu , Pm , and Pd denote the branching probabilities, respectively. Pu , Pm , and Pd denote the branching probabilities of the node with stock price Si,j . The backward induction formulae for the European-style and American-style options are V(Si,j , C ) (3.10) and V(Si,j , C ) = e max -rt [Pu V(Si+1,j , C + Si+1,j )+ Pm V(Si+1,j +1 , C + Si+1,j +1 ) + Pd V(Si+1,j +2 , C + Si+1,j +2 )] , E ) , respectively. The exercise value E in the latter formula is defined in Eq. (2.3). The above formulae can be applied in a backward fashion from time n to time 0. The root node thus gives the desired option value. The backward-induction procedure implies that the overall running time is proportional to the total number of prefix sums on the lattice. Unfortunately, the number of price paths grows exponentially in n, giving as many prefix sums. This makes an exact pricing algorithm explode exponentially. Hull and White suggest an efficient algorithm by limiting the number of prefix sums at each node to some manageable magnitude k [14]. It then resorts to interpolation as an approximation scheme in backward induction. This approach is efficient, with a running = e-rt [Pu V(Si+1,j , C + Si+1,j )+ Pm V(Si+1,j +1 , C + Si+1,j +1 ) + Pd V(Si+1,j +2 , C + Si+1,j +2 )] To reduce the number of prefix sums at each node in our lattice, the stock price of each node (except the root node) is restricted to be an integer. To ensure that the stock price process simulated by our lattice converges to the stock price process mentioned in Eq. (2.1), the mean and the variance of the logarithmic stock price process are matched at each node in the lattice. In this section, we will first show how the lattice is constructed step by step in order to meet the above two requirements. Proof will be given in the next section to show that our lattice provides a subexponential-time algorithm for Asian options. The homogeneous property says [20]: E [max(A - X, 0)] = 1 E [max (K A - K X, 0)] . K 713 Thus we can multiply the initial stock price (S0 ) and the strike price X by a constant K and price this hypothetical option. The desired option value is then obtained by dividing this hypothetical option price by K . To ensure that a proper integral price can be assigned to each node (except the root node), K is defined as follows: (4.11) ( . n /T exp 0.5 2 - r) T + 2 T n K (0.25S0 )-1 Note that K eO( n) . We will show later that this K works. Next a trinomial lattice is constructed to price this hypothetical option. Note that the stock price of the root node (S0,0 ) is equal to K S0 .2 Our goal is to find integral stock prices Si,j for 0 < i n, a 0 j 2i. Define the V -log-price of stock pri V ce s ln(V /V ) and ci,j (r - 0.5 2 ) it + 2(i - j ) t . Si,j will be some integer whose K S0 -log-price belongs to the following interval centered around ci,j : (ci,j - 0.25 t, ci,j + 0.25 t). We call ci,j the log-price center for Si,j . Take the 2-time-step trinomial lattice in Fig. 3 as an example. The x-axis marks the time step in the lattice, and the y -axis denotes K S0 -logprices. Each log-price center is depicted as a hollow circle. Each dotted line segment begins at ci,j and ends at ci+1,j +1 . The slopes of these dotted lines represent the expected growth rate of the logarithmic stock price, (r - 0.5 2 )t. The integral stock price for each node is depicted as a solid circle. Take S2,0 as an example. Because c2,0 = (r - 0.5 2 ) 2t + 4 t, -p the K S0 -log rice of S2,0 should fall within the interval (c2,0 - 0.25 t, c2,0 + 0.25 t). The proof in section 5.1.1 shows that there is always at least one integer whose K S0 -log-price falls within the said interval. The branching probabilities for each node are computed as follows. Take a node with price Si,j . Recall that the probabilities for the stock price moving to Si+1,j , Si+1,j +1 , and Si+1,j +2 are Pu , Pm , and Pd , respectively. Define , , and as follows: (4.12) (4.13) ln(Si+1,j /Si,j ) - µ, ln(Si+1,j +1 /Si,j ) - µ, Logarithmic Stock Price C 2,0 + 0.25 t C2,0 C2,0 - 0.25 t C2,1 C1,0 F = (r - 0.5 2 )t C2,2 0 C1,1 C1, 2 C2 , 3 C2, 4 1 2 Time igure 3: A 2-Time-Step Trinomial Lattice over K S0 -log-prices. where Var is defined in Eq. (3.6). Eqs. (4.15) and (4.16) match the mean and the variance of the logarithmic stock price, respectively. Hence our lattice converges weakly to the lognormal stock price process. That Eqs. (4.15)­(4.17) give valid branching probabilities will be proved in section 5.1.2. 5 Pro of A proof is given to show that our approach provides a subexponential-time algorithm for pricing Asian options. The proof is broken up into two parts. First, we will show that a valid lattice is constructed. Next we will show that the exact pricing algorithm based on this lattice runs in subexponential time. 5.1 Validity of the Lattice 5.1.1 Existence of Integral Sto ck Prices When constructing the trinomial lattice, an integral stock price is assigned to each node. More specifically, Si,j ln(Si+1,j +2 /Si,j ) - µ, (4.14) should be an integer whose K S0 -log-price falls in (ci,j - where µ is defined in Eq. (3.5). The branching proba0.25 t, ci,j + 0.25 t). To ensure that such an bilities satisfy integer exists, it suffices to show that e c - c > (4.15) Pu + Pm + Pd = 0, (4.16) (4.17) Pu 2 + Pm 2 + Pd 2 Pu + Pm + Pd = = Var, 1, K S0 xp i,j + 0.25 t exp i,j - 0.25 t 1. 2 Note that K S is not necessary an integer since b oth K and 0 S0 are not necessary integers, too. Our goal now is to show that our choice of K in Eq. (4.11) satisfies the above inequality. Without loss of is generality, only the case Sn,2n considered as exp(ci,j + 0.25 t) - exp(ci,j - 0.25 t) is minimized when 714 i = n and j = 2n. Thus it suffices to show that our K satisfies e -1 - K > S0 1 e-cn,2n 0.25 t - e-0.25 t . Indeed, = e -1 - S0 1 e-cn,2n 0.25 t - e-0.25 t ( × - S0 1 exp 0.5 2 - r ) T + 2 T n e -1 0.25 t - e-0.25 t ( / T - S0 1 exp 0.5 2 - r ) T + 2 T n (0.25 /n) ( n (0.25S0 )-1 /T exp 0.5 2 - r ) T + 2 T n eO( e n) We next represent and in terms of . Define d1 as the difference between Si+1,j 's and Si+1,j +1 's Si,j log-prices and d2 as the difference between Si+1,j +1 's and Si+1,j +2 's Si,j -log-prices. Thus and can be represented as = ln (Si+1,j /Si,j ) - ln(Si+1,j +1 /Si,j ) (5.18) < = + ln(Si+1,j +1 /Si,j ) - µ = d1 + , = ln (Si+1,j +2 /Si,j ) - ln(Si+1,j +1 /Si,j ) , > + 0.25 t - 1 = 0.25 t . where Eq. (5.18) holds because 1 0.25 t -0.25 t -e 5.1.2 Validity of Branching Probabilities In this section, we will prove that Eqs. (4.15)­(4.17) result in valid branching probabilities for the stock price Si,j . To be more specific, the branching probabilities Pu , Pm , and Pd , are proved to be strictly larger than 0 to meet the no-arbitrage requirement (note that this suffices to ensure that they are all less than 1). First we will derive constraints on , , defined in Eqs. (4.12)­(4.14). Then we will show that valid branching probabilities are obtained by solving Eqs. (4.15)­(4.17) given the constraints on , , and . We use the plot in Fig. 4 to aid the proof. Note that a K S0 -log-price of x becomes a Si,j -log-price of x + lln KiSj0 . The following computations are in Si,j -lognS, prices unless sated otherwise. The log-price center of Si,j , c , equals ci,j + lln KiSj0 , whereas c, the log-price nS, center of Si+1,j +1 , equals c + (r - 0.5 2 )t. he logT price centers of Si+1,j and Si+1,j +2 are c + 2 t and c - 2 t, respectively. The Si,j -log-price of Si,j is 0. The conditional mean of the stock price one time step after it reaches Si,j is µ = (r - 0.5 2 )t. By construction, the distance between the Si,j -log-price of eq Si,j , which uals 0, and its log-price center c is smaller than 0.25 t . This implies that |c | < 0.25 t . Hence, =( c+ r - 0.5 2 )t - (r - 0.5 2 )t |µ - c| = | c | < 0.25 t . Thus µ falls within interval (c - 0.25 t, c + 0.25 t). Now = ln(Si+1,j +1 /Si,j ) - µ falls within interval (-0.5 t, 0.5 t) as the Si,j -log-price of Si+1,j1 , ln(Si+1,j +1 /Si,j ), falls within interval (c - + 0.25 t, c + 0.25 t). Figure 4 illustrates a case where < 0. + ln(Si+1,j +1 /Si,j ) - µ = -d2 + . Note that 1.5 t < d1 < 2.5 t because c + 1.75 t < ln(Si+1,j /Si,j ) < c + 2.25 t, c - 0.25 t < ln(Si+1,j +1 /Si,j ) < c + 0.25 t, d1 = ln(Si+1,j /Si,j ) - ln(Si+1,j +1 /Si,j ). N t Similarly, 1.5 t < d2 < 2.5 t. ote also hat = d1 + > t > 0 as (-0.5 t, 0.5 t) S and d1 (1.5 t, 2.5 t). imilarly, = -d2 + < - t < 0 as d2 (1.5 t, 2.5 t). It is also obvious that > > as d1 , d2 > 0. We now show that positive branching probabilities are obtained given the constraints on , , and derived above and summarized below: (-0.5 t, 0.5 t). = d1 + , where d1 (1.5 t, 2.5 t). = -d2 + , where d2 (1.5 t, 2.5 t). The branching probabilities are solved by applying Cramer's rule to Eqs. (4.15)­ (4.17). Define det detu detm detd = = = = ( - )( - )( - ), ( + Var)( - ), ( + Var)( - ), ( + Var)( - ). Then Pu = detu /det, Pm = detm /det, and Pd = detd /det. Note that det < 0 as > > . To show that the branching probabilities are valid, we have to show that Pu , Pm , Pd > 0. As det < 0, it is sufficient to show detu , detm , detd < 0. Moreover, as - < 0, - > 0, and - < 0, we only need to show that + Var > 0, + Var < 0, and + Var > 0 instead. 1. + Var > 0: Note that + Var = ( - d2 ) + 2 t = ( - 0.5d2 )2 - 0.25d2 + 2 t. 2 715 c + 2.25 t c + 2 t c + 1.75 t ( S i + 1, j ) | | 3. + Var > 0: This is proved similarly as we prove + Var > 0. Note that + Var d1 Pu c'+0.25 t ( Si , j ) = ( + d1 ) + 2 t = ( + 0.5d1 )2 - 0.25d2 + 2 t. 1 c + 0.25 t c µ ( S i +1, j +1 ) c' c'-0.25 t Pm Pd | | | | c - 0.25 t d2 For a given d1 , + Var reaches its minimum when l = -0.5d1 . Recal the constraints that -0.5d1 (-1.25 t, -0.75 t) and > -0.5 t. Hence + Var reaches its minimum for given d1 a (1.5 t, 2.5 t) when -0.5 t. Thus we have + Var ( + d1 ) + 2 t > (-0.5 t + d1 )(-0.5 t) + 2 t = -0.5 t d1 + 1.25 2 t > -1.25 2 t + 1.25 2 t = 0. = c - 1.75 t c - 2 t ( S i +1, j + 2 ) i c - 2.25 t i+1 Figure 4: Branching Probabilities for the No de with Price Si,j . All the values in this figure are Si,j -log-prices except the ones that are parenthesized. The nodes with stock prices Si,j , Si+1,j , Si+1,j +1 , and Si+1,j +2 are represented by solid circles. The branches that connect these nodes are represented by thick lines. The log-price centers of Si,j and Si+1,j +1 are c and c, respectively. Pu , Pm , and Pd denote the branching probabilities for the upper, middle, and lower branches from the node with price Si,j . Values , , and are defined in Eqs. (4.12)­(4.14). Finally, | d1 | denotes the distance between Si+1,j 's and Si+1,j +1 's Si,j -log-prices, and | d2 | denotes the distance between Si+1,j +1 's and Si+1,j +2 's Si,j -log-prices. For a given d2 , + Var reaches its minimum when ec th = .5d2 . R all the constraints at 0.5d2 0 (0.75 t, 1.25 t) and < 0.5 t. Hence + ar reaches its minimum for a given d2 V (1.5 t, 2.5 t) when 0.5 t. Thus, we have 5.2 Running-Time Analysis Note that the time complexity of an exact pricing algorithm is proportional to the total number of prefix sums on the lattice. Thus the pricing algorithm is subexponential in n if the total number of prefix sums is bounded by a subexponential function. We will first show that the maximum prefix sum in our lattice is bounded by a subexponential function. Then we will show that the total number of prefix sums is, too. The maximum stock price Sn,0 is bounded by K S0 ecn,0 +0.25 t , where cn,0 = (r - 0.5 2 )nt + 2(n - 0) t = (r - 0.5 2 ) T + 2 T n . Thus Sn,0 is bounded by a subexponential function as both K and ecn,0 +0.25 t are subexponential in n. The maximum prefix sum in the lattice is equal to n i=0 Si,0 (n + 1)Sn,0 . Note that (n + 1)Sn,0 is also a subexponential function. We define F (n + 1)Sn,0 for simplicity. The next goal is to show that the total number of prefix sums is bounded by a subexponential function. + Var = ( - d2 ) + 2 t Recall that the stock price for each node except the root node in our lattice must be an integer. The stock > 0.5 t (0.5 t - d2 ) + 2 t price at the root node (K S0 ) can be represented as 2 = -0.5 t d2 + 1.25 t S + a for some integer S 0 and some rational > -1.25 2 t + 1.25 2 t = 0. number a where 0 a < 1. Thus all the possible prefix sums must belong to the set {X : X F, X = 2. + Var < 0: Note that I + a, I is a nonnegative integer.}. The number of 2 elements in this set is at most F . Thus the maximum + Var = ( + d1 )( - d2 ) + t. number of prefix sums for each node is bounded by F . Since there are (n+1)2 nodes in an n-time-step trinomial As + d1 > t and - d2 < - t, we have lattice, the total number of prefix sums is bounded ( + d1 )( - d2 ) + 2 t < ( t)(- t) + 2 t = 0. above by the subexponential function (n + 1)2 F . The 716 time complexity of our algorithm is thus subexponential in n. 6 Conclusions This paper develops a new trinomial lattice particularly with the Asian option in mind. The lattice uses the notion of integrality of stock prices to reduce the time complexity of an exact pricing algorithm dramatically. Rigorous proof is given to show that the time complexity is subexponential in n. Our lattice is guaranteed to converge to the continuous-time stock price process. The proposed pricing algorithm is guaranteed to converge to the desired option value as it is exact. This is the first exact lattice algorithm to break the exponential-time barrier. References [1] Abate, J., and W. Whitt. (1995). "Numerical Inversion of Laplace Transforms of Probability Distributions." ORSA Journal of Computing 7, 36­43. [2] Aingworth, D., R. Motwani, and J.D. Oldham. (2000). "Accurate Approximations for Asian Options." In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms. [3] Boyle, P.P., M. Broadie, and P. Glasserman. (1997). "Monte Carlo Methods for Security Pricing." Journal of Economic Dynamics & Control 21, 1267­ 1321. [4] Broadie, M., and P. Glasserman. (1996). "Estimating Security Price Derivatives Using Simulation." Management Science 42, 269­285. [5] Broadie, M., P. Glasserman, and S. Kou. (1999). "Connecting Discrete and Continuous Path-Dependent Options." Finance and Stochastics 3, 55­82. [6] Cox, J., S. Ross, and M. Rubinstein. (1979). "Option Pricing: A Simplified Approach." Journal of Financial Economics 7, 229­264. [7] Dai, T.-S., G. -S. Huang, and Y.-D. Lyuu. (2002). "Extremely Accurate and Efficient Algorithms for Asian Options with Error Bounds." Quantitative Methods in Finance 2002 Conference, Cairns, Australia. [8] Dai, T.-S., and Y.-D. Lyuu. (2002). "Efficient, Exact Algorithms for Asian Options with Multiresolution Lattices." Review of Derivatives Researches 5, 181­203. [9] Duffie, D. (1996). Dynamic Asset Pricing Theory. 2nd ed. Princeton NJ: Princeton University Press. [10] Forsyth, P. A., K. R. Vetzal, and R. Zvan. (2002). "Convergence of Numerical Methods for Valuing Path-Dependent options Using Interpolation." Journal of Computational Finance 5, 273­314. [11] Fu, M.C., D.B. Dilip, and T. Wang. (1998/9). "Pricing Continuous Asian Options: A Comparison of Monte Carlo and Laplace Transform Inversion Methods." Journal of Computational Finance 2, 49­74. [12] Geman, H., and A. Eydeland. (1995). "Domino Effect." Risk 8, 65­67. [13] Geman, H., and M. Yor. (1993). "Bessel Processes, Asian Options, and Perpetuities." Mathematical Finance 3, 349­375. [14] Hull, J., and A. White. (1993). "Efficient Procedures for Valuing European and American PathDependent Options." Journal of Derivatives 1, 21­31. [15] Klassen, T.R. (2001). "Simple, Fast and Flexible Pricing of Asian Options." Journal of Computational Finance 4, 89­124. [16] Kemna, A.G.Z., and A.C.F. Vorst. (1990). "A Pricing Method Based on Average Asset Values." Journal of Banking and Finance 14, 113­129. [17] Levy, E. (1992). "Pricing European Average Rate Currency Options." Journal of International Money and Finance 11, 474­491. [18] Longstaff, F.A., and E.S. Schwartz. (2001). "Valuing American Options by Simulation: a Simple Least-Squares Approach." Review of Financial Studies 14, 113­147. [19] Lyuu, Y.-D. (2002). Financial Engineering and Computation: Principles, Mathematics, and Algorithms. Cambridge, U.K.: Cambridge University Press. [20] Merton, R.C. (1994). Continuous-Time Finance. Revised ed. Cambridge, MA: Blackwell. [21] Milevsky, M.A., and S.E. Posner. (1998). "Asian Options, the Sum of Lognormals, and the Reciprocal Gamma Distribution." Journal of Financial and Quantitative Analysis 33, 409­422. [22] Ritchken, P., L. Sankarasubramanian, and A.M. Vijh. (1993). "The Valuation of Path Dependent Contracts on the Average." Management Science 39, 1202­ 1213. [23] Shaw, W.T. (1998). Modeling Financial Derivatives with Mathematica. Cambridge, U.K.: Cambridge University Press. [24] Turnbull, S.M., and L.M. Wakeman. (1991). "A Quick Algorithm for Pricing European Average Options." Financial and Quantitative Analysis 26, 377­ 389. [25] Zvan, R., and K. Vetzal. (1999). "Discrete Asian Barrier Options." Journal of Computational Finance 3, 41­68. 717