# Efficient and Robust Combinatorial Option Pricing Algorithms on the Trinomial Lattice for Polynomial and Barrier Options

Authors: Jr-Yan Wang; Chuan-Ju Wang; Tian-Shyr Dai; Tzu-Chun Chen; Liang-Chih Liu; Lei Zhou
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Options can be priced by the lattice model, the results of which converge to the theoretical option value as the lattice’s number of time stepsn approaches infinity. The time complexity of a common dynamic programming pricing approach on the lattice is slow (at least On2), and a large n is required to obtain accurate option values. Although On-time combinatorial pricing algorithms have been developed for the classical binomial lattice, significantly oscillating convergence behavior makes them impractical. The flexibility of trinomial lattices can be leveraged to reduce the oscillation, but there are as yet no linear-time algorithms on trinomial lattices. We develop On-time combinatorial pricing algorithms for polynomial options that cannot be analytically priced. The commonly traded plain vanilla and power options are degenerated cases of polynomial options. Barrier options that cannot be stably priced by the binomial lattice can be stably priced by our On-time algorithm on a trinomial lattice. Numerical experiments demonstrate the efficiency and accuracy of our On-time trinomial lattice algorithms.


---

## Body

## 1. Introduction

Options are important financial derivatives whose values depend on other more fundamental financial assets, which are called the underlying assets, for instance, stocks, indexes, and currencies [1]. In this study, for convenience, the underlying asset is assumed to be a stock. To improve the market completeness and efficiency, many complex options have been structured to meet specific financial goals. However, most complex options do not have analytical pricing formulae and must be priced using numerical methods [2]. Exploring efficient and accurate numerical pricing methods is thus important in both theory and practice.The lattice method is a popular numerical pricing method. It can easily deal with American-style features like early redemption and early exercise that are found in many option contracts. It is also flexible, since only nominal changes are needed to price complex, nonstandard options, which do not have simple closed-form solutions [3] (Indeed, the flexibility of the lattice method makes it widely adopted in recent literature, such as the evaluation of American stock options [6], variable annuity products [7, 8], catastrophe equity puts [9], employee stock options [10], swing options [11], or corporate bonds [12–15]). Technically speaking, a lattice divides the option life into n discrete equal-length time steps and simulates stock price movements discretely at each time step. Four-time-step binomial and trinomial lattices are shown in Figure 1. While each node (except the nodes at the last time step) in the binomial lattice has two branches connected to the two following nodes at the next time step, each node in the trinomial lattice has three branches. The most classical binomial lattice is proposed by Cox, Ross, and Rubinstein [4] (CRR model hereafter) (Rubinstein [16] reviews the relation between binomial and trinomial lattices and shows that they are equivalent to explicit finite difference methods.), where a node with stock price S can move to SU or SD (UD=1) at the next time step with probabilities PU and PD, respectively. Similarly, a node with price S in a trinomial lattice can move to Su, S, and Sd (assuming ud=1 in Figure 1) at the next time step with probabilities pu, pm, and pd, respectively. The branching probabilities and the stock price multiplicative factors (like PU, PD, U, and D in the binomial lattice and pu, pm, pd, u, and d in the trinomial lattice) are determined to match the first two moments of distribution of the stock price process, so that the pricing results generated by lattice models converge to the theoretical value as n⟶∞ [4, 5].Figure 1
Illustration of binomial and trinomial lattice models. Four-time-step binomial (a) and trinomial (b) lattices are shown. The initial stock prices for both lattices are S0. In the binomial lattice, the upward and downward multiplicative factors for the stock price are U and D, respectively, where UD = 1 based on Cox et al. [4], and the upward and downward branching probabilities are PU and PD, respectively. In the trinomial lattice, the upward and downward multiplicative factors for the stock price are u and d (assuming ud = 1), respectively, and the upward, middle, and downward branching probabilities are pu, pm, and pd, respectively.
(a)(b)Pricing options on the lattice model can be achieved by dynamic programming. The value for each node in the lattice is recursively evaluated from the last-time-step back to the root node. Thus, it takes at leastOn2 time (or quadratic time of n) (For an On2-time pricing method, the computational time quadruples when n doubles) to price options on both the binomial and trinomial lattice models, since there are On2 nodes on an n-time-step lattice. The dynamic programming approach can be quite inefficient as the pricing results may converge slowly in n, and thus, a large value for n is required. Fortunately, Dai et al. [3] and Lyuu [17] proposed combinatorial approaches that can efficiently price a variety of options on the CRR binomial lattice in On time (or linear time of n). The computational time of an (O(n))-time pricing method doubles when O(n) doubles. (therefore, an O(n)-time pricing method runs much faster than a O(n2 ) one when n is large.)However, option pricing results generated by the lattice may oscillate wildly withn [18, 19]. For instance, when applying the CRR binomial lattice to price barrier options, the significant oscillation renders it impractical, as shown in Figure 2. To suppress this oscillation, the lattice structure should be adjusted to fit the option’s specifications. Since the trinomial lattice is more flexible than the binomial lattice, the structure of the trinomial lattice can be adjusted according to the option contacts to suppress the oscillation [2, 5, 19] (In the literature, various methods are used to mitigate the oscillating convergent behavior of the CRR binomial model; for example, Tian [22] and Klassen [23] for pricing vanilla options and Bolye and Lau [24] for pricing barrier options. Note that the modifications in Tian [22] and Klassen [23] lead to a nonhorizontal binomial tree, i.e., the asset price layers are no longer parallelly horizontal. However, the wide applications of combinatorial option pricing approaches depend crucially on the existence of horizontal layers, especially when they are used to price barrier-dependent options. Consequently, this study develops combinatorial option pricing algorithms based on trinomial lattices consisting of a set of parallelly horizontal layers. Bolye and Lau [24], meanwhile, proposed a method to locate a layer of nodes as close as possible to the barrier. Nevertheless, Ritchken [19] demonstrated that the trinomial lattice adopted in this study outperforms Bolye and Lau’s [24] method in terms of a faster convergence rate. In addition, the exponential error convergence rate of Fourier transform methods has led to their wide adoption in recent derivative pricing literature, such as discretely monitored barrier options [25, 26], continuously monitored barrier options [27], α-quantile and perpetual early exercise options [28], and Asian options [29]. Although lattice methods have slow error convergence rates as in Talponen and Turunen [30], their flexibility has led to their wide adoption in recent literature, as mentioned in footnote 1.). Although the trinomial lattice can alleviate the price oscillation problem, no efficient combinatorial algorithms for the trinomial lattice have been proposed and the inefficient dynamic programming approach, which takes at least On2 time, must be applied. To address this problem, we develop combinatorial pricing algorithms on the trinomial lattice, such that this novel option pricing framework inherits both the efficiency of the combinatorial algorithm and the accuracy of the trinomial lattice.Figure 2
Comparison of convergence behavior between binomial and proposed trinomial lattice models for pricing barrier options. Thex-axis and y-axis denote the number of time steps n and the option values, respectively. The dotted and dashed lines denote the pricing results generated by the binomial and our trinomial lattices, respectively. The solid line stands for the theoretical value based on the analytical pricing formula [20, 21]. Clearly, the trinomial lattice model alleviates the price oscillation problem with respect to the number of time steps, n.Developing a combinatorial algorithm for the trinomial lattice is much more difficult than that for the binomial one because the additional middle branch in the trinomial lattice complicates combinatorial formulae. Consider, for example, the number of price paths that start at the root and then finally reach the terminal stock priceS0 at the fourth-time-step, as shown in Figure 1. The number of price paths based on the binomial lattice (Figure 1(a)) is 42 because all price paths in this case should consist of exactly two upward and two downward movements. In contrast, the number of price paths based on the trinomial lattice (Figure 1(b)) is 4042+4221+4400, where each term represents a different composition of upward, middle, and downward movements for the price paths reaching the terminal node S0. For instance, the second term indicates that the price paths consist of two middle movements, one upward movement, and one downward movement. This complicated nature might be why no linear-time algorithm has been proposed for the trinomial lattice before this paper.We address this first by noting that the option pricing formulae for a wide range of options on the trinomial lattice can be decomposed into certain regular summation forms. Then, we prove in two theorems that each term in the summation form can be represented by a simple recursive formula of its preceding term; thus, the summation form can be evaluated inOn time. We take polynomial options as the first example to develop an On-time combinatorial algorithm for the trinomial lattice because polynomial options are general and able to accommodate widely traded power and vanilla call or put options as special cases, but polynomial options do not have closed-form solutions unless their payoffs satisfy certain restricted criteria [31, 32] (Kim et al. [33] and Zhang et al. [34] price power options as special cases of polynomial options). Other reasons motivating us to consider polynomial options are their flexible applications in practice. For instance, since the unusual payoff functions of exotic path-independent options (or even option portfolios) can be approximated by a polynomial function, the pricing method for the polynomial option can be employed to approximate the values of those exotic options that might not have closed-form solutions. In addition, if a portfolio is exposed to a risk factor in a nonlinear manner, the polynomial option can provide a more appropriate payoff to hedge this portfolio; such a hedge strategy is usually much cheaper than hedging with a combination of more fundamental derivatives. As a result, developing efficient and accurate algorithms for pricing polynomial options is an important and valuable issue. Furthermore, to demonstrate the versatility of the theorems proposed in this study, we develop the reflection principle on the trinomial lattice and then extend the combinatorial pricing algorithms on the binomial lattice in the study by Dai et al. [3] to evaluate barrier options on the trinomial lattice. The numerical results verify that our pricing algorithms run in On time and show that our algorithms are superior in terms of accuracy and efficiency.The structure of this study is as follows. We introduce fundamental knowledge about option pricing and the combinatorial approach in Section2 and propose two novel combinatorial theorems for option pricing in Section 3. In Section 4, we apply these theorems to develop linear-time algorithms for polynomial, power, plain vanilla, and barrier options. We present the experimental results in Section 5 and conclude in Section 6.


## 2. Preliminaries

### 2.1. Basic Framework

#### 2.1.1. Stock Price Process

Suppose an option initiates at time 0 and matures at timeT. Let St denote the stock price at time t, where 0≤t≤T. In addition, this study adopts the most common assumption for the St process on option pricing, which states that under the risk-neutral measure, St follows a log-normal diffusion process with drift μ=r−σ2/2 (this paper takes a non-dividend-paying stock for example. It is straightforward to extend our model to consider a stock paying a continuously compounding dividend yield) and volatility σ, where r is the risk-free rate.


#### 2.1.2. Kamrad and Ritchken Lattice (KRL) Model

Kamrad and Ritchken [5] proposed a trinomial lattice model, as shown in Figure 1(b). Denote Δt=T/n as the length of each time step. The KRL model parameterizes upward and downward multiplication factors u and d as(1)u=eλσΔt,d=u−1,where λ is the stretch parameter that can be adjusted to fit the option’s specification to alleviate the oscillation problem. To ensure that the trinomial lattice matches the drift (μ) and volatility (σ) of the stock price process, Kamrad and Ritchken set the upward, middle, and downward branching probabilities pu, pm, and pd as(2)ρu=12λ2+μΔt2λσ,pm=1−1λ2,pd=12λ2−μΔt2λσ.According to Ritchken [19], the oscillation problem can be significantly reduced by causing the lattice to coincide with a certain price level Y. Following this idea, we define λ as(3)λ=1.224745,ifY=S0orYis not available,InY/S0/σΔtInY/S0/σΔt,otherwise.Note that whenY=S0 (there must be a stock price layer coinciding with Y) or Y is not available (there is no specific level in the option contract to fit), we follow Kamrad and Ritchken [5] in setting λ as 1.224745, such that all branching probabilities converge to 1/3 when n⟶∞, which streamlines convergence for pricing options.


### 2.2. Polynomial Option

One major contribution of this study is the pricing of polynomial options—which do not have closed-form solutions unless polynomial payoffs satisfy some restricted criteria [31, 32]—with the trinomial lattice model in linear time. A general payoff form is considered as(4)Payoff=maxAST−X,0,where ST denotes the stock price on the maturity date T, and AST can be any polynomial function defined as AST≡α1STq1+α2STq2+⋯+αDSTqD, where αi’s can be any real numbers and qi’s are the nonidentical real numbers. Typically, the AST−X curve may intersect the ST-axis several times as shown in Figure 3. Consequently, there may be several separate regions that can generate positive payoffs, such as regions i, ii, and iii in Figure 3.Figure 3
Illustration of payoff function of polynomial option. This figure shows that the holder of this polynomial option can receive a positive payoff ifST belongs to regions i, ii, or iii, which in this paper are termed positive-payoff regions. Each positive-payoff region can be represented by a closed interval λl,λu; therefore, regions i, ii, and ii can be represented by 0,λ1, λ2,λ3, and λ4,∞, respectively.


### 2.3. Power Option

A power option grants the holder a right to buy or sell the power of the stock price for the exercise priceX at the maturity date T. On the other hand, the holder can junk the call option (or the put option) if the power of the stock price is lower (or higher) than the exercise price X at time T. The payoff of a power option can be defined as(5)Payoff=maxθSTq−θX,0,where q can be any real number and θ equals 1 for call options and −1 for put options.


### 2.4. Vanilla Option

A vanilla option, a special case of the power option by settingq=1, is a standard option without unusual features. The payoff for a vanilla option at time T is(6)Payoff=maxθST−θX,0,where θ equals 1 for call options and −1 for put options. Since the payoff function of the polynomial option can accommodate the payoffs of the power and vanilla options as special cases, it is straightforward to employ our combinatorial pricing algorithm for the polynomial option to evaluate these two options. Moreover, to alleviate the oscillation problem when pricing power and vanilla options, the KRL lattice requires a price level that coincides with X (i.e., Y=X in equation (3)) [23].


### 2.5. Barrier Option

A barrier option is an option whose payoff depends on whether the stock price path ever hits a certain price levelH called a barrier. Our study focuses on “up-and-in” barrier options; the extension to other types of barrier options is straightforward. Furthermore, we consider the case of H>S0 for convenience. Thus, an “up-and-in” barrier option can only be exercised at maturity when the stock price path has risen to hit the barrier during the option life. Define Ssup=sup0≤t≤TSt. The payoff function for a barrier option at time T is(7)Payoff=maxθST−θX,0,ifSsup≥H,0,otherwise,where θ equals 1 for call options and −1 for put options.To alleviate the oscillation problem, Ritchken [19] suggests that a price level of the lattice should coincide with the barrier H (i.e., Y=H in equation (3)).


### 2.6. Option Pricing Based on the KRL Model

The theoretical value of an option equals the discounted expected payoff of the option under the risk-neutral measure:(8)e−rTEpayoff.The above formula can be evaluated via dynamic programming by computing the option value of each node on the lattice model from time stepn back to time step 0. Take the polynomial option, for example. The value of each node at maturity can be evaluated by equation (4). In Figure 4, the examined node, say D, has three descendant nodes, say A, B, and C. Define Vy as the option value for any node y. The value VD of nodes other than the nodes at maturity can be computed by following backward induction formula.Figure 4
Dynamic programming approach for trinomial lattice. The node D has three outgoing branches to nodesA, B, and C with probability pu, pm, and pd, respectively. Vy denotes the option value for any node (y). The length of each time step is denoted as Δt. In the dynamic programming approach, the value VD can be computed by the following backward induction formula: VD=e−rΔtpuVA+pmVB+pdVC, where r is the risk-free interest rate.The pricing result is the value of the root of the lattice computed recursively by the aforementioned formula. This naive pricing method takes at leastOn2 time as there are On2 nodes in the n-time-step KRL model. When pricing barrier options, one must consider not only the stock price but also other path-dependent variables; thus, the dynamic programming approach is more complex, and the order of computational time complexities could be higher than two [4, 35].Instead of evaluating the option value of each node, the combinatorial approach improves efficiency by grouping stock price paths with the same payoff and calculating their contribution to the option value. DefineG as the set of all possible stock paths from time step 0 to time step n. If we define πk,z as a subset of G that contains price paths with n−k middle movements, x≡k−z upward movements, and z downward movements, then the set of subsets {πk,z|0≤z≤k≤n} forms a partition of G. Thus, the theoretical value of a polynomial option can be expressed as(9)e−rTEpayoff=∑τ∈Gprobτpayoffτ=∑πk,zπk,zpuk−zpmn−kpdzmaxAS0uk−zdz−X,0,where payoffτ denotes the payoff corresponding to path τ at maturity and(10)πk,z=nn−kkz,denotes the number of paths in the subset πk,z. The second equality is based on the fact that the probability of each path in πk,z is puk−zpmn−kpdz and the payoff of each path in πk,z is the same as maxAS0uk−zdz−X,0. The following sections will show how to evaluate equation (9) in linear time of n. Moreover, similar techniques plus the reflection principle can also be applied to develop On time pricing algorithms for barrier options.


### 2.7. Reflection Principle on the KRL Trinomial Lattice Model

The reflection principle efficiently counts the number of paths that hit a specific price level before reaching a certain node at maturity in the KRL model. This principle is essential when pricing barrier options using combinatorial methods. In contrast to applying the reflection principle on the binomial lattice to price barrier options in the study by Dai et al. [3] and Lyuu [17], this study extends their work to the trinomial lattice. The grid in Figure 5 represents the structure of the KRL model, where x and y-axes denote the time step and the stock price level, respectively. Each node i,j can move to node i+1,j+1 (upward movement), node i+1,j (middle movement), or node i+1,j−1 (downward movement) at the next time step. The reflection principle can help us count the number of paths from node A0,−a to node Bn,−b that hit the barrier H. Without loss of generality, we assume that a, b≥ 0. Consider one such path, AJB^, that hits barrier H at node J for the first time. We can reflect the path AJ^ with respect to barrier H to obtain A1J^ (the dashed path). Each path from node A to node J maps to a unique path from node A1 to node J and vice versa. Thus, the number of paths from node A to node J equals the number of paths from node A1 to node J. As a result, the desired number of paths moving from node A to node B and hitting barrier H equals the number of paths from node A1 to node B. This is the celebrated reflection principle.Figure 5
Reflection principle on trinomial lattice. The reflection principle can be applied to the trinomial lattice; it asserts that the number of paths that hit barrier H before arriving at node B from node A is equal to the number of paths from nodeA1 to node B.Suppose the number of upward and downward movements isx and z, respectively, and the sum of upward and downward movements is k (given the number of middle movements to be n−k). Thereby,(11)x+z=k,z−x=a+b.The first equation is from the definition ofx, z, and k, and the second equation ensures that the number of downward movements exceeds the number of upward movements by a+b, which is the distance in y-axis between node A1 and node B. By solving the aforementioned system of equations for x and z, we have(12)x=k−a+b2,z=k+a+b2.Thus, the number of paths that hit barrierH before arriving node B from A and that have n−k middle movements is(13)nn−kkx=nn−kkk−a+b2,where kk−a+b/2≡0 if k−a+b/2 is not a nonnegative integer. Thus, the total number of paths hitting barrier H before arriving B from A is(14)∑k=0nnn−kkk−a+b2.


## 2.1. Basic Framework

### 2.1.1. Stock Price Process

Suppose an option initiates at time 0 and matures at timeT. Let St denote the stock price at time t, where 0≤t≤T. In addition, this study adopts the most common assumption for the St process on option pricing, which states that under the risk-neutral measure, St follows a log-normal diffusion process with drift μ=r−σ2/2 (this paper takes a non-dividend-paying stock for example. It is straightforward to extend our model to consider a stock paying a continuously compounding dividend yield) and volatility σ, where r is the risk-free rate.


### 2.1.2. Kamrad and Ritchken Lattice (KRL) Model

Kamrad and Ritchken [5] proposed a trinomial lattice model, as shown in Figure 1(b). Denote Δt=T/n as the length of each time step. The KRL model parameterizes upward and downward multiplication factors u and d as(1)u=eλσΔt,d=u−1,where λ is the stretch parameter that can be adjusted to fit the option’s specification to alleviate the oscillation problem. To ensure that the trinomial lattice matches the drift (μ) and volatility (σ) of the stock price process, Kamrad and Ritchken set the upward, middle, and downward branching probabilities pu, pm, and pd as(2)ρu=12λ2+μΔt2λσ,pm=1−1λ2,pd=12λ2−μΔt2λσ.According to Ritchken [19], the oscillation problem can be significantly reduced by causing the lattice to coincide with a certain price level Y. Following this idea, we define λ as(3)λ=1.224745,ifY=S0orYis not available,InY/S0/σΔtInY/S0/σΔt,otherwise.Note that whenY=S0 (there must be a stock price layer coinciding with Y) or Y is not available (there is no specific level in the option contract to fit), we follow Kamrad and Ritchken [5] in setting λ as 1.224745, such that all branching probabilities converge to 1/3 when n⟶∞, which streamlines convergence for pricing options.


## 2.1.1. Stock Price Process

Suppose an option initiates at time 0 and matures at timeT. Let St denote the stock price at time t, where 0≤t≤T. In addition, this study adopts the most common assumption for the St process on option pricing, which states that under the risk-neutral measure, St follows a log-normal diffusion process with drift μ=r−σ2/2 (this paper takes a non-dividend-paying stock for example. It is straightforward to extend our model to consider a stock paying a continuously compounding dividend yield) and volatility σ, where r is the risk-free rate.


## 2.1.2. Kamrad and Ritchken Lattice (KRL) Model

Kamrad and Ritchken [5] proposed a trinomial lattice model, as shown in Figure 1(b). Denote Δt=T/n as the length of each time step. The KRL model parameterizes upward and downward multiplication factors u and d as(1)u=eλσΔt,d=u−1,where λ is the stretch parameter that can be adjusted to fit the option’s specification to alleviate the oscillation problem. To ensure that the trinomial lattice matches the drift (μ) and volatility (σ) of the stock price process, Kamrad and Ritchken set the upward, middle, and downward branching probabilities pu, pm, and pd as(2)ρu=12λ2+μΔt2λσ,pm=1−1λ2,pd=12λ2−μΔt2λσ.According to Ritchken [19], the oscillation problem can be significantly reduced by causing the lattice to coincide with a certain price level Y. Following this idea, we define λ as(3)λ=1.224745,ifY=S0orYis not available,InY/S0/σΔtInY/S0/σΔt,otherwise.Note that whenY=S0 (there must be a stock price layer coinciding with Y) or Y is not available (there is no specific level in the option contract to fit), we follow Kamrad and Ritchken [5] in setting λ as 1.224745, such that all branching probabilities converge to 1/3 when n⟶∞, which streamlines convergence for pricing options.


## 2.2. Polynomial Option

One major contribution of this study is the pricing of polynomial options—which do not have closed-form solutions unless polynomial payoffs satisfy some restricted criteria [31, 32]—with the trinomial lattice model in linear time. A general payoff form is considered as(4)Payoff=maxAST−X,0,where ST denotes the stock price on the maturity date T, and AST can be any polynomial function defined as AST≡α1STq1+α2STq2+⋯+αDSTqD, where αi’s can be any real numbers and qi’s are the nonidentical real numbers. Typically, the AST−X curve may intersect the ST-axis several times as shown in Figure 3. Consequently, there may be several separate regions that can generate positive payoffs, such as regions i, ii, and iii in Figure 3.Figure 3
Illustration of payoff function of polynomial option. This figure shows that the holder of this polynomial option can receive a positive payoff ifST belongs to regions i, ii, or iii, which in this paper are termed positive-payoff regions. Each positive-payoff region can be represented by a closed interval λl,λu; therefore, regions i, ii, and ii can be represented by 0,λ1, λ2,λ3, and λ4,∞, respectively.


## 2.3. Power Option

A power option grants the holder a right to buy or sell the power of the stock price for the exercise priceX at the maturity date T. On the other hand, the holder can junk the call option (or the put option) if the power of the stock price is lower (or higher) than the exercise price X at time T. The payoff of a power option can be defined as(5)Payoff=maxθSTq−θX,0,where q can be any real number and θ equals 1 for call options and −1 for put options.


## 2.4. Vanilla Option

A vanilla option, a special case of the power option by settingq=1, is a standard option without unusual features. The payoff for a vanilla option at time T is(6)Payoff=maxθST−θX,0,where θ equals 1 for call options and −1 for put options. Since the payoff function of the polynomial option can accommodate the payoffs of the power and vanilla options as special cases, it is straightforward to employ our combinatorial pricing algorithm for the polynomial option to evaluate these two options. Moreover, to alleviate the oscillation problem when pricing power and vanilla options, the KRL lattice requires a price level that coincides with X (i.e., Y=X in equation (3)) [23].


## 2.5. Barrier Option

A barrier option is an option whose payoff depends on whether the stock price path ever hits a certain price levelH called a barrier. Our study focuses on “up-and-in” barrier options; the extension to other types of barrier options is straightforward. Furthermore, we consider the case of H>S0 for convenience. Thus, an “up-and-in” barrier option can only be exercised at maturity when the stock price path has risen to hit the barrier during the option life. Define Ssup=sup0≤t≤TSt. The payoff function for a barrier option at time T is(7)Payoff=maxθST−θX,0,ifSsup≥H,0,otherwise,where θ equals 1 for call options and −1 for put options.To alleviate the oscillation problem, Ritchken [19] suggests that a price level of the lattice should coincide with the barrier H (i.e., Y=H in equation (3)).


## 2.6. Option Pricing Based on the KRL Model

The theoretical value of an option equals the discounted expected payoff of the option under the risk-neutral measure:(8)e−rTEpayoff.The above formula can be evaluated via dynamic programming by computing the option value of each node on the lattice model from time stepn back to time step 0. Take the polynomial option, for example. The value of each node at maturity can be evaluated by equation (4). In Figure 4, the examined node, say D, has three descendant nodes, say A, B, and C. Define Vy as the option value for any node y. The value VD of nodes other than the nodes at maturity can be computed by following backward induction formula.Figure 4
Dynamic programming approach for trinomial lattice. The node D has three outgoing branches to nodesA, B, and C with probability pu, pm, and pd, respectively. Vy denotes the option value for any node (y). The length of each time step is denoted as Δt. In the dynamic programming approach, the value VD can be computed by the following backward induction formula: VD=e−rΔtpuVA+pmVB+pdVC, where r is the risk-free interest rate.The pricing result is the value of the root of the lattice computed recursively by the aforementioned formula. This naive pricing method takes at leastOn2 time as there are On2 nodes in the n-time-step KRL model. When pricing barrier options, one must consider not only the stock price but also other path-dependent variables; thus, the dynamic programming approach is more complex, and the order of computational time complexities could be higher than two [4, 35].Instead of evaluating the option value of each node, the combinatorial approach improves efficiency by grouping stock price paths with the same payoff and calculating their contribution to the option value. DefineG as the set of all possible stock paths from time step 0 to time step n. If we define πk,z as a subset of G that contains price paths with n−k middle movements, x≡k−z upward movements, and z downward movements, then the set of subsets {πk,z|0≤z≤k≤n} forms a partition of G. Thus, the theoretical value of a polynomial option can be expressed as(9)e−rTEpayoff=∑τ∈Gprobτpayoffτ=∑πk,zπk,zpuk−zpmn−kpdzmaxAS0uk−zdz−X,0,where payoffτ denotes the payoff corresponding to path τ at maturity and(10)πk,z=nn−kkz,denotes the number of paths in the subset πk,z. The second equality is based on the fact that the probability of each path in πk,z is puk−zpmn−kpdz and the payoff of each path in πk,z is the same as maxAS0uk−zdz−X,0. The following sections will show how to evaluate equation (9) in linear time of n. Moreover, similar techniques plus the reflection principle can also be applied to develop On time pricing algorithms for barrier options.


## 2.7. Reflection Principle on the KRL Trinomial Lattice Model

The reflection principle efficiently counts the number of paths that hit a specific price level before reaching a certain node at maturity in the KRL model. This principle is essential when pricing barrier options using combinatorial methods. In contrast to applying the reflection principle on the binomial lattice to price barrier options in the study by Dai et al. [3] and Lyuu [17], this study extends their work to the trinomial lattice. The grid in Figure 5 represents the structure of the KRL model, where x and y-axes denote the time step and the stock price level, respectively. Each node i,j can move to node i+1,j+1 (upward movement), node i+1,j (middle movement), or node i+1,j−1 (downward movement) at the next time step. The reflection principle can help us count the number of paths from node A0,−a to node Bn,−b that hit the barrier H. Without loss of generality, we assume that a, b≥ 0. Consider one such path, AJB^, that hits barrier H at node J for the first time. We can reflect the path AJ^ with respect to barrier H to obtain A1J^ (the dashed path). Each path from node A to node J maps to a unique path from node A1 to node J and vice versa. Thus, the number of paths from node A to node J equals the number of paths from node A1 to node J. As a result, the desired number of paths moving from node A to node B and hitting barrier H equals the number of paths from node A1 to node B. This is the celebrated reflection principle.Figure 5
Reflection principle on trinomial lattice. The reflection principle can be applied to the trinomial lattice; it asserts that the number of paths that hit barrier H before arriving at node B from node A is equal to the number of paths from nodeA1 to node B.Suppose the number of upward and downward movements isx and z, respectively, and the sum of upward and downward movements is k (given the number of middle movements to be n−k). Thereby,(11)x+z=k,z−x=a+b.The first equation is from the definition ofx, z, and k, and the second equation ensures that the number of downward movements exceeds the number of upward movements by a+b, which is the distance in y-axis between node A1 and node B. By solving the aforementioned system of equations for x and z, we have(12)x=k−a+b2,z=k+a+b2.Thus, the number of paths that hit barrierH before arriving node B from A and that have n−k middle movements is(13)nn−kkx=nn−kkk−a+b2,where kk−a+b/2≡0 if k−a+b/2 is not a nonnegative integer. Thus, the total number of paths hitting barrier H before arriving B from A is(14)∑k=0nnn−kkk−a+b2.


## 3. Linear-Time Algorithms for Evaluating Summations in Option Pricing Formulae

Trinomial lattice option pricing formulae such as equation (9) can be expressed in terms of a linear combination of summations ∑k=cnωk, where ωk follows certain forms (introduced later) and c is a nonnegative integer smaller than n, the number of time steps in the lattice model. These summations can be evaluated in linear time (i.e., in On time) if the first term ωc can be evaluated in On time and each following term (i.e., ωk for c<k≤n) can be iteratively evaluated in O1 time. The aforementioned linear-computation property is the main idea to construct our linear-time option pricing algorithms. Define the set F to contain all the sequences (e.g., ωk) that have this linear-computation property. The following proofs show that the series expressed in certain forms (this will be used to develop pricing algorithms later) belong to F.Lemma 1.
DefineVk as βnkαk, where β can be evaluated in On time, α is a real number, and k is a nonnegative running integer variable. Then, the sequence Vk belongs to the set F.Proof.
SupposeVc=βncαc=βn!/c!n−c!αc is the first term of the sequence Vk, where c is a nonnegative integer smaller than n. Then, Vc can be evaluated in On time since β, n!, c!, n−c!, and αc can all be evaluated in On time. In addition, each following term Vk can be iteratively computed in O1 time by the recurrence formula Vk=Vk−1αn−k+1/k for c<k≤n. Consequently, we can obtain Vk∈F, and thus, ∑k=cnVk can be evaluated in On time.Lemma 2.
Defineωk≡Vk∑z=0Mkkzazbk−z, where k and z are the nonnegative running integer variables, a and b are the real-number constants, and Mk is a nonnegative integer-valued function. Then, the following formula holds:(15)Vk∑z=1Mkk+1zazbk+1−z=b+aωk−Vkk0a0bk+1−VkkMkaMk+1bk−Mk.Proof.
First,bωk and aωk can be expressed as(16)bωk=Vk∑z=0Mkkzazbk+1−z=Vkk0a0bk+1+Vk∑z=1Mkkzazbk+1−z.(17)aωk=Vk∑z=0Mkkzaz+1bk−z=Vk∑z=0Mk−1kzaz+1bk−zVkkMkaMk+1bk−Mk.
The sum of the second term in equation (16) and the first term in equation (17) can be simplified as(18)Vk∑z=1Mkkzazbk+1−z+Vk∑z=0Mk−1kzaz+1bk−z=Vk∑z=1Mkkzazbk+1−z+Vk∑z=1Mkkz−1azbk−z−1=Vk∑z=1Mkkz+kz−1azbk−z+1=Vk∑z=1Mkk+1zazbk−z+1,where the third equality is due to the combinatorial addition identity. Thus,(19)b+aωk=Vkk0a0bk+1+Vk∑z=1Mkk+1zazbk−z+1+VkkMkaMk+1bk−Mk.
As a result, Lemma2 can be obtained by rewriting the above formula.
The following theorems and corollaries show that the summation in certain formats can be evaluated inOn time, which is useful for deriving linear-time combinatorial option pricing algorithms.Theorem 1.
If the sequenceVk∈F, then the sequence ωk defined in Lemma 2 also belongs to F under the premise that Mk+1−Mk=1, that is, ∑k=cnωk can be evaluated in On time given that c is a nonnegative integer smaller than n.Proof.
To show thatωk∈F, we first prove that the first term of the sequence, ωc=Vc∑z=0Mcczazbc−z, can be evaluated in On time. This can be achieved by showing that the sequence δz≡czazbc−z, the terms in the summation, belongs to F. Since δ0=c0a0bc−0=bc can be evaluated in On time and δz=δz−1c−z+1/za/b suggests that each δz can be evaluated in O1 time given δz−1 is known, we can infer that δz∈F. Thus, ωc=Vc∑z=0Mcczazbc−z=Vc∑z=0Mcδz can be evaluated in On time since both Vc and ∑z=0Mcδz can be evaluated in On time.
The next task is to expressωk+1 in terms of ωk, such that ωk+1 can be iteratively computed in O1 time given the value of ωk. Rewrite ωk+1 as(20)ωk+1=Vk+1∑z=0Mk+1k+1zazbk+1−z=Vk+1VkVk∑z=0Mk+1k+1zazbk+1−z=Vk+1VkVkk+10a0bk+1+Vk∑z=1Mkk+1zazbk+1−z+Vkk+1Mk+1aMk+1bk−Mk.
By replacingVk∑z=1Mkk+1zazbk+1−z with Lemma 2, ωk+1 can be expressed in terms of ωk as(21)ωk+1=Vk+1VkVkk+10a0bk+1+b+aωk−Vkk0a0bk+1−VkkMkaMk+1bk−Mk+Vkk+1Mk+1aMk+1bk−Mk=Vk+1Vkb+aωk+VkkMkk−MkMk+1aMk+1bk−Mk=Vk+1Vkb+aωk+Vk+1kMkk−MkMk+1aMk+1bk−Mk.
Define functionsf1 and g1 as(22)f1k=Vk+1Vkb+a,g1k=Vk+1kMkk−MkMk+1aMk+1bk−Mk=g1k−1Vk−1VkakMk+1.
Then, we havef1k∈F, since Vk∈F and each f1k can be parallelly evaluated in constant time during the calculation of Vk+1 given Vk. Following the same logic, g1k∈F because given g1k−1, g1k can be evaluated in constant time in parallel when evaluating Vk+1 given Vk.
Sinceωk+1 can be expressed in terms of ωk as(23)ωk+1=f1kωk+g1k,∑k=cnωk can be computed in On time through equation (23) by evaluating f1k and g1k in parallel.
In the following corollaries, we consider the different integer-valued functionMk and show the resulting sequence ωk∈F.Corollary 1.
∑k=cnωk can be computed in On time when Mk+1−Mk=0.Proof.
Similarly,ωk+1 can be expressed as equation (20) except that Mk+1=Mk:(24)ωk+1=Vk+1VkVk∑z=0Mkk+1zazbk+1−z=Vk+1VkVkk+10a0bk+1+Vk∑z=1Mkk+1zazbk+1−z.
By replacingVk∑z=1Mkk+1zazbk+1−z with the formula in Lemma 2, ωk+1 can be further expressed as(25)ωk+1=Vk+1VkVkk+10a0bk+1+b+aωk−Vkk0a0bk+1−VkkMkaMk+1bk−Mk=Vk+1Vkb+aωk−Vk+1kMkaMk+1bk−Mk.
Defineg2k to be a function as follows:(26)g2k=Vk+1kMkaMk+1bk−Mk=g2k−1Vk+1Vkbkk−Mk.
Clearly,g2k∈F since Vk∈F and g2k can be evaluated in constant time given g2k−1 in parallel with the calculation of Vk+1 given Vk. Since ωk+1 can be expressed in terms of ωk as(27)ωk+1=f1kωk−g2k,∑k=cnωk can be computed in On time via equation (27) by parallelly evaluating f1k and g2k.Corollary 2.
∑k=cnωk can be computed in On time when Mk+1−Mk= 0 or 1 (Note that the value Mk+1−Mk is determined by the nonnegative integral running variable k. It is not a random variable).Proof.
Sincef1k, g1k, g2k∈F, and the first term of ωk and ωc, can be evaluated in On time as mentioned in Theorem 1, each following term ωk+1 (note that k+1>c.) can be recursively evaluated from the precedent term ωk in O1 time by equation (21) or (23) if Mk+1−Mk= 1 or 0, respectively. Thus, ∑k=cnωk can be computed in On time.Theorem 2.
LetVk belonging to F, k, and z be the nonnegative running integer variables, a and b be the real-number constants, and both Mk and mk be the nonnegative integer-valued functions with the properties Mk+1−Mk=0 or 1 and mk+1−mk=0 or 1. Then, a more general series ω′k with the definition ω′k≡Vk∑z=mkMkkzazbk−z belongs to F, given that c is a nonnegative integer smaller than n.Proof.
We can rewriteω′k as(28)ω′k=Vk∑z=0Mkkzazbk−z−Vk∑z=0mk−1kzazbk−z.
We next defineωMk≡Vk∑z=0Mkkzazbk−z and ωmk≡Vk∑z=0mk−1kzazbk−z, since both ∑k=cnωMk and ∑k=cnωmk can be evaluated in On time by specifying the upper bounds of the running variable z to be Mk and mk−1 in Theorem 1 (including Corollary 1 and 2), respectively. As a consequence, ∑k=cnω′k can be evaluated in On time and ω′k∈F.


### 3.1. Combinatorial Option Pricing Algorithms

We will first develop a linear-time pricing algorithm for polynomial options (with the payoff in equation (4)) by calculating the discounted expected payoffs with the aforementioned theorems and corollaries. Since power and vanilla options are special cases of polynomial options (their payoffs are shown in equations (5) and (6), respectively), our pricing algorithm for polynomial options can be easily extended to price power options or vanilla options. In addition, the reflection principle on the KRL trinomial lattice is applied to price barrier options. Our algorithms focus on call options; the extension to put options is straightforward.


## 3.1. Combinatorial Option Pricing Algorithms

We will first develop a linear-time pricing algorithm for polynomial options (with the payoff in equation (4)) by calculating the discounted expected payoffs with the aforementioned theorems and corollaries. Since power and vanilla options are special cases of polynomial options (their payoffs are shown in equations (5) and (6), respectively), our pricing algorithm for polynomial options can be easily extended to price power options or vanilla options. In addition, the reflection principle on the KRL trinomial lattice is applied to price barrier options. Our algorithms focus on call options; the extension to put options is straightforward.


## 4. Linear-Time Algorithm for Polynomial Options on the KRL Model

For convenience, we first introduce useful notation for developing our combinatorial pricing algorithm. On the KRL trinomial lattice,S0, u, and d≡u−1 denote the initial stock price, the upward and the downward multiplication factors, respectively. In addition, each price path is described with n−k middle movements, x=k−z upward movements, and z downward movements; thus the corresponding stock price at maturity is S0uk−zdz=S0uk−2z, for 0≤z≤k≤n. As a consequence, there are a total of 2n+1 attainable stock prices at maturity listed from the highest to the lowest as follows: S0un,S0un−1,…,S0u0,S0u−1,…,S0u−n. Thus, we number the stock price layer from n to –n according to the exponent of u of the attainable stock prices at maturity. Finally, we identify the stock price layer cl and cu that makes S0ucl,S0ucu a largest interval bracketed by a positive-payoff region λl,λu through the following formulae:(29)cl=lnλl/S0lnu,cu=lnλu/S0lnu.Note that neithercl nor cu can be less than –n or greater than n since the highest and the lowest stock prices attainable at maturity are S0un and S0u−n, respectively. Therefore, to ensure that equation (29) is well-defined under all scenarios, two extreme cases are considered in our model: if 0≤λl≤S0u−n, cl is set to –n, and if S0un≤λu<∞, cu is set to n.Next, we classify each positive-payoff region of a polynomial option into one of the following three cases:λl<λu≤S0, S0≤λl<λu, and λl<S0<λu. For each case, we can develop a combinatorial algorithm to evaluate the option value contributed by the positive-payoff region in linear time of n. Thus, the total value of a polynomial option can also be evaluated in linear time of n by accumulating the option values contributed by all positive-payoff regions.Case 1.
λl<λu≤S0
We first derive the constraints for the price paths that end up in the positive-payoff region. Due to the conditionsλl<λu≤S0, the corresponding price layers c1l and c1u can be derived based on equation (29), and should satisfy −n≤c1l≤c1u≤0. Since the stock price at maturity ST can be expressed as S0uk−zdz=S0uk−2z, and ST must be within the range S0uc1l,S0uc1u, we derive the first constraint for k and z as(30)c1l≤k−2z≤c1u⇒k−c1u2≤z≤k−c1l2.
In addition, since the number of downward movementsz should be no less than 0 and no larger than the sum of the numbers of upward and downward movements, k, we derive the second constraint for k and z as 0≤z≤k. Finally, a stock price path should have at least −c1u downward movements to ensure that ST≤S0uc1u; thus the sum of the numbers of upward and downward movements, k, should be no less than −c1u and no larger than the number of time steps, n, i.e., −c1u≤k≤n, which is the third constraint. The option value contributed from the positive-payoff region λl,λu can be expressed as the sum of the values contributed by the stock price paths that satisfy the above three constraints as(31)e−rT∑k=−c1lnnn−kpmn−k∑z=Uk,c1uLk,c1lkzpuk−zpdzpayoffS0uk−zdz+e−rT∑k=−c1u−c1l−1nn−kpmn−k∑z=Uk,c1ukkzpuk−zpdzpayoffS0uk−zdz,where(32)Lk,c≡k−c2,Uk,c≡k−c2,and payoffS0uk−zdz denotes the payoff of the polynomial option given that the maturity stock price is S0uk−zdz.Case 2.
S0≤λl<λu
According to the conditionS0≤λl<λu and the definitions in equation (29), we can obtain the stock price layers c2l and c2u corresponding to λl and λu, respectively, and they should satisfy 0≤c2l≤c2u≤n. Similar to Case 1, we can derive three constraints for k and z as k−c2u/2≤z≤k−c2l/2, 0≤z≤k, and c2l≤k≤n. As a consequence, the option value contributed from the region λl,λu can again be expressed as the sum of the values contributed by the paths that satisfy the above three constraints as(33)e−rT∑k=c2unnn−kpmn−k∑z=Uk,c2uLk,c2lkzpuk−zpdzpayoffS0uk−zdz+e−rT∑k=c2lc2u−1nn−kpmn−k∑z=0Lk,c2lkzpuk−zpdzpayoffS0uk−zdz.Case 3.
λl<S0<λu
Sinceλl<S0<λu, the corresponding stock price layers c3l and c3u derived from equation (29) should satisfy −n≤c3l≤0≤c3u≤n. Next, we simply decompose the positive-payoff region into two parts: one includes the stock price layers from c3l to –1 and the other includes the stock price layers from 0 to c3u. The first part can be evaluated as Case 1 by setting c1u as –1 and c1l as c3l, and the second part can be evaluated as Case 2 by setting c2u as c3u and c2l as 0. Finally, the option value contributed from region λl,λu can be evaluated as the sum of the values contributed by the aforementioned two parts.
To show the efficiency of our algorithm, we next prove that Case1 and Case 2 can be evaluated in linear time of n. Note that this implies that Case 3 can be evaluated in linear time since Case 3 can be expressed as a combination of Case 1 and Case 2. The value of a polynomial option is simply the sum of the values contributed by all positive-payoff regions and thus can be evaluated in linear time of n. Our proofs take advantage of Theorems 1 and 2 developed in Section 3.
The linear-time pricing algorithm for each positive-payoff region can be proved by showing that equations (31) and (33) can both be evaluated in linear time of n. We first show that the second summation term in equation (33) can be evaluated in linear time according to Theorem 1. The polynomial payoff of this term can be decomposed into the sum of its D+1 component terms as(34)e−rT∑k=c2lc2u−1nn−kpmn−k∑z=0Lk,c2lkzpuk−zpdzpayoffS0uk−zdz=∑k=c2lc2u−1w1k+∑k=c2lc2u−1w2k+⋯+∑k=c2lc2u−1wDk−∑k=c2lc2u−1φk,where(35)wik=e−rTnn−kpmn−k∑z=0Lk,c2lkzpuk−zpdzαiS0uk−zdzqi=αiS0qie−rTnn−kpmn−k∑z=0Lk,c2lkzuqipuk−zdqipdz,for 1≤i≤D, and(36)φk=Xe−rTnn−kpmn−k∑z=0Lk,c2lkzpuk−zpdz.
Note that each of the (D+1) summation terms in equation (34) can be evaluated in On time. Specifically, ∑k=c2lc2u−1wik can be evaluated in On time according to Theorem 1 by setting a=dqipd,b=uqipu,Vk=αiS0qie−rTnn−kpmn−k=αiS0qie−rTpmnnkpm−1k, (According to Lemma 1, Vk∈F can be obtained by setting β=αiS0qie−rTpmn and α=pm−1) and Mk=Lk,c2l. In addition, ∑k=c2lc2u−1φk also can be evaluated in linear time by setting a=pd,b=pu,Vk=Xe−rTnn−kpmn−k=Xe−rTpmnnkpm−1k, (According to Lemma 1, Vk∈F can be obtained by setting β=Xe−rTpmn and α=pm−1.) and Mk=Lk,c2l in Theorem 1. As a result, the second summation term in equation (33) can be evaluated in linear time of n.
For both of the first summation terms in equations (31) and (33), since the lower bounds for the index z are integer-valued functions of another running variable k rather than constants, Theorem 2 is used to prove that they can be evaluated in linear time of n. We set Mk=Lk,cil and mk=Uk,ciu, for i=1,2, and then mimic the method to evaluate equation (34) by specifying the appropriate terms for a, b, and Vk to evaluate each component term in the polynomial payoff in linear time with Theorem 2. Similarly, for the second summation terms in equation (31), we set Mk=k, mk=Uk,c1u, and a, b, and Vk to appropriate terms and next apply Theorem 2 to evaluate each component term in the polynomial payoff in linear time of n.
As a result, each of the four summation terms in equation (31) of Case 1 and equation (33) of Case 2 can be evaluated in linear time of n. Therefore, Case 3 can be evaluated in linear time of n as well. Since the option value of any polynomial option contributed from each positive-payoff region can be computed as either Case 1, 2, or 3 in linear time of n, the total value of any polynomial option can be obtained in On time with our combinatorial pricing algorithm. Thus our approach is more efficient than other lattice models, which price polynomial options in at least On2 time.
Note that the above algorithm is quite general and able to price not only polynomial options but also power and vanilla call or put options inOn time. To the best of our knowledge, this paper is also the first in the literature to obtain On-time combinatorial pricing algorithms for polynomial, power, and vanilla options on the trinomial lattice model.


### 4.1. Linear-Time Algorithm for Barrier Options on the KRL Model

Pricing a barrier option is much more complex than pricing a polynomial option since the barrier option is a path-dependent option and can be exercised only if the stock price has hitH during the life of the option. To mitigate the oscillation problem when pricing barrier options on the trinomial lattice model, the parameter λ in equation (3) is adjusted by setting Y=H, such that the barrier H can coincide with a layer of the lattice, as shown in Figure 6. Before introducing our combinatorial algorithm, we first define h=lnH/S0/lnu to be the number of net upward movements needed to reach H from S0 and also define c=mini|i∈Z,S0ui≥X where S0uc can represent the lowest stock price layer which is above or coinciding with the strike price X. In the following paragraphs, our linear-time algorithm for barrier options discusses two different cases regarding the relation between the strike price X and the barrier H.Figure 6
KRL model placed on grid for pricing barrier options. The KRL model drawn in solid lines is placed on a dashed line grid, wherex-axis represents the stock price layer that coincides with barrier H and y-axis represents time step 0. The coordinates of root S0 and node B are 0,−h and n,−h+k−2z, respectively.Case 4.
X≥H
In this case, a positive payoff (i.e.,maxST−X,0>0) at maturity guarantees the hit on barrier H during the option life, so the barrier option degenerates into a vanilla option. The reason behind this phenomenon is explained as follows.(37)e−rTEpayoff=e−rTEmaxST−X,01Ssup≥H=e−rTEST−X1ST>X1Ssup≥H=e−rTEST−X1ST>X=e−rTEmaxST−X,0=value of a vanilla call option,where the first equality is the combination of equations (7) and (9). Since Ssup≥ST is true by definition and X≥H holds in Case 4, ST>X implies Ssup≥H. Thus, the second equality can be reduced to the third one. As a consequence, the barrier option in the case of X≥H can be priced by the algorithm for the vanilla option.Case 5.
X<H
In this case, the option value can be further decomposed into two parts: the value contributed by the terminal nodes aboveH (inclusive) and the value contributed by the terminal nodes between H (exclusive) and X (The value contributed by the nodes below X is not taken into account since the option payoff at these nodes is 0.).
First, consider a terminal node, sayA in Figure 6, above or equal to the barrier H. Note that all price paths reaching node A must also hit the barrier H. Thus, the payoff for this kind of node is the same as the payoff for the vanilla call, i.e., maxST−X,0. Furthermore, since X<H≤ST in this case, the payoff for nodes above H can be simplified to be ST−X. In addition, for those paths reaching a node above H (inclusive), we have S0uk−2z≥S0uh, which implies(38)k−2z≥h⇒z≤k−h2⇒z≤k−h2=Lk,h,where the third inequality is due to the fact that z is an integer and the last equality is according to the definition in equation (31). In addition, since the number of downward movements z is a nonnegative integer, the number of the sum of the upward and downward movements k should satisfy(39)k=x+z≥z+h+z≥h.
Thereby, the option value contributed by these terminal nodes is(40)e−rT∑k=hnnn−kpmn−k∑z=0Lk,hkzpuk−zpdzS0uk−2z−X,where the lower bound of the first summation is from equation (39) and the upper bound of the second summation is from equation (38).
Next, we employ Corollary1 to develop an On-time algorithm for evaluating equation (40), which can be rewritten as(41)∑k=hnωk−∑k=hnφk,where(42)ωk=S0e−rTnn−kpmn−k∑z=0Lk,hkzupuk−zdpdz,φk=Xe−rTnn−kpmn−k∑z=0Lk,hkzpuk−zpdz.
The summation term,∑k=cnωk, can be evaluated in On time through Corollary 2 by setting a=dpd,b=upu,Vk=S0e−rTnn−kpmn−k=S0e−rTpmnnkpm−1k, and Mk=Lk,h, where Vk can be proved to belong to F through Lemma 1 by setting β=S0e−rTpmn and α=pm−1. Similarly, the summation term, ∑k=cnφk, can be evaluated in On time through Corollary 2 by setting a=pd,b=pu,Vk=Xe−rTnn−kpmn−k=Xe−rTpmnnkpm−1k, and Mk=Lk,h. Note that Vk∈F can be proved using Lemma 1 by setting β=Xe−rTpmn and α=pm−1.
Second, consider terminal nodes that are below the barrierH (exclusive) but above or equal to X, like node B in Figure 6. For those terminal nodes, they should satisfy S0uc≤S0uk−2z<S0uh. Therefore, a pair of upper and lower bounds for z can be derived as(43)c≤k−2z<h⇒k−c2≥z>k−h2⇒k−c2≥z≥k−h2+1⇒Lk,c≥z≥Lk,h+1.
In addition, for a price path that first reaches the barrierH (which takes h upward movements) and then falls below the barrier at maturity (which takes at least 1 downward movement), the sum of the number of downward movements and upward movements, k, should satisfy(44)k≥h+1.
Moreover, in order to hitH during the option life, the number of upward movements, x, must be larger than h, which suggests another constraint for z:(45)x≥h⇒k−z≥h⇒z≤k−h.
Finally, the number of paths, which starts from the root node, hits the barrierH during the option life, and reaches the terminal node below the barrier H that can be computed by the reflection principle mentioned in equation (13). Note that in Figure 6, the root of the lattice is h step lower than H (i.e., a=h in Figure 5) and the vertical distance between the terminal node and the root is k−2z; thus, the y-coordinate for node B is −h+k−2z, which implies b=h−k−2z in Figure 5. The number of the paths that satisfy the aforementioned constraints can be obtained by substituting a and b into equation (13) to get nn−kkk−z−h. Thus, the option value contributed by the terminal nodes that are below the barrier H but above or equal to X is(46)e−rT∑k=h+1nnn−kpmn−k∑z=Lk,h+1mink−h,Lk,ckk−z−hpuk−zpdzS0uk−zdz−X,where the lower bound of the first summation is from equation (44) and the lower and upper bounds of the second summation are from equations (43 and 45), respectively.
To evaluate equation (46) in On time, the first step is to substitute j for k−z−h, and then, we can rewrite equation (46) by employing j as the running variable for the inner summation. Because(47)Lk,h+1≤z≤mink−h,Lk,c⇒maxh−k,−Lk,c≤−z≤−Lk,h−1⇒k−h+maxh−k,−Lk,c≤k−z−h≤k−h−Lk,h−1⇒k−h−Lk,c+≤j≤Uk,h−1,where Uk,h=k−h/2, equation (46) can be rewritten as(48)e−rTupuhdpd−h∑k=h+1nnn−kpmn−k∑j=k−h−Lk,c+Uk,h−1kjpujpdk−jS0ujdk−j−e−rTpuhpd−h∑k=h+1nnn−kpmn−k∑j=k−h−Lk,c+Uk,h−1kjpujpdk−jX≡∑k=h+1nωk−∑k=h+1nφk,where(49)ωk=S0e−rTupuhdpd−hnn−kpmn−k∑j=k−h−Lk,c+Uk,h−1kjupujdpdk−j,φk=Xe−rTpuhpd−hnn−kpmn−k∑j=k−h−Lk,c+Uk,h−1kjpujpdk−j.
The first term in equation (48), ∑k=h+1nωk, can be evaluated in On time through Theorem 2 by setting a=upu,b=dpd,Vk=S0e−rTupuhdpd−hnn−kpmn−k, Mk=Uk,h−1, and mk=k−h−Lk,c+. Note that Vk∈F can be proved via Lemma 1 by rewriting Vk=S0e−rTupuhdpd−hpmnnkpm−1k and setting β=S0e−rTupuhdpd−hpmn and α=pm−1.
Similarly, the second term∑k=h+1nφk can be evaluated in On time through Theorem 2 by setting a=pu, b=pd, Vk=Xe−rTpuhpd−hnn−kpmn−k, Mk=Uk,h−1, and mk=k−h−Lk,c+. Again, Vk∈F can be proved by Lemma 1 by rewriting Vk=Xe−rTpuhpd−hpmnnkpm−1k and setting β=Xe−rTpuhpd−hpmn and α=pm−1. Thereby, equations (48) and (46) can be evaluated in On time.
The price of the barrier option of Case5 is the sum of equations (40) and (46). We hereby propose an On-time algorithm to price barrier options on the KRL model.


## 4.1. Linear-Time Algorithm for Barrier Options on the KRL Model

Pricing a barrier option is much more complex than pricing a polynomial option since the barrier option is a path-dependent option and can be exercised only if the stock price has hitH during the life of the option. To mitigate the oscillation problem when pricing barrier options on the trinomial lattice model, the parameter λ in equation (3) is adjusted by setting Y=H, such that the barrier H can coincide with a layer of the lattice, as shown in Figure 6. Before introducing our combinatorial algorithm, we first define h=lnH/S0/lnu to be the number of net upward movements needed to reach H from S0 and also define c=mini|i∈Z,S0ui≥X where S0uc can represent the lowest stock price layer which is above or coinciding with the strike price X. In the following paragraphs, our linear-time algorithm for barrier options discusses two different cases regarding the relation between the strike price X and the barrier H.Figure 6
KRL model placed on grid for pricing barrier options. The KRL model drawn in solid lines is placed on a dashed line grid, wherex-axis represents the stock price layer that coincides with barrier H and y-axis represents time step 0. The coordinates of root S0 and node B are 0,−h and n,−h+k−2z, respectively.Case 4.
X≥H
In this case, a positive payoff (i.e.,maxST−X,0>0) at maturity guarantees the hit on barrier H during the option life, so the barrier option degenerates into a vanilla option. The reason behind this phenomenon is explained as follows.(37)e−rTEpayoff=e−rTEmaxST−X,01Ssup≥H=e−rTEST−X1ST>X1Ssup≥H=e−rTEST−X1ST>X=e−rTEmaxST−X,0=value of a vanilla call option,where the first equality is the combination of equations (7) and (9). Since Ssup≥ST is true by definition and X≥H holds in Case 4, ST>X implies Ssup≥H. Thus, the second equality can be reduced to the third one. As a consequence, the barrier option in the case of X≥H can be priced by the algorithm for the vanilla option.Case 5.
X<H
In this case, the option value can be further decomposed into two parts: the value contributed by the terminal nodes aboveH (inclusive) and the value contributed by the terminal nodes between H (exclusive) and X (The value contributed by the nodes below X is not taken into account since the option payoff at these nodes is 0.).
First, consider a terminal node, sayA in Figure 6, above or equal to the barrier H. Note that all price paths reaching node A must also hit the barrier H. Thus, the payoff for this kind of node is the same as the payoff for the vanilla call, i.e., maxST−X,0. Furthermore, since X<H≤ST in this case, the payoff for nodes above H can be simplified to be ST−X. In addition, for those paths reaching a node above H (inclusive), we have S0uk−2z≥S0uh, which implies(38)k−2z≥h⇒z≤k−h2⇒z≤k−h2=Lk,h,where the third inequality is due to the fact that z is an integer and the last equality is according to the definition in equation (31). In addition, since the number of downward movements z is a nonnegative integer, the number of the sum of the upward and downward movements k should satisfy(39)k=x+z≥z+h+z≥h.
Thereby, the option value contributed by these terminal nodes is(40)e−rT∑k=hnnn−kpmn−k∑z=0Lk,hkzpuk−zpdzS0uk−2z−X,where the lower bound of the first summation is from equation (39) and the upper bound of the second summation is from equation (38).
Next, we employ Corollary1 to develop an On-time algorithm for evaluating equation (40), which can be rewritten as(41)∑k=hnωk−∑k=hnφk,where(42)ωk=S0e−rTnn−kpmn−k∑z=0Lk,hkzupuk−zdpdz,φk=Xe−rTnn−kpmn−k∑z=0Lk,hkzpuk−zpdz.
The summation term,∑k=cnωk, can be evaluated in On time through Corollary 2 by setting a=dpd,b=upu,Vk=S0e−rTnn−kpmn−k=S0e−rTpmnnkpm−1k, and Mk=Lk,h, where Vk can be proved to belong to F through Lemma 1 by setting β=S0e−rTpmn and α=pm−1. Similarly, the summation term, ∑k=cnφk, can be evaluated in On time through Corollary 2 by setting a=pd,b=pu,Vk=Xe−rTnn−kpmn−k=Xe−rTpmnnkpm−1k, and Mk=Lk,h. Note that Vk∈F can be proved using Lemma 1 by setting β=Xe−rTpmn and α=pm−1.
Second, consider terminal nodes that are below the barrierH (exclusive) but above or equal to X, like node B in Figure 6. For those terminal nodes, they should satisfy S0uc≤S0uk−2z<S0uh. Therefore, a pair of upper and lower bounds for z can be derived as(43)c≤k−2z<h⇒k−c2≥z>k−h2⇒k−c2≥z≥k−h2+1⇒Lk,c≥z≥Lk,h+1.
In addition, for a price path that first reaches the barrierH (which takes h upward movements) and then falls below the barrier at maturity (which takes at least 1 downward movement), the sum of the number of downward movements and upward movements, k, should satisfy(44)k≥h+1.
Moreover, in order to hitH during the option life, the number of upward movements, x, must be larger than h, which suggests another constraint for z:(45)x≥h⇒k−z≥h⇒z≤k−h.
Finally, the number of paths, which starts from the root node, hits the barrierH during the option life, and reaches the terminal node below the barrier H that can be computed by the reflection principle mentioned in equation (13). Note that in Figure 6, the root of the lattice is h step lower than H (i.e., a=h in Figure 5) and the vertical distance between the terminal node and the root is k−2z; thus, the y-coordinate for node B is −h+k−2z, which implies b=h−k−2z in Figure 5. The number of the paths that satisfy the aforementioned constraints can be obtained by substituting a and b into equation (13) to get nn−kkk−z−h. Thus, the option value contributed by the terminal nodes that are below the barrier H but above or equal to X is(46)e−rT∑k=h+1nnn−kpmn−k∑z=Lk,h+1mink−h,Lk,ckk−z−hpuk−zpdzS0uk−zdz−X,where the lower bound of the first summation is from equation (44) and the lower and upper bounds of the second summation are from equations (43 and 45), respectively.
To evaluate equation (46) in On time, the first step is to substitute j for k−z−h, and then, we can rewrite equation (46) by employing j as the running variable for the inner summation. Because(47)Lk,h+1≤z≤mink−h,Lk,c⇒maxh−k,−Lk,c≤−z≤−Lk,h−1⇒k−h+maxh−k,−Lk,c≤k−z−h≤k−h−Lk,h−1⇒k−h−Lk,c+≤j≤Uk,h−1,where Uk,h=k−h/2, equation (46) can be rewritten as(48)e−rTupuhdpd−h∑k=h+1nnn−kpmn−k∑j=k−h−Lk,c+Uk,h−1kjpujpdk−jS0ujdk−j−e−rTpuhpd−h∑k=h+1nnn−kpmn−k∑j=k−h−Lk,c+Uk,h−1kjpujpdk−jX≡∑k=h+1nωk−∑k=h+1nφk,where(49)ωk=S0e−rTupuhdpd−hnn−kpmn−k∑j=k−h−Lk,c+Uk,h−1kjupujdpdk−j,φk=Xe−rTpuhpd−hnn−kpmn−k∑j=k−h−Lk,c+Uk,h−1kjpujpdk−j.
The first term in equation (48), ∑k=h+1nωk, can be evaluated in On time through Theorem 2 by setting a=upu,b=dpd,Vk=S0e−rTupuhdpd−hnn−kpmn−k, Mk=Uk,h−1, and mk=k−h−Lk,c+. Note that Vk∈F can be proved via Lemma 1 by rewriting Vk=S0e−rTupuhdpd−hpmnnkpm−1k and setting β=S0e−rTupuhdpd−hpmn and α=pm−1.
Similarly, the second term∑k=h+1nφk can be evaluated in On time through Theorem 2 by setting a=pu, b=pd, Vk=Xe−rTpuhpd−hnn−kpmn−k, Mk=Uk,h−1, and mk=k−h−Lk,c+. Again, Vk∈F can be proved by Lemma 1 by rewriting Vk=Xe−rTpuhpd−hpmnnkpm−1k and setting β=Xe−rTpuhpd−hpmn and α=pm−1. Thereby, equations (48) and (46) can be evaluated in On time.
The price of the barrier option of Case5 is the sum of equations (40) and (46). We hereby propose an On-time algorithm to price barrier options on the KRL model.


## 5. Experimental Results

In this section, we compare our linear-time combinatorial algorithms with the standard backward induction procedure (which is indeed the dynamic programming approach mentioned above) for pricing polynomial, vanilla, and barrier options on the KRL trinomial lattice. The results demonstrate the superiority of our combinatorial model in terms of efficiency and accuracy.Since there is no simple closed-form pricing formula for polynomial options, it is necessary to price them numerically. However, pricing polynomial options via dynamic programming suffer from slow convergence, and thus, a large number ofn is required. Figure 7 shows the comparison of the running time between our On-time trinomial combinatorial approach and the On2-time dynamic programming approach. The x and y-axes denote the logarithmic values of n and running time, respectively. The slopes of linear regression formulae denote the estimations for the order of time complexities. Note that the combinatorial approach (slope=0.896) is much more efficient than the dynamic programming approach (slope=1.894). Moreover, we compare the convergence rates of absolute pricing errors for binomial and trinomial lattices, as shown in Figure 8. Our trinomial lattice generates smaller absolute pricing errors and shows a faster convergence rate than the CRR binomial lattice for pricing polynomial options. To further confirm the stable and fast convergence of our combinatorial algorithm, Figure 9 shows comprehensive sensitivity analyses for the polynomial option analyzed in Figure 7. The absolute pricing errors for the combinatorial approaches based on both the binomial and trinomial lattices are much smaller than the dynamic programming approach on the trinomial lattice and the explicit finite difference method (The implementation issues about applying the finite difference and Fourier transform methods to price polynomial options are discussed in Appendix.) for different settings of the risk-free rates r, stock price volatilities σ, times to maturity T, exercise prices X, and payoff functions. In addition, the combinatorial approach based on the trinomial lattice performs better than that on the binomial one in terms of less oscillations, as shown in Figure 10.Figure 7
Time complexity for pricing polynomial options. This figure is a log-log plot of the running time versus the number of time steps. The solid and dashed lines denote the combinatorial and the dynamic programming approaches, respectively. The linear regression formulae are listed next to the lines. The initial stock price is 5, the exercise price is 5, the risk-free rate is 10% per annum, the volatility of the stock price is 25%, and the time to maturity (T) is one year. The payoff of the examined polynomial option is maxST4−22ST3+179ST2−638ST+845−X,0. The results demonstrate that our combinatorial approach successfully reduces the time complexity for pricing polynomial options on the trinomial lattice to On time, comparing to the On2-time complexity of the dynamic programming approach.Figure 8
Convergence of absolute pricing errors for pricing polynomial options. The black dots indicate the pricing errors generated by our trinomial lattice, and the gray triangles represent the pricing errors of the CRR binomial lattice. The benchmark option price, 10.8856, is generated by the CRR binomial lattice with a very largen = 10,000. All parameters are identical to those in Figure 7. The trinomial lattice adopted in this study converges faster than the CRR binomial lattice does for pricing polynomial options.Figure 9
Sensitivity analyses for polynomial options. Thex and y-axes represent the running time and the absolute pricing error, respectively. The black and light gray thin curves denote the pricing errors generated by the combinatorial algorithms based on the KRL trinomial and CRR binomial lattice, respectively. The dark gray and light gray thick curves indicate the pricing errors generated by the dynamic programming approach on the CRR binomial lattice and explicit finite difference method. All parameters in (a)–(h) are identical to those in Figure 7 except the parameters specified in the legend. Specifically, the risk-free rates (r) in (a) and (b) are set to 5% and 15%; the volatilities of the stock price σ in (c) and (d) is 20% and 30%; the times to maturity (T) in (e) and (f) are 0.5 and 1.5 years; the exercise prices (X) in (g) and (h) are 2.5 and 7.5, respectively. The benchmark option value for each parameter setting is listed on the top right corner of each subfigure. (a) r = 5%. (b) r = 15%. (c) σ = 20%. (d) σ = 30%. (e) T = 0.5. (f) T = 1.5. (g) X = 2.5. (h) X = 7.5.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 10
Convergence oscillations for pricing polynomial options. Thex-axis and y-axis represent the running time and the absolute pricing error, respectively. The black and light-gray curves denote the pricing errors generated by the combinatorial algorithms based on the KRL trinomial and CRR binomial lattice, respectively. The dark-gray thick curves indicate the pricing errors generated by the dynamic programming approach on the KRL trinomial lattice. The payoff function for the polynomial option is specified as maxST−0.7XST−1.3X−5000,0, where the initial stock price S0, the exercise price X, the risk-free rate r, the time to maturity T, and the volatility of the stock price σ are set to 50, 50, 10%, 0.5 years, and 40%, respectively. The benchmark option value for each parameter setting is listed on the top right corner of the figure.A vanilla option is a special case of a polynomial option, and its value can be analytically evaluated by the Black–Scholes formula [36]. With this property, we can analyze the pricing errors generated by our combinatorial algorithm. Figure 11 shows the comparison of the absolute pricing errors and running times between the dynamic programming approach and the combinatorial approach for pricing vanilla call options. The x and y-axes denote the running time and absolute pricing errors, respectively. The results show that the absolute pricing errors of the combinatorial approach decrease more smoothly and rapidly than the dynamic programming approach.Figure 11
Comparison of absolute pricing error versus running time for pricing vanilla call options. For the examined vanilla call option, the initial stock price is 90, the exercise price is 100, the risk-free rate is 10% per annum, the volatility of the stock price is 25%, and the time to maturity is 1 year. The benchmark option price is obtained based on Black and Scholes [36]. The black line indicates the absolute pricing errors of our combinatorial approach, and the gray line represents the absolute pricing errors of the dynamic programming approach. The right-hand side diagram is a more detailed illustration for the running time shorter than 0.003 seconds. Compared with the dynamic programming approach, our combinatorial approach shows more rapidly decreasing errors and smoother convergence behavior.Figure12 shows the relation between the running time and the number of time steps n for our combinatorial and dynamic programming approaches on pricing up-and-in barrier call options. The x and y-axes denote the values after taking the logarithm of the number of time steps and for the corresponding running time, respectively. The regression formula for the dynamic programming approach is y=2.039x−7.591, whereas the regression formula for the combinatorial approach is y=0.971x−5.938. The slope of the dynamic programming approach is twice as high as that of the combinatorial one. These results again demonstrate that we successfully reduce the time complexity of pricing barrier options on the trinomial lattice from On2 by the dynamic programming approach to On by this novel trinomial combinatorial approach. Figure 13 shows the comparison of the absolute pricing errors versus running time for pricing up-and-in barrier call options between the binomial combinatorial approach and the trinomial combinatorial and dynamic programming approaches based on the KRL trinomial lattice. The binomial combinatorial approach is the linear-time pricing algorithm developed in Dai et al. [3] based on the CRR binomial lattice. Even equipped with this efficient linear-time binomial combinatorial approach, the oscillation problem is clearly more pronounced than the other two trinomial lattice-based models. Moreover, the trinomial combinatorial approach converges faster and more smoothly than the trinomial lattice dynamic programming approach and the binomial combinatorial approach in terms of running time.Figure 12
Time complexity comparison of pricing up-and-in barrier call options. This figure represents the log-log plot of the running time versus the number of time steps. The solid and dashed lines denote the results for the combinatorial approach and the dynamic programming approach, respectively. The linear regression formulae are listed next to the lines. The initial stock price is 90, the exercise price is 85, the higher barrier is 95, the risk-free rate is 10% per annum, the volatility of the stock price is 25%, and the time to maturity is 1 year. The results demonstrate that our combinatorial approach successfully reduces the time complexity for pricing barrier options on the trinomial lattice toOn time, whereas the time complexity of the dynamic programming approach is On2.Figure 13
Comparison of absolute pricing error versus running time for pricing up-and-in barrier call options. The black and gray solid lines indicate the absolute errors of our combinatorial approach and the dynamic programming approach based on the KRL trinomial lattice. The dotted line represents the absolute errors of the linear-time binomial lattice combinatorial approach proposed in the study by Dai et al. [3]. The benchmark option price is derived based on Rich [20] and Rubinstein and Reiner [21]. All parameters are the same as those in Figure 12. The right-hand side diagram is a more detailed illustration for the running time shorter than 0.005 seconds. The oscillation problem of the binomial combinatorial approach is more pronounced than those of the other two trinomial lattice-based models. Moreover, our trinomial combinatorial approach shows most rapidly decreasing errors and smoothest convergence behavior among the three models.Note that the analyses in Figure2 demonstrate that the pricing results of the binomial combinatorial approach are more inclined to oscillate and less accurate than those of the trinomial combinatorial approach in terms of both the number of time steps and running time. These comparisons between binomial and trinomial combinatorial approaches support the necessity and contribution of proposing combinatorial option pricing approaches based on the trinomial lattice in this study.


## 6. Conclusion

Although the trinomial lattice framework for option pricing has been shown to provide better convergence behavior than the binomial lattice framework, only the dynamic programming approach, whose complexity is at leastOn2 time, has been developed under the trinomial lattice framework to price options. This study proposes a novel combinatorial approach to reduce the time complexity for pricing options on the trinomial lattice of Kamrad and Ritchken [5]. The notion is to decompose the complex option payoff functions into certain regular summation forms, which can be evaluated in On time by simple recursive formulae. We successfully develop On-time pricing algorithms for a wide range of options which require at least On2 time when priced by the original dynamic programming approach.



---

*Source: 5843491-2022-05-21.xml*