This post will look at implementing the binomial tree algorithm in an imperative style, and refactoring it to be more functional.
The wikipedia page on the binomial options pricing model provides pseudo-code for the pricing of an American Put option.
That code can be implemented almost identically in F#.
and is called as follows:
Functional programmers have probably died a little on the inside on seeing that code, but one of the good thing about F# being multi-paradigm is that it’s easy to take code of this form and implement it, and test it for correctness before refactoring.
I did actually look at whether the results of the code were as expected at this point, but I’ll cover this later in this blog post.
The first thing to do is to change the initial values V to be created more functionally:
Now, the main algorithm consists of two parts, an outer loop where each ‘level’ of the tree is calculated stepping up towards the root, using the results of the previous level’s nodes (the nodes nearest to the leaves). The inner loop iterates over all of the nodes at a given level calculating the option’s value at that node.
First off, the outer loop can be replaced with a recursive method:
The next change is quite minor – it’s for each pass of the inner loop to create a new array, instead of mutating the vi array:
This change now means that there’s no need for any mutable state, so the initial values can be created as a sequence instead of an array, and the inner loop can be written in a functional style:
I find this code style is clearer to understand than following the array mutations to see what each part of the code is doing and how those parts interact.
If I was implementing this in C# I’d probably change the variable names to be more descriptive (e.g. strikePrice, riskFreeRate etc) but as one of the key advantages of F# is its succinctness it makes more sense to leave the well-known symbols in. Anyone implementing the algorithm with knowledge of the domain would know what the symbols mean without the more verbose names.
Validating the results
The calculated option value with the requested parameters is 4.486090. Running the EqutyOptions example in the .NET port of QuantLib, QLNet (http://sourceforge.net/projects/qlnet), with the same parameters gives the following results:
The figures are in the same ballpark, but the difference is curious.
Chapter 45 of GPU GEMS 2 creates the initial values in this way:
This gives a result of 4.486375 which still doesn’t match QLNet, but is nearer.
The result of running the Cox version of Bubo’s code from here http://cs.hubfs.net/topic/None/59053 also equals 4.486375, which matches the results of using this initialisation function. As an aside, I like how that examples shows how F# partial function application allows the variations on the algorithm to be composed, and much more succinctly than using OO.
Bubo’s Tian model does match QuantLib’s result exactly. I’ll have to dig a bit deeper to figure out which variations on the binomial tree model these different examples are using.
The code is available here: https://github.com/taumuon/FSharp-Binomial-Tree