Abstract

Derivative pricing lies at the center of modern quantitative finance, and stock-option pricing is its most fundamental form. The binomial option pricing model has found wide applications in both in equity and in fixed income derivatives pricing. This paper present a software optimization methodology that accelerates any derivative pricing application based on the binomial tree option pricing model.

Overview: Quantitative Finance and Stock Options

An option is commonly called a financial derivative, because it derives its value from the underlying asset. Put simply, an option is a contract between two parties: the option buyer and the option seller. The contract gives the buyer the right (though not the obligation) to either buy or sell a certain portion of the underlying security at a fixed price for a specific period. On the other side of the contract, the seller agrees to deliver or receive the same portion of the underlying asset for the fixed price within the same period.

The option buyer pays the option seller a pre-agreed-upon amount for this right. By definition, the amount of money that passes from option buyer to option seller is the value of the stock option. The first part of this article presents a simple way to calculate the value of a stock option through an iterative approach known as binomial tree.

Depending on the time constraints involved in exercising it, an option can be a European-style or an American-style option. European options can only be exercised on the day the contract period ends, while American options can be exercised at any time during the contact period. American options should be worth at least as much as the equivalent European options, because they are more flexible to the option buyers.

In some cases, an option can be exercised only on specific dates within the contract period. This third type, which us not as restrictive as the equivalent European option and not as flexible as an American option, is called a Bermudan option, referring to an island between the two continents. The Bermudan option is the simplest form of what’s known as exotic options. Other exotic options include Asian options, whose contracted prices are path dependent. Intel’s 1993-1998 open-market-traded Step-Up Warrant was another form of exotic option.

In this article, we start by looking at European options and then extend our methodology to cover American and Bermudan options.

Binomial Option Pricing Modeling

The binomial tree model was fist proposed by Cox, Ross and Rubenstein in 1979. It derived its name from the construction of a binomial tree that models different possible paths that might be followed by the underlying asset price over the time span of the option.

Binomial option pricing is a simple but powerful technique that can be used to solve many complex option-pricing problems. Unlike the Black-Scholes and other complex option pricing models, it does not require solutions to stochastic differential equations; the binomial option-pricing model is mathematically trivial. Anyone with a good understanding of the time value of money and risk-neutral valuation should be able to understand the binomial model.

Time value of money is based on the simple premise that any amount of money is worth more now than it will be in the future. If you are going to receive X dollars in time T, assuming a continuous compounding rate r, these X dollars are actually worth Xe-rT. In another words, to get the present value S of the future cash flow X, we have to discount X at the appropriate interest rate r .

S = Xe-rT

Risk-neutral valuation is an important general principle in the theoretical foundation of option pricing. In the risk-neutral world, investors are indifferent to risk, and they require no compensation for it. The theory argues that the expected return of all traded securities is the risk-free interest rate and that the future cash flows can be valued by discounting their expected values at the risk-free interest rate.

Consider a stock with the initial value of S0, and an option f with lifetime T. During the life of the option, the stock price can either move up from S0 to a new level, S0u where u > 1 (going up 1-u percent), or it can move down from S0 to a new level S0d where d < 1 (going down 1-d percent). Let’s suppose that when the stock price moved to S0u, the payoff from option is fu ; when the stock price moved down to S0d, the payoff from the option is fd :

Binomial valuation starts by creating a riskless portfolio consisting of a long option in Δ shares of the underlying stocks and a short position in one unit of option. When the stock moves up, the value of the portfolio becomes S0u Δ -fu; when the stock moves down, the value of the portfolio becomes S0d Δ –fd. Using no arbitrage argument, these two cases should be the equal value or:

Therefore:

The risk-neutral argument also dictates that all portfolios shall earn the risk-free interest rate. Since we know the risk-free interest r. the current value of the portfolio when the stock goes up can be written as follows:

(S0u –fu )e-rT

This must equal to the cost of setting up the portfolio:

S0Δ - f = (S0u –fu )e-rT

Thus:

f = S0Δ — (S0u –fu )e-rT

Since we know Δ. we can further reduce this equation as follows:

where:

With the last two equations, we can naturally interpret the variable p as the probability of an upward movement in the underlying stock price. Thus, 1-p is the probability of a downward movement. We can further state that the value of the option today is the expected future payoff discounted at the risk-free rate.

The last challenge in creating a binomial option-pricing algorithm is to integrate the stock-price movement process into the binomial tree parameters u and d. Using the same assumption as the Black-Scholes model; we can construct a binomial tree by using the underlying stock price volatility σ. Cox, Ross and Rubinstein (1979) proposed the following set of u and p:

These values not only match the volatility with the up and down movement of stock price but also make the binomial tree recombinant, in the sense that the nodes that represent a stock moving up then down and the stock price moving down then up will be merged or recombined as a single node. This property also spares us from the elaborated process to propagate the internal node values to the leaf nodes; instead it gives a closed-end formula for each leaf node.

Now we can easily extend the one-step binomial tree into a two-step binomial tree, three-step binomial tree, and N-step binomial tree. The previous picture shows a perfectly balanced N-step binomial tree, where each initial node has exactly two child nodes representing an upward movement and a downward movement of the stock price, respectively.

The probability of an upward movement is p and the probability of downward movement is 1-p. The N-Step binomial tree has N+1 level; each level has one less node than its previous level and one more node than its next level. The number of leaf nodes for N-Step binomial tree is N+1.

Implementation of Binomial Option Pricing Model

Now we can turn our discussion to the implementation of the binomial pricing algorithm. The input parameters to this algorithm are the current stock price S. the option strike price X. the duration of the option T. risk-free interest rate R. and annualized volatility of the stock V. Other assumptions to be made for this algorithm are the option type (whether it is call option or a put option), as well as option styles (whether it is a European or American option). As mentioned earlier, we restrict ourselves to European-style call options. The output of this algorithm is the current price of the option F .

Binomial option pricing can be conceptually described as a three-step process:

1. Binomial tree representation and generation
2. Calculation of option values at the leaf nodes
3. Backward iterative calculation of option value at internal nodes; the value at the root node is the current price of the option

Binomial tree representation and generation

The first step in choosing a binomial tree representation is to determine how deep the binomial tree would be. In another words, we need to determine how many time steps we would like to use to model the stock price between the option inception and the option expiration. Given the same option duration, the higher the number of time steps, the more accurate the option price. However, a larger number of time steps always demands higher computational power.

In our example, the number of time steps is reconfigurable and initially set to 2048.

//Number of time steps

#define NUM_STEPS 2048

The next step is to determine a data structure that can represent all the tree nodes. Since the binomial tree model involves calculations on adjacent levels, the minimum data structure required is the one that holds all the node values in one level, including the leaf nodes level, which has the number of nodes equal to the number of time steps + 1. Depending on the application precision requirement, we can choose a one-dimensional single-precision floating-point array to accomplish this purpose.

static float Call[NUM_STEPS+1];

By convention, we use Call[0] to represent the leaf node that took all the downward paths, and Call[NUM_STEPS] to represent the leaf node that took all the upward paths.

Finally, we have to initialize all the values useful in the rest of the binomial tree calculation.

const float dt = T / (float)NUM_STEPS;

const float vDt = V * sqrtf(dt);

const float rDt = R * dt;

//Per-step interest and discount factors

const float If = expf(rDt);

const float Df = expf(-rDt);

//Values and pseudoprobabilities of upward and downward moves

const float u = expf(vDt);

const float d = expf(-vDt);

const float pu = (If — d) / (u — d);

const float pd = 1.0f — pu;

const float puByDf = pu * Df;

const float pdByDf = pd * Df;

Calculation of option value at the leaf nodes

As mentioned before, we can use a simple analytical formula to systematically generate all leaf node stock prices. Let ST, i be the underlying stock price at option expiration in the leaf node array Call[] at index i:

Once we have the stock price at expiration T, the value of call options simply takes their intrinsic value by using a simple pay-off function of max(ST-X, 0), where X is the strike price of the option. The calculation of option value at the leaf-node array can be written as:

for(int i = 0; i <= NUM_STEPS; i++)

float d = S * expf(vDt * (2*i — NUM_STEPS)) – X;

Call[i] = (d > 0). d. 0;

Backward iterative calculation of option value at internal nodes

As we completed calculation of the option price at the leaf nodes, our next step is to propagate the stock option price from the leaf nodes to internal node, one tree level a time. At level N-1, each node, representing the option value at that time, depends on two option values of level N using the following equation:

fn-1 = e-rT[pfn,u + (1-p)fn,d ]

The backward propagation refers to the fact that the interactive calculation starts at level N-1 and ends at level 0. The code looks surprising succinct:

for(int i = NUM_STEPS; i > 0; i—)

for(int j = 0; j <= i — 1; j++)

Call[j] = puByDf * Call[j + 1] + pdByDf * Call[j];

After we propagated the option value to level 0, the root, we get the current option value:

callValue = Call[0];

The full source code can be downloaded from this web site. On Intel® Core™ i7 processor Extreme Edition-based systems running Microsoft Windows,* compiled using the Microsoft Visual Studio* 2005 compiler, it takes 28.12 seconds to complete all 1024 options. In the next paper, we demonstrate a process that enables a 180x performance gain by exploiting parallel code executions.

Conclusion: Building Binomial Option Pricing Program using the Intel® C/C++ Compiler

The first step in any optimization project is to choose an optimizing compiler. These compilers, including the Intel® C/C++ Compiler, carefully analyze source code and generate optimized object code that delivers uncompromising results on systems specified by the developer. In addition, the Intel compilers are typically first in the industry to take advantage of the most recent hardware features, such as new instruction set architectures, on Intel® processors. The Intel C/C++ compiler is compatible with Microsoft Visual Studio 2005 on Windows platforms and with the GNU Compiler Collection* on Linux.* It is also available on Mac OS X.*

In the Windows environment, you can successfully compile Binomial.cpp with the Microsoft C/C++ Compiler. using the following command line:

cl /Fe binomial /O2 binomial.cpp /link winmm.lib

To quickly improve application performance, you can switch to the Intel Compiler and compile the same application with one more letter in your command line:

icl /Fe binomial /O2 binomial.cpp /link winmm.lib

Simply invoking the executables will reveal stunning results. Visual Studio 2005 took 28.12 seconds. The Intel C/C++ Compiler version 11.0 took 0.558 seconds-a 50x improvement.

References

1. Black, F. and M. Scholes The Pricing of Options and Corporate Liabilities. Journal of Political Economy 81 (May/June 1973): 637-654.
2. Cox, J. C. S. A. Ross, and M. Rubinstein. “Option Pricing. A Simplified Approach.” Journal of Financial Economics 7 (October 1979): 229-64.
3. Hull, J.C. Options, Futures, and Other Derivatives. 7th Edition Prentice Hall, 2008 Chapter 11. 237-58.
4. Wilmott, P. Paul Wilmott Introduces Quantitative Finance. Second Edition. John Wiley & Son Ltd, 2007: Chapter 3. 59-90