American-style options may be exercised prior to expiry. To price them on a binomial tree, the full tree has to be constructed. The prices are then computed at each node through a backward reduction process starting from the prices at maturity. At each node, we take the maximum of the payoff at that node versus the price implied by the binomial model.

Constructing a binomial price tree is relatively easy in q:

BPTree:{[n;S;u] n{(x*y 0),y%x}[u]\1#S} / binomial price tree

where n is the depth of the tree, S is the current price and u is the scale of the up-move. We simply let the scale of the down-move be 1/u and hence the y%x in the expression.

The general binomial model can then be implemented as follow:

GBM:{[R;P;S;T;r;b;v;n] / General Binomial Model (CRR) t:T%n; / time interval u:exp v*sqrt t; / up; down is 1/u p:(exp[b*t]-1%u)%(u-1%u); / probability of up ptree:reverse BPTree[n;S;u]; / reverse binomial price tree first R[exp[neg r*t];p] over P ptree }

where R is a reduction function, P is the payoff function, S is the current price, T is the time to maturity, r is the risk-free rate, b is the cost of carry, v is the volatility and n is the depth of the tree. For American and European options, the reduction functions may be expressed as:

American:{[D;p;a;b] max(b;D*(-1_a*p)+1_a*1-p)} European:{[D;p;a;b] D*(-1_a*p)+1_a*1-p}

where D is the discount factor and p is the probability of an up-move. Consequently, we can express the American and European binomial models simply as:

ABM:GBM[American] EBM:GBM[European]

Testing the code on an American vanilla put option (strike = 102; price = 100; time to maturity = 1 year; risk-free rate = cost of carry = 8%; volatility = 20%; depth of tree = 1000):

q) VP:{[S;K]max(K-S;0)} / vanilla put: max(K-S,0) q) \t show ABM[VP[;102];100;1;0.08;0.08;0.2;1000] 6.2215 31

It took 31 ms to compute. Pretty nice for so little code.

Note: It turns out that this implementation of EBM is faster than the one in the previous post. The reason is that I avoided using the expensive xexp function this time round. Otherwise, the previous implementation should be faster since it only computes the payoffs at maturity and not the intermediate nodes.