Intelligent Lattice Search

In the previous page we set a few techniques that help accelerate lattice estimation. One of the downsides of using lattice relates to the computational intensity associated with running larger step sizes. European Options can be priced with minimal fuss using Black Scholes (1973). For American options however only limited progress has been made. This is an important problem in that trading houses may need to price thousands of contracts for book revaluation and VAR calculations. One therefore wishes to be able to obtain a fast accurate price in a minimal amount of time. The crucial issue for such calculations is to find a methodology that achieves a sufficiently accurate price quickly.

Our objective here is to find a fast binomial tree by examining many choices of parameters and accelerations in order to find which is fastest. Below we set out some basic VBA code that will accelerate the binomial tree framework based on our paper in the Journal of Derivatives. The intelligent lattice search algorithm is designed efficiently locate the optimal exercise boundary for American options. The VBA code below is applied to a binomial framework and incorporates intelligent lattice search, truncation, and dynamic memory. The model reduces computational runtime from over 18 minutes down to less than 3 seconds to estimate a 15,000-step binomial tree where the results obtained are consistent with a widely acclaimed literature. Lattice estimation, in general, is considered to be slow and not practical for valuing large books of options or for promptly re-balancing a risk neutral portfolio. Our technique transforms standard binomial trees and renders them to be at least on par with commonly used analytical formulae. More importantly, intelligent lattice search can be tweaked to reach varying levels of accuracy with different step size, while conventional analytical formulae are less flexible. Below, we have posted VBA code for the Cox, Ross and Rubinstein accelerated with Intelligent Lattice Search. A timer is included, so feel free to test and re-test. Both snippets of code produce identical estimates for CRR but the computational run-times are vastly different.

Public Function AccelCRR(AmeEurFlag As String, CallPutFlag As String, S As Double, X As Double, T As Double, _

r As Double, b As Double, v As Double, n As Integer) As Variant

Dim Sec1 As Double, Sec2 As Double

Sec1 = Timer

Dim OptionValue() As Double

Dim u As Double, d As Double, p As Double, dt As Double, Df As Double

Dim i As Integer, j As Integer, locate As Integer, Index As Double, _

Flag As Integer, Start As Integer, Finish As Integer, Num As Integer

ReDim OptionValue(0 To n)

dt = T / n

u = Exp(v * Sqr(dt))

d = 1 / u

p = (Exp(b * dt) - d) / (u - d)

Df = Exp(-r * dt)

Flag = 0

Num = Int((Log(X / S) / Log(u) + n) / 2)

If Num < 0 Then Num = 0 'For special condition of Call Option

If Num >= n Then Num = n - 1 'For special condition of Put Option

'Call Option

If CallPutFlag = "c" Then

'Last column

For i = 0 To n

OptionValue(i) = Application.Max(0, S * u ^ (2 * i - n) - X)

For i = Num To (n - 1)

If (S * u ^ (2 * i - (n - 1)) - X) > (p * OptionValue(i + 1) + (1 - p) * OptionValue(i)) * Df Then

Flag = 1 'early exercise exists

locate = i 'Location that first early exercise may happen in one cloumn

Index = locate

Exit For

End If

If AmeEurFlag = "e" Or Flag = 0 Then 'early exercise does not exist

For j = n - 1 To 0 Step -1

Start = Num - (n - 1 - j) 'Truncation: omit the zero area

If j < (n - Num) Then Start = 0

For i = Start To j

OptionValue(i) = (p * OptionValue(i + 1) + (1 - p) * OptionValue(i)) * Df

'early exercise does exist

ElseIf AmeEurFlag = "a" And Flag = 1 Then

For j = n - 1 To 0 Step -1

Start = Num - (n - 1 - j) 'Truncation: omit the zero area

If j < (n - Num) Then Start = 0

Finish = Application.Min(locate - 1, j) 'Exit from locate search

'Part A: No early exercise happens

For i = Start To Finish

OptionValue(i) = (p * OptionValue(i + 1) + (1 - p) * OptionValue(i)) * Df

If locate >= 0 And locate <= j Then

If (p * OptionValue(locate + 1) + (1 - p) * OptionValue(locate)) * Df >= (S * u ^ (2 * locate - j) - X) Then

OptionValue(locate) = (p * OptionValue(locate + 1) + (1 - p) * OptionValue(locate)) * Df

Else

OptionValue(locate) = (S * u ^ (2 * locate - j) - X)

Index = locate - 1 'Index is auxiliary locate

End If

'Part C: Early exercise happens

If (locate < j) Then OptionValue(locate + 1) = S * u ^ (2 * (locate + 1) - j) - X

locate = Index

'Put option

ElseIf CallPutFlag = "p" Then

'Last column

For i = 0 To n

OptionValue(i) = Application.Max(0, X - S * u ^ (2 * i - n))

For i = Num To 0 Step -1

If (X - S * u ^ (2 * i - (n - 1))) > (p * OptionValue(i + 1) + (1 - p) * OptionValue(i)) * Df Then

Flag = 1 'early exercise exists

locate = i 'Location that first early exercise may happen in one cloumn

Index = locate

Exit For

End If

'Build option tree except the zero part

If AmeEurFlag = "e" Or Flag = 0 Then 'early exercise does not exsit

For j = n - 1 To 0 Step -1

If j < Num + 1 Then Finish = j

For i = 0 To Finish

OptionValue(i) = (p * OptionValue(i + 1) + (1 - p) * OptionValue(i)) * Df

ElseIf AmeEurFlag = "a" And Flag = 1 Then 'early exercise does exist

For j = n - 1 To 0 Step -1

If j < Num + 1 Then Finish = j

Start = Application.Min(locate - 1, j) 'Exit from locate search

'Part A: Early exercise happens

If locate > 0 Then OptionValue(Start) = X - S * u ^ (2 * Start - j)

'Part B: Compare St-X and (Pu*Opt(i+1)+Pd*Opt(i))*Df

If locate >= 0 And locate <= j Then

If (p * OptionValue(locate + 1) + (1 - p) * OptionValue(locate)) * Df >= X - S * u ^ (2 * locate - j) Then

OptionValue(locate) = (p * OptionValue(locate + 1) + (1 - p) * OptionValue(locate)) * Df

Index = locate - 1 'auxiliary locate

Else

OptionValue(locate) = X - S * u ^ (2 * locate - j)

End If

'Part C: No early exercise happens

For i = locate + 1 To Finish

OptionValue(i) = (p * OptionValue(i + 1) + (1 - p) * OptionValue(i)) * Df

Else

OptionValue(0) = 0

End If

Sec2 = Timer

AccelCRR = Array(OptionValue(0), Sec2 - Sec1)

End Function

For comparison, we post a conventional static implementation of Cox, Ross and Rubinstein with timer also included below:

Function CRR(EuroAmer As String, PutCall As String, Spot, K, T, r, b, sigma, n)

Dim Sec1 As Double, Sec2 As Double

Sec1 = Timer

dt = T / n

u = Exp(sigma * (dt ^ 0.5))

d = 1 / u

p = (Exp(b * dt) - d) / (u - d)

' Tree for stock price

Dim S() As Double

ReDim S(n + 1, n + 1) As Double

S(1, 1) = Spot

For i = 1 To n + 1

For j = i To n + 1

S(i, j) = S(1, 1) * u ^ (j - i) * d ^ (i - 1)

Next j

Next i

' Calculate Terminal Price for Calls and Puts

Dim Op() As Double

ReDim Op(n + 1, n + 1) As Double

For i = 1 To n + 1

Select Case PutCall

Case "c": Op(i, n + 1) = Application.Max(S(i, n + 1) - K, 0)

Case "p": Op(i, n + 1) = Application.Max(K - S(i, n + 1), 0)

End Select

Next i

' Calculate Remaining entries for Calls and Puts

For j = n To 1 Step -1

For i = 1 To j

Select Case EuroAmer

Case "a":

If PutCall = "c" Then

Op(i, j) = Application.Max(S(i, j) - K, Exp(-r * dt) * (p * Op(i, j + 1) + (1 - p) * Op(i + 1, j + 1)))

ElseIf PutCall = "p" Then

Op(i, j) = Application.Max(K - S(i, j), Exp(-r * dt) * (p * Op(i, j + 1) + (1 - p) * Op(i + 1, j + 1)))

End If

Case "e":

Op(i, j) = Exp(-r * dt) * (p * Op(i, j + 1) + (1 - p) * Op(i + 1, j + 1))

End Select

Next i

Next j

Sec2 = Timer

CRR = Array(Op(1, 1), Sec2 - Sec1)

End Function

Intelligent Lattice Search by slide

Vinegarhill Lab Intelligent Lattice Search Algorithm.ppt