Friday, March 13, 2015

C++ Coding - Black Scholes Option Pricing - Binomial Trees

The example question for these solutions can be found on my website (click here).

5.1 Binomial Tree For Option Pricing

The two most popular models for using binomial trees to price options are

We wish to generate a stock price tree, so denote the value of the underlying asset after timestep i and upstate j by Sij and we have that:

S  =  S ujdi−j
 ij    0

First download and start with this template code:

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

/* Template code for the binomial tree
 * Instructions to build the code are here
 * http://www.maths.manchester.ac.uk/~pjohnson/Tutorials/node1.html
 */
int main()
{
  // declare and initialise Black Scholes parameters
  
  // declare and initialise tree paramaters (steps in tree)
  
  // declare and initialise local variables (u,d,p)
  
  // create storage for the stock price tree and option price tree
  
  // setup and initialise the stock price tree
  
  // setup and initialise the final conditions on the option price tree
  
  // loop through time levels, setting the option price at each node in the tree
  
  // output the estimated option price
  
}

First declare and initialise the Black Scholes parameters for your chosen problem. Here we are going to value a Black Scholes vanilla European call option with, S0 = 100, X = 100, T = 1, r = 0.06 and σ = 0.2, so declare variables for each of these. Next add in an integer to store the number of steps in the tree and call it n. Finally add in some local variable to describe the tree, so we have the timestep length dt, u, d and q. Your code should look like

  // declare and initialise Black Scholes parameters
  double S0=100.,X=100.,T=1.,r=0.06,sigma=0.2;
  // declare and initialise tree paramaters (steps in tree)
  int n=3;
  // declare and initialise local variables (u,d,q)
  double dt,u,d,q;

Then calculate the values for dt, u, d and q, using the appropriate formula, you should check the value of these against those found in my lecture notes (click here, slide 19).

Next we need to create some storage for the values of the stock at each node in the tree. Declare a vector of vectors stockTree, into which we will place our stock price nodes.

  // create storage for the stock price tree and option price tree
  vector<vector<double>> stockTree(n+1,vector<double>(n+1));

where this has been intialised to an n + 1 × n + 1 2D array, and n is the number of nodes in the tree.

Now use a for loop and the function pow to input the value of the stock at each node in the tree, where Si,j stockTree[i][j].
PIC

Now print out the vector stockTree[i][j] to the screen. Your code might look something like this

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
/* Template code for the binomial tree
 * Instructions to build the code are here
 * http://www.maths.manchester.ac.uk/~pjohnson/Tutorials/node1.html
 */
int main()
{
  // declare and initialise Black Scholes parameters
   // declare and initialise Black Scholes parameters
  double S0=100.,X=100.,T=1.,r=0.06,sigma=0.2;
  // declare and initialise tree paramaters (steps in tree)
  int n=3;
  // declare and initialise local variables (u,d,q)
  double dt,u,d,q;
  dt = T/n;
  u = exp(sigma*sqrt(dt));
  d = exp(-sigma*sqrt(dt));
  q = (exp(r*dt)-d)/(u-d);
  // create storage for the stock price tree and option price tree
  vector<vector<double>> stockTree(n+1,vector<double>(n+1));
  // setup and initialise the stock price tree
  for(int i=0;i<=n;i++)
  {
    for(int j=0;j<=i;j++)
    {
      stockTree[i][j]=S0*pow(u,j)*pow(d,i-j);
      cout << i << " " << j << " " << stockTree[i][j] << endl;
    }
    cout << endl;
  }
/** OUTPUT
0 0 100

1 0 89.0947
1 1 112.24

2 0 79.3787
2 1 100
2 2 125.978

3 0 70.7222
3 1 89.0947
3 2 112.24
3 3 141.398
*/
}

Compare the values with those from the example in the lectures.

5.2 The Option Value Tree

Let us generate a simple example so that we can compare results at every stage to something that we can work out on paper. This is an important idea in debugging, to solve the problem and do all of your bug checking on a small scale before attempting the full problem.

First declare a vector of vectors which shall hold the values of the option

  // create storage for the stock price tree and option price tree
  vector<vector<double>> valueTree(n+1,vector<double>(n+1));

and set it to the same size as stockTree. Here we use the same relation
V i,j valueTree[i][j].

Now fill in the final values of the tree, given that we have already first generated the stock tree:

Vn,j = payoff (Sn,j),
where payoff is the appropriate function for the type of option we are solving for. For a European call option you should get

  for(int j=0;j<=n;j++)
  {
    valueTree[n][j]=max(stockTree[n][j]-X,0.);
    cout << n << " " << j << " " << valueTree[n][j] << endl;
  }

Now we need to loop backwards through the tree to generate the value at each node using the equation:

Vij = e−rΔt(qVi+1,j+1 + (1 − q)Vi+1,j).
You will need to do the following.
  • Write for loops to move backwards through the vector array caculating the value of the option at each node.
  • Print out the tree to screen (with n=3) and compare to the simple example (click here, slide 19) to check your code is working.
  • If your values don’t match - try to work out why!!
  • Now print out the value at (0, 0) increasing the number of steps in the tree. Do the results look feasible? Compare them against the exact values from the formula.

Finally your code should look like this

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

/* Template code for the binomial tree
 * Instructions to build the code are here
 * http://www.maths.manchester.ac.uk/~pjohnson/Tutorials/node1.html
 */
int main()
{
  // declare and initialise Black Scholes parameters
  double S0=100.,X=100.,T=1.,r=0.06,sigma=0.2;
  // declare and initialise tree paramaters (steps in tree)
  int n=3;
  // declare and initialise local variables (u,d,q)
  double dt,u,d,q;
  dt = T/n;
  u = exp(sigma*sqrt(dt));
  d = exp(-sigma*sqrt(dt));
  q = (exp(r*dt)-d)/(u-d);
  // create storage for the stock price tree and option price tree
  vector<vector<double>> stockTree(n+1,vector<double>(n+1));
  // setup and initialise the stock price tree
  for(int i=0;i<=n;i++)
  {
    for(int j=0;j<=i;j++)
    {
      stockTree[i][j]=S0*pow(u,j)*pow(d,i-j);
    }
  }
  vector<vector<double>> valueTree(n+1,vector<double>(n+1));
  for(int j=0;j<=n;j++)
  {
    valueTree[n][j]=max(stockTree[n][j]-X,0.);
  }
  for(int i=n-1;i>=0;i--)
  {
    for(int j=0;j<=i;j++)
    {
      valueTree[i][j] = exp(-r*dt)*( q*valueTree[i+1][j+1] + (1-q)*valueTree[i+1][j]);
    }
  }
  cout << " V(S="<<S0<<",t=0) = " << valueTree[0][0] << endl;
/** OUTPUT
 V(S=100,t=0) = 11.552
 */
}

Finally, you could try to improve your code with the following

  • Create a function returning the value of the binomial tree for a set of given parameters.
  • Write a code storing two time-levels, and compare (at every stage if needed) with the previous code.
  • Is it possible to store just one time-level? Try to write a code for this.
  • Do you notice any difference (time taken for computation) between the codes with different storage requirements?

5.3 Evaluating Convergence Properties

Taking the code from last time, we can finish this off by taking the main algorithm out into a function and allowing the payoff function to be set independently. A representative code might look like the following:

#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

/* Template code for the binomial tree
 * Instructions to build the code are here
 * http://www.maths.manchester.ac.uk/~pjohnson/Tutorials/node1.html
 */

// return the payoff of the function you want to evaluate
double payoff(double S,double X)
{
  return max(S-X,0.);
}

// return the value of the binomial tree
double binomialTree(double S0,double X,double T,double r,double sigma,int n)
{
  // declare and initialise local variables (u,d,q)
  double dt,u,d,q;
  dt = T/n;
  u = exp(sigma*sqrt(dt));
  d = exp(-sigma*sqrt(dt));
  q = (exp(r*dt)-d)/(u-d);
  // create storage for the stock price tree and option price tree
  vector<vector<double>> stockTree(n+1,vector<double>(n+1));
  // setup and initialise the stock price tree
  for(int i=0;i<=n;i++)
  {
    for(int j=0;j<=i;j++)
    {
      stockTree[i][j]=S0*pow(u,j)*pow(d,i-j);
    }
  }
  vector<vector<double>> valueTree(n+1,vector<double>(n+1));
  for(int j=0;j<=n;j++)
  {
    valueTree[n][j]=payoff(stockTree[n][j],X);
  }
  for(int i=n-1;i>=0;i--)
  {
    for(int j=0;j<=i;j++)
    {
      valueTree[i][j] = exp(-r*dt)*( q*valueTree[i+1][j+1] + (1-q)*valueTree[i+1][j]);
    }
  }
  return valueTree[0][0];
}

int main()
{
  // declare and initialise Black Scholes parameters
   // declare and initialise Black Scholes parameters
  double S0=100.,X=100.,T=1.,r=0.06,sigma=0.2;
  // declare and initialise tree paramaters (steps in tree)
  int n=3;
  cout << " V(S="<<S0<<",t=0) = " << binomialTree(S0,X,T,r,sigma,n) << endl;
/** OUTPUT
 V(S=100,t=0) = 11.552
 */
}

Now we wish to investigate what happens when N is increasing. Write the following loop in your code to output some results to file, you will need to adjust the output filename depending on you preference for where the file should be saved

  // open output stream
  ofstream output("binomial-convergence.csv");
  // check it is open
  if(output.is_open())
  {
    cout << "File opened successfully" << endl;
    // output various n and V_n to file
    for(int n=3;n<=1000;n++)
    {
      output << n<<" , " << binomialTree(S0,X,T,r,sigma,n) << endl;
    }
    cout << "File write complete" << endl;
  }
  else
  {
    cout << "File could not be opened for some reason.\n";
  }
/** OUTPUT
 File opened successfully
 File write complete
 */

Run the code for S0 = 100 and X = 100 and then import the data into a ploting package and visualise the results. You should see the following pattern
PIC

The pattern can be explained by realising that the nodes at terminal time will either be placed exactly on the strike price, or above/below depending on whether the number of steps is odd or even. We will see quite a different pattern if you choose S0X, so for example set S0 = 97.3467 in your code and rerun the results. After putting this in a plotting package you should see something like this
PIC

To produce this graph I have set n = 25 as the minimum grid size to show up the pattern better. This time we see humps as well as an odd-even effect. The humps are again caused by the positioning of the grid nodes relative to the strike price. Although the convergence of the tree is O(1∕n), the humps make it very difficult to achieve high accuracy. There are several papers that try to address this, including Leisen and Reimer (1996) and Heston and Zhou (2000), whilst Joshi (2007) gives a good comparison of different methods when American options are being priced.

References

   Cox, John C, Stephen A Ross, and Mark Rubinstein. Option pricing: A simplified approach. Journal of financial Economics, 7(3):229–263, 1979.

   Heston, Steve and Guofu Zhou. On the rate of convergence of discrete-time contingent claims. Mathematical Finance, 10(1):53–75, 2000.

   Joshi, Mark S. The convergence of binomial trees for pricing the american put. Available at SSRN 1030143, 2007. URL http://fbe.unimelb.edu.au/__data/assets/pdf_file/0006/806280/170.pdf.

   Leisen, Dietmar PJ and Matthias Reimer. Binomial models for option valuation-examining and improving convergence. Applied Mathematical Finance, 3(4): 319–346, 1996.

   Rendleman, Richard J and Brit J Bartter. Two-state option pricing. The Journal of Finance, 34(5):1093–1110, 1979.

1 comment:

  1. Minimum initial down payment requirements - One must have the ability to open binary trading account in the website for free and you don't need to provide initial deposits. Binary Options Search for those binary trading platforms that supply free registrations and minimum deposits.

    ReplyDelete