This article introduces a new type of recombining derivative pricing, called the willow tree, as an alternative to standard binomial and trinomial trees. The motivation for this numerical technique is the following. Consider modeling a Brownian motion using a binomial tree with 100 time steps. Using this model, the nodes at maturity are spread uniformly across 20 standard deviations of the theoretical distribution of the process level. The range of nodes in a standard tree (binomial or trinomial) spreads out faster (linearly) than does the marginal probability distribution (as the square root of time). As a result, many very low probability events are included in the backward and forward induction algorithms. This inefficiency can be mitigated by "pruning" the tree, but this solves only part of the problem, and in an awkward way that is difficult to generalize to multiple factors. A more practical approach is to place the nodes in regions where they will do the most good, i.e. in the more probable regions. The problem then becomes how to connect up the nodes to form a "mathematically correct" tree. This problem can be solved using linear programming (LP), where each time step corresponds to a single LP. These LPs are solved only once, and the results are stored. (In the current implementation of the willow tree these transition probabilities take up a quite manageable 2 MB of memory.) The LP solutions ensure that the increments of the discrete process satisfy the following conditions (this is what is meant by "mathematically correct"):
1) probabilities which add to one;
2) zero drift;
3) variance equal to the length of the time step;
4) reproduce a particular discrete distribution at
each time step;
The first three conditions are standard. Condition four imposes that the unconditional distribution of the process is fixed.
Figure 1 gives a graphical depiction of a three time step willow tree with 11 nodes at each time step. This represents the solution to three linear programs, which also yield appropriate transition probabilities (not shown). Observe that, by design, the tree expands as the square root of time and that, while the number of transitions out from each node varies, on average there is four. Since the willow tree does not involve pruning, probability is conserved. Therefore accuracy can be maintained using trees of substantially lesser width.
Numerical tests comparing the performance of the willow tree with 30 nodes per time step to a standard trinomial implementation were conducted. An American put option was used for the tests with spot price 100, strike price 105, risk-free interest rate 5%, maturity one year, and with no dividends. For reference, an accurate result for the price is 8.740. Figure 2 shows the result of the test. The horizontal axis represents the maximum error for a number of time steps greater than or equal to the number that yields the corresponding CPU time. The vertical axis values (CPU time) adjust with the number of time steps taken for each tree. The numbers on the plot are the number of time steps for each tree corresponding to the CPU time. Clearly, the willow tree enjoys a very significant advantage over the trinomial tree in excess of an order of magnitude. Observe that the willow tree price estimate converges more smoothly than the trinomial estimate. If this were exploited by applying Richardson extrapolation to the number of time steps taken, the willow tree would benefit more, and the results would be even more striking.
Willow tree implementations have been developed for multiple factor equity models as well as multifactor normal and lognormal short rate models. Computation speed improvements for multifactor models tends to be even more pronounced than those for single factor models because of the relatively small number of nodes in each spatial dimension of the willow tree. Work also has been initiated on building implied willow trees which reproduce observed option prices. The advantages of the willow tree with regard to memory and computation time make real-time three-factor trading models feasible with currently available hardware.
This Learning Curve was written by Michael Curran and Zhengyun Hu of RiskCare Limited in London.
