Discrete Processes: Binomial Tree Model

After reading a bit from Baxter and Rennie's book about discrete processes, I decided to implement the basic binomial tree described in the book. It's a build onto the binomial branch model, in essence it's the same thing but done on a recursive scale. It is mostly used for evaluating the cost of an option via arbitrage. The main downfall to discrete process modelling computationally is that it becomes exceedingly difficult to scale it for problems of large instances. Unlike continuous processes which are evaluated through approximation, discrete processes models each tiny step and for an accurate representation would require a lot of memory and computational time.

The model suggests having a portfolio of stocks and bonds. This simple combination allows us to synthesize the derivative by replicating desired values. The key point is the probability of up and down moves from a given stock at a given time does not influence our ability to generate the desired values. For example, we can say for certainty that if the stock moved up then down and then up again we would reach our desired value f(n). We use an algebraic relation from the next stock up and down prices to determine our claim value. We evaluate the claim value from the back of the tree where the payoff/desired value is guaranteed and move our way back to our initial node. This claim value at the initial node is what we should price the option at.

Now if the market was to move up or down, we need to adjust our proportion of stocks and bonds to compensate. It's essentially like a board game, when the stock moves we make an appropriate adjustment to ensure that the next move (either up or down) is within our described tree regardless of the outcome. At the end of the time period, we are guaranteed to get the claim value for the given sequence of stock movements from t = 0 to t = n, where n is the number of time ticks (i.e. depth of the binomial tree). For more information refer to Baxter and Rennie's Financial Calculus book.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// represent the stock as a value in time
class Stock {
public:
   double price;
   double prUp;
   double prDown;
   Stock() { }
   Stock(double p, double up, double down) : price(p), prUp(up), prDown(down) { }
};

vector<double> fTable;   // represents the claim tree
vector<Stock> graph;   // represents the recombinant tree
int sz;

#define EPS 1e-09

// claims are calculated as:
//      q = (stock_now - stock_down) / (stock_up - stock_down)
//      f = q * f_up + (1 - q) * f_down
// base conditions can be computed based on valuation of the option at t=0 versus the
// payoff given a sequence of situations (when the stock goes up/down for t=0 to t=n).
double computeClaims(int node) {
   int baseNode = (sz-1) >> 1;
   if (fTable[node] >= 0) {
      // memoisation
      return fTable[node];
   }
   if (node >= baseNode) {
      // base case
      return fTable[node] = max(0.0, graph[node].price - graph[1].price);
   }
   // compute
   double q = (graph[node].price - graph[node*2+1].price) / 
      (graph[node*2].price - graph[node*2+1].price);
   fTable[node] = q * computeClaims(node*2) + (1 - q) * computeClaims(node*2+1);
   return fTable[node];
}

// define an recombinant tree and reconstruct the option value
int main() 
{
   int N;   // the depth of the tree
   cin >> N;
   graph = vector<Stock>((1 << N) + 1);
   
   // read in the recombinant tree (stated in order of time)
   // file format:
   // stockprice prUp
   // stockprice2 prUp2
   // etc.

   int totalCnt = (1 << N);
   for (int i = 0; i < totalCnt-1; i++) {
      double stockPrice, prUp, prDown;
      cin >> stockPrice >> prUp;
      prDown = 1 - prUp;
      graph[i+1] = Stock(stockPrice, prUp, prDown);
   }

   // reconstruct the option price by backtracking
   fTable = vector<double>((1 << N) + 1, -1.0);
   sz = (1 << N) + 1;
   double optionPrice = computeClaims(1);
   cout << "Option price is " << optionPrice << "\n";
   
   // run simulations (optional)
   // file format:
   //   sequence of {up, down}'s equal to N-1.
   // note: stockHolding is calculated by:
   //   s = (f_up - f_down) / (s_up - s_down)
   string status;
   string lastStatus = "-";
   int cnt = 0;
   int curTime = 0;
   double stockHolding = 0.0;
   double bondHolding = 0.0;
   int curBranch = 1;
   while (cin >> status && cnt++ <= N-1) {
      // output the status
      cout << "Time: " << curTime << " Last Jump: " << lastStatus << 
         " Stock Price: " << graph[curBranch].price << 
         " Option Value: " << fTable[curBranch] << " Stock Holding: " 
         << stockHolding << " Bond Holding: " << bondHolding << "\n";
      curTime++;
      lastStatus = status;
      stockHolding = (fTable[curBranch*2] - fTable[curBranch*2+1]) / 
         (graph[curBranch*2].price - graph[curBranch*2+1].price);
      bondHolding = fTable[curBranch] - (stockHolding * graph[curBranch].price);
      if (status == "up") {
         curBranch = (curBranch * 2);
      } else {
         curBranch = (curBranch * 2) + 1;
      }
   }
   if (cnt > 0) {
      cout << "Time: " << curTime << " Last Jump: " << lastStatus << 
         " Stock Price: " << graph[curBranch].price << 
         " Option Value: " << fTable[curBranch] << " Stock Holding: " 
         << stockHolding << " Bond Holding: " << bondHolding << "\n";
   }
   return 0;
}

With an example file input based on the book examples (pipe it in):

4
100 0.75
120 0.75
80 0.25
140 0.75
100 0.25
100 0.75
60 0.25
160 0.75
120 0.25
120 0.75
80 0.25
120 0.75
80 0.25
80 0.75
40 0.25
up
up
down