# Chapter 7, part 5 of 6: tree-based lattices

Welcome back.

This week’s content is the fifth part of the series on the QuantLib tree framework which started in this post.

A bit of self promotion: Quants Hub has
modified its pricing structure so that all workshops are now sold at
£99. This includes my *A Look at QuantLib Usage and
Development* workshop, which
I hope is now affordable for a lot more people. It’s six hours of
videos, so it should be a decent value for that money. (But if you
want to see me in person instead, come to London from June 29th to
July 1st for my *Introduction to QuantLib Development* course. Details
are at this
link. You’re
still in time for an early-bird discount.)

Follow me on Twitter if you want to be notified of new posts, or add me to your circles, or subscribe via RSS: the buttons for that are in the footer. Also, make sure to check my Training page.

### The *TreeLattice* class template

After the last couple of posts on trees, we’re now back to
lattices. The `TreeLattice`

class, shown in the listing below,
inherits from `Lattice`

and is used as a base class for lattices that
are implemented in terms of one or more trees. Of course, it should be
called `TreeBasedLattice`

instead; the shorter name was probably
chosen before we discovered the marvels of automatic
completion—or English grammar.

This class template acts as an adapter between the `Lattice`

class,
from which it inherits the interface, and the `Tree`

class template
which will be used for the implementation. Once again, we used the
Curiously Recurring Template Pattern (which wasn’t actually needed for
trees, but it is in this case); the behavior of the lattice is written
in terms of a number of methods that must be defined in derived
classes. For greater generality, there is no mention of trees in the
`TreeLattice`

class. It’s up to derived classes to choose what kind of
trees they should contain and how to use them.

The `TreeLattice`

constructor is simple enough: it takes and stores
the time grid and an integer `n`

specifying the order of the tree (2
for binomial, 3 for trinomial and so on). It also performs a check or
two, and initializes a couple of data members used for caching data;
but I’ll gloss over that here.

The interesting part is the implementation of the `Lattice`

interface,
which follows the outline I gave back in the first post on this
framework. The `initialize`

method calculates the index of the passed
time on the stored grid, sets the asset time, and finally passes the
number of nodes on the corresponding tree level to the asset’s `reset`

method. The number of nodes is obtained by calling the `size`

method
through CRTP; this is one of the methods that derived classes will
have to implement, and (like all other such methods) has the same
signature as the corresponding method in the tree classes.

The `rollback`

and `partialRollback`

methods perform the same work,
with the only difference that `rollback`

performs the adjustment at
the final time and `partialRollback`

doesn’t. Therefore, it’s only to
be expected that the one is implemented in terms of the other;
`rollback`

performs a call to `partialRollback`

, followed by another
to the asset’s `adjustValues`

method.

The rollback procedure is spelled out in `partialRollback`

: it finds
the indexes of the current time and of the target time on the grid,
and it loops from one to the other. At each step, it calls the
`stepback`

method, which implements the actual numerical work of
calculating the asset values on the `i`

-th level of the tree from
those on level `i+1`

; then it updates the asset and, at all steps
except the last, calls its `adjustValues`

method.

The implementation of the `stepback`

method defines, by using it, the
interface that derived classes must implement (that’s currently the
only sane way, since concepts were left out of C++11). It determines
the value of the asset at each node by combining the values at each
descendant node, weighed by the corresponding transition probability;
the result is further adjusted by discounting it. All in all, the
required interface includes the `size`

method, which I’ve already
shown; the `probability`

and `descendant`

methods, with the same
signature as the tree methods of the same name; and the `discount`

method, which takes the indexes of the desired level and node and
returns the discount factor between that node and its descendants
(assumed to be independent of the particular descendant).

Finally, the `presentValue`

method is implemented by returning the
dot-product of the asset values by the state prices at the current
time on the grid. I’ll cheerfully ignore the way the state prices are
calculated; suffice it to say that using them is somewhat more
efficient than rolling the asset all the way back to \( t=0 \).

Now, why does the `TreeLattice`

implementation calls methods with the
same signature as those of a tree (thus forcing derived classes to
define them) instead of just storing a tree and calling its methods
directly? Well, that’s the straightforward thing to do if you have
just an underlying tree; and in fact, most one-dimensional lattices
will just forward the calls to the tree they store. However, it
wouldn’t work for other lattices (say, two-dimensional ones); and in
that case, the wrapper methods used in the implementation of
`stepback`

allow us to adapt the underlying structure, whatever that
is, to their common interface.

The library contains instances of both kinds of
lattices. Most—if not all—of those of the straightforward
kind inherit from the `TreeLattice1D`

class template, shown in the
listing below.

It doesn’t define any of the methods required by `TreeLattice`

; and
the method it does implement (the `grid`

method, defined as pure
virtual in the `Lattice`

base class) actually requires another one,
namely, the `underlying`

method. All in all, this class does little
besides providing a useful categorization; the storage and management
of the underlying tree is, again, left to derived classes. (One might
argue for including a default implementation of the required methods
in `TreeLattice1D`

. This would probably make sense; it would make it
easier to implement derived classes in the most common cases, and
could be overridden if a specific lattice needed it.)

One such class is the inner `OneFactorModel::ShortRateTree`

class,
shown in the next listing.

Its constructor takes a trinomial tree, built by any specific
short-rate model according to its dynamics; an instance of the
`ShortRateDynamics`

class, which I’ll gloss over; and a time grid,
which could have been extracted from the tree so I can’t figure out
why we pass it instead. The grid is passed to the base-class
constructor, together with the order of the tree (which is 3, of
course); the tree and the dynamics are stored as data members.

As is to be expected, most of the required interface is implemented by
forwarding the call to the corresponding tree method. The only
exception is the `discount`

method, which doesn’t have a corresponding
tree method; it is implemented by asking the tree for the value of its
underlying value at the relevant node, by retrieving the short rate
from the dynamics, and by calculating the corresponding discount
factor between the time of the node and the next time on the grid.

Note that, by modifying the dynamics, it is possible to change the
value of the short rate at each node while maintaining the structure
of the tree unchanged. This is done in a few models in order to fit
the tree to the current interest-rate term structure; the
`ShortRateTree`

class provides another constructor, not shown here,
that takes additional parameters to perform the fitting procedure.

As an example of the second kind of lattice, have a look at the
`TreeLattice2D`

class template, shown in the listing below. It acts as
base class for lattices with two underlying variables, and implements
most of the methods required by `TreeLattice`

. (In this, it differs
from `TreeLattice1D`

which didn’t implement any of them. We might have
had a more symmetric hierarchy by leaving `TreeLattice2D`

mostly empty
and moving the implementation to a derived class. At this time,
though, it would sound a bit like art for art’s sake.)

The two variables are modeled by correlating the respective trees. Now, I’m sure that any figure I might draw would only add to the confusion. However, the idea is that the state of the two variables is expressed by a pair of node from the respective trees; that the transitions to be considered are those from pair to pair; and that all the possibilities are enumerated so that they can be retrieved by means a single index and thus can match the required interface.

For instance, let’s take the case of two trinomial trees. Let’s say we’re at level \( i \) (the two trees must have the same time grid, or all bets are off). The first variable has a value that corresponds to node \( j \) on its tree, while the second sits on node \( k \). The structure of the first tree tells us that on next level, the first variable might go to nodes \( j’_0 \), \( j’_1 \) or \( j’_2 \) with different probabilities; the second tree gives us \( k’_0 \), \( k’_1 \) and \( k’_2 \) as target nodes for the second variable. Seen as transition between pairs, this means that we’re at \( (j,k) \) on the current level and that on the next level we might go to any of \( (j’_0,k’_0) \), \( (j’_1,k’_0) \), \( (j’_2,k’_0) \), \( (j’_0,k’_1) \), \( (j’_1,k’_1) \), and so on until \( (j’_2,k’_2) \) for a grand total of \( 3 \times 3 = 9 \) possibilities. By enumerating the pairs in lexicographic order like I just did, we can give \( (j’_0,k’_0) \) the index \( 0 \), \( (j’_1,k’_0) \) the index \( 1 \), and so on until we give the index \( 8 \) to \( (j’_2,k’_2) \). In the same way, if on a given level there are \( n \) nodes on the first tree and \( m \) on the second, we get \( n \times m \) pairs that, again, can be enumerated in lexicographic order: the pair \( (j,k) \) is given the index \( k \times n + j \).

At this point, the implementation starts making sense. The constructor
of `TreeLattice2D`

takes and stores the two underlying trees and the
correlation between the two variables; the base-class `TreeLattice`

constructor is passed the time grid, taken from the first tree, and
the order of the lattice, which equals the product of the orders of
the two trees; for two trinomial trees, this is \( 3 \times 3 = 9 \)
as above. (The current implementation assumes that the two trees are
of the same type, but it could easily be made to work with two trees
of different orders.) The constructor also initializes a matrix `m_`

that will be used later on.

The size of the lattice at a given level is the product \( n \times m
\) of the sizes of the two trees, which translates in a
straightforward way into the implementation of the `size`

method.

Things get more interesting with the two following methods. The
`descendant`

method takes the level `i`

of the tree; the index of the
lattice node, which is actually the index of a pair \( (j,k) \)
among all those available; and the index of the branch to take, which
by the same token is a pair of branches. The first thing it does is to
extract the actual pairs. As I mentioned, the passed index equals \(
k \times n + j \), which means that the two underlying indexes can be
retrieved as `index%n`

and `index/n`

. The same holds for the two
branches, with \( n \) being replaced by the order of the first
tree. Having all the needed indexes and branches, the code calls the
`descendant`

method on the two trees, obtaining the indexes \( j’ \)
and \( k’ \) of the descendant nodes; then it retrieves the size \(
n’ \) of the first tree at the next level; and finally returns the
combined index \( k’ \times n’ + j’ \).

Up to a certain point, the `probability`

method performs the same
calculations; that is, until it retrieves the two probabilities from
the two underlying trees. If the two variables were not correlated,
the probability for the transition would then be the product of the
two probabilities. Since this is not the case, a correction term is
added which depends from the passed correlation (of course) and also
from the chosen branches. I’ll gloss on the value of the correction as
I already did on several other formulas.

This completes the implementation. Even though it contains a lot more
code than its one-dimensional counterpart, `TreeLattice2D`

is still an
incomplete class. Actual lattices will have to inherit from it, close
the CRTP loop, and implement the missing `discount`

method.

I’ll close this post by mentioning one feature that is currently
missing from lattices, but would be nice to have. If you turn back to
the implementation of the `stepback`

method, you’ll notice that it
assumes that the values we’re rolling back are cash values; that is,
it always discounts them. It could also be useful to roll values back
without discounting. For instance, the probability that an option be
exercised could be calculated by rolling it back on the trees without
discounting, while adjusting it to \( 1 \) on the nodes where the
exercise condition holds.