C++ Tables

1.	Introduction
2.	Binomial model
3.	Options
4.	American puts
5.	Systems of equations
6.	Matrix operations
7.	Matrix inverse

Binomial Model with C++ Tables

1. Introduction to binomial model

In the real world, the price of each stock is unpredictable. We know the current price and we use the letter $S$ or $S_0$ to denote this current price. All the future prices are random.

In binomial model we make some assumptions to significantly simplify the randomness.

Assumption 1. There are only $n$ moments in the future at which the stock price will change. These prices are denoted by $S_1$, $S_2$, $\dots$, $S_n$.

Assumption 2. There exist two positive constants $u$ and $d$ and for each moment in time $i\geq 1$, the price $S_i$ must satisfy \[S_{i}\in \left\{S_{i-1}\cdot u,S_{i-1}\cdot d\right\}.\]

2. Example

Let us consider an example in which the input values are $n=2$, $S_0=S=\$200$, $u=1.25$, $d=0.75$. Then the price $S_1$ satisfies \[S_1\in\left\{S\cdot u,S\cdot d\right\}=\left\{200\cdot 1.25,200\cdot 0.75\right\}=\{250,150\}.\] If the price $S_1$ is equal to $\$250$, then the price $S_2$ must belong to $\{312.5,187.5\}$. If the price $S_1$ is equal to $\$150$, then the price $S_2$ must belong to $\{187.5,112.5\}$. We can summarize these conclusions with the stock price tree

\begin{eqnarray*} \begin{array}{ccccc} \quad & \quad & \quad & \quad & \$312.5\\ & & & \nearrow & \quad\\ & & \$250& &\\ &\nearrow & &\searrow&\\ \$200& &&& \$187.5\\ &\searrow & & \nearrow&\\ & & \$150& &\\ & & & \searrow & \\ & & & & \$112.5 \end{array} \end{eqnarray*}

3. Stock price tree with C++ tables

3.1. Input variables

We first have to make a decision on where to put the values $n$, $S$, $u$, and $d$ in the input table A. Let's make have them all in the row 0. More specifically, let's have them in this order, i.e. n=A[0][0], S=A[0][1], u=A[0][2], and d=A[0][3].

We need to declare the variables n, S, u, and d in our C++ code. The variables S, u, and d are real numbers, so the following code should work

double S, u, d;
S=A[0][1]; u=A[0][2]; d=A[0][3];

The variable n is an integer, so its declaration is a bit different

int n;
n=A[0][0];

3.2. Data structure for stock tree

Now we need to decide on appropriate data structure for the stock tree.

At time 0, there is only one possibility for the price. That price is $S$.

At time 1, there are two possibilities: $S\cdot u$ and $S\cdot d$.

At time 2, there are three possibilities: $S\cdot u^2$, $S\cdot ud$, and $S\cdot d^2$.

Similarly, at time t, there are $t+1$ possibilities.

For each time $t\in \{0,1,\dots, n\}$, we need to store $t+1$ elements. Therefore, the data structure stock_tree has to be quite complex. For example, for time 2, the object stock_tree[2] must have three elements $S\cdot u^2$, $S\cdot ud$, and $S\cdot d^2$. In C++ we can use a vector to store there three elements. Hence, stock_tree[2] will be a vector. Its three elements will be stock_tree[2][0]$=S\cdot u^2$, stock_tree[2][1]$=S\cdot ud$, stock_tree[2][2]$=S\cdot d^2$.

We will have a lot of vectors: stock_tree[0], stock_tree[1], stock_tree[2], stock_tree[n] in order to fit all of our data. This is a visual representation of our tree:

\begin{eqnarray*} \begin{array}{ccccc} \quad & \quad & \quad & \quad & \mbox{stockTree[2][0]}\\ & & & \nearrow & \quad\\ & & \mbox{stockTree[1][0]}& &\\ &\nearrow & &\searrow&\\ \mbox{stockTree[0][0]}& &&& \mbox{stockTree[2][1]}\\ &\searrow & & \nearrow&\\ & & \mbox{stockTree[1][1]}& &\\ & & & \searrow & \\ & & & & \mbox{stockTree[2][2]} \end{array} \end{eqnarray*}

Hence, stock_tree needs to be a vector of vectors. Its declaration is

std::vector<std::vector<double> > stock_tree;

We need to resize the vector stock_tree so it can store all of stock_tree[0], stock_tree[1], stock_tree[2], stock_tree[n].

stock_tree.resize(n+1);

Now we need to make sure that each of the vectors stock_tree[0], stock_tree[1], stock_tree[2], stock_tree[n] is properly resized. The vector stock_tree[0] must have the size $1$, so it can store stock_tree[0][0].

The vector stock_tree[1] must have the size $2$ so it can store stock_tree[1][0] and stock_tree[1][1].

The vector stock_tree[2] must have the size $3$ so it can store stock_tree[2][0], stock_tree[2][1], and stock_tree[2][2].

int i;
i=0;
while(i<=n){
  stock_tree[i].resize(i+1);
  i=i+1;
}

3.3. Calculations of stock prices

The price stock_tree[0][0] is just S.

The prices stock_tree[1][0] and stock_tree[1][1] can be evaluated next. They are stock_tree[0][0] * u and stock_tree[0][0] * d.

The prices stock_tree[2][0], stock_tree[2][1], and stock_tree[2][2] are next. The first one, stock_tree[2][0] is stock_tree[1][0]*u. The remaining ones, stock_tree[2][1] and stock_tree[2][2] can be obtained as stock_tree[0][0]*d and stock_tree[1][1]*d.

stock_tree[0][0]=S;
int j;
i=1;
while(i<=n){
  stock_tree[i][0]=stock_tree[i-1][0]*u;
  j=1;
  while(j<=i){
    stock_tree[i][j]=stock_tree[i-1][j-1]*d;
    j=j+1;
  }
  i=i+1;
}

3.4. Preparation of output

We will now transfer the calculated prices into the output table B. The prices stock_tree[0][0], stock_tree[1][0], stock_tree[2][0], ..., stock_tree[n][0] will be placed in the cells B[0][0], B[0][1], B[0][2], ..., B[0][n]. The prices stock_tree[1][1], stock_tree[2][1], ..., stock_tree[n][1] will go into the cells B[1][1], B[1][2], ..., B[1][n]. Similarly, for each i, we will transfer the prices stock_tree[i][i], stock_tree[i+1][i], ..., stock_tree[n][i] into the cells B[i][i], B[i][i+1], ..., B[i][n].

i=0;
while((i<=n)&&(i<20)){
  j=i;
  while((j<=n)&&(j<20)){
    B[i][j]=stockTree[j][i];
    j=j+1;
  }
  i=i+1;
}

3.5. Final code

double S, u, d;
S=A[0][1]; u=A[0][2]; d=A[0][3];
int n;
n=A[0][0];
std::vector<std::vector<double> > stockTree;
stockTree.resize(n+1);
int i;
i=0;
while(i<=n){
  stockTree[i].resize(i+1);
  i=i+1;
}
stockTree[0][0]=S;
int j;
i=1;
while(i<=n){
  stockTree[i][0]=stockTree[i-1][0]*u;
  j=1;
  while(j<=i){
    stockTree[i][j]=stockTree[i-1][j-1]*d;
    j=j+1;
  }
  i=i+1;
}

i=0;
while((i<=n)&&(i<20)){
  j=i;
  while((j<=n)&&(j<20)){
    B[i][j]=stockTree[j][i];
    j=j+1;
  }
  i=i+1;
}