Implementation of a simple slow and fast binomial pricing model in python. We will treat binomial tree as a network with nodes (i,j) with i representing the time steps and j representing the number of ordered price outcome, lowest – or bottom of tree – to highest.
- american_tree_slow
- american_tree_fast
Generic timing wrapper function
We will use this to benchmark the two binomial models.
import numpy as np
from functools import wraps
from time import time
def timing(f):
@wraps(f)
def wrap(*args, **kw):
ts = time()
result = f(*args, **kw)
te = time()
print('func:%r args:[%r, %r] took: %2.4f sec' % \
(f.__name__, args, kw, te-ts))
return result
return wrap
Binomial Tree Representation
Stock tree can be represented using nodes (i,j) and intial stock price \(S_0\)
\(S_{i,j} = S_0u^{j}d^{i-j}\)
\(C_{i,j}\) represents contract price at each node (i,j). Where \(C_{N,j}\) represents final payoff function that we can define.
American Option Characteristics
For an American Put Option:
if \(T = t_N\) then at the terminal nodes, \(C^{j}_N = (K-S^{j}_N)^{+}\)
for all other parts of the tree at nodes \((i,j)\)
– Max of exercise value or continuation/hold value
– \(C^{j}_i = \max \Big((K-S^{j}_i)^{+}, \exp^{-r\Delta t} \big\{ q^{j}_i C^{j+1}_{i+1} + (1 – q^{j}_i)C^{j-1}_{i-1}\big\}\Big)\)
# Initialise parameters S0 = 100 # initial stock price K = 100 # strike price T = 1 # time to maturity in years r = 0.06 # annual risk-free rate N = 3 # number of time steps u = 1.1 # up-factor in binomial models d = 1/u # ensure recombining tree opttype = 'P' # Option Type 'C' or 'P'
American Tree Slow
Here we will use for loops to iterate through nodes j at each time step i.
@timing
def american_slow_tree(K,T,S0,r,N,u,d,opttype='P'):
#precompute values
dt = T/N
q = (np.exp(r*dt) - d)/(u-d)
disc = np.exp(-r*dt)
# initialise stock prices at maturity
S = np.zeros(N+1)
for j in range(0, N+1):
S[j] = S0 * u**j * d**(N-j)
# option payoff
C = np.zeros(N+1)
for j in range(0, N+1):
if opttype == 'P':
C[j] = max(0, K - S[j])
else:
C[j] = max(0, S[j] - K)
# backward recursion through the tree
for i in np.arange(N-1,-1,-1):
for j in range(0,i+1):
S = S0 * u**j * d**(i-j)
C[j] = disc * ( q*C[j+1] + (1-q)*C[j] )
if opttype == 'P':
C[j] = max(C[j], K - S)
else:
C[j] = max(C[j], S - K)
return C[0]
american_slow_tree(K,T,S0,r,N,u,d,opttype='P')
American Tree Fast
Now we will vectorise out code using numpy arrays instead of for loops through j nodes.
@timing
def american_fast_tree(K,T,S0,r,N,u,d,opttype='P'):
#precompute values
dt = T/N
q = (np.exp(r*dt) - d)/(u-d)
disc = np.exp(-r*dt)
# initialise stock prices at maturity
S = S0 * d**(np.arange(N,-1,-1)) * u**(np.arange(0,N+1,1))
# option payoff
if opttype == 'P':
C = np.maximum(0, K - S)
else:
C = np.maximum(0, S - K)
# backward recursion through the tree
for i in np.arange(N-1,-1,-1):
S = S0 * d**(np.arange(i,-1,-1)) * u**(np.arange(0,i+1,1))
C[:i+1] = disc * ( q*C[1:i+2] + (1-q)*C[0:i+1] )
C = C[:-1]
if opttype == 'P':
C = np.maximum(C, K - S)
else:
C = np.maximum(C, S - K)
return C[0]
american_fast_tree(K,T,S0,r,N,u,d,opttype='P')
Binomial Tree Slow vs Fast
Now we will compare runtimes for slow vs fast. Ignore option price changes as this is impacted with changing the time steps and keeping the u and d factors the same.
for N in [3,50, 100, 1000, 5000]:
american_fast_tree(K,T,S0,r,N,u,d,opttype='P')
american_slow_tree(K,T,S0,r,N,u,d,opttype='P')