In this tutorial we will be implementating 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.
– binomial_tree_slow
– binomial_tree_fast
We will be using a generic timing wrapper function to judge the time performance of using numpy arrays over for loops to iterate over j nodes in each time step i. Please note if you do not want to use the timing wrapper, please still import numpy!
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 \(S0\)
\(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.
For this tutorial will will price a European Call, so \(C_{N,j} = max(S_{N,j}-K,0)\)
# 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 = 'C' # Option Type 'C' or 'P'
Binomial Tree Slow
For the binomial tree slow, we will use for loops to iterate through nodes j at each time step i.
@timing
def binomial_tree_slow(K,T,S0,r,N,u,d,opttype='C'):
#precompute constants
dt = T/N
q = (np.exp(r*dt) - d) / (u-d)
disc = np.exp(-r*dt)
# initialise asset prices at maturity - Time step N
S = np.zeros(N+1)
S[0] = S0*d**N
for j in range(1,N+1):
S[j] = S[j-1]*u/d
# initialise option values at maturity
C = np.zeros(N+1)
for j in range(0,N+1):
C[j] = max(0, S[j]-K)
# step backwards through tree
for i in np.arange(N,0,-1):
for j in range(0,i):
C[j] = disc * ( q*C[j+1] + (1-q)*C[j] )
return C[0]
binomial_tree_slow(K,T,S0,r,N,u,d,opttype='C')
Binomial Tree Fast
Now we will vectorise out code using numpy arrays instead of for loops through j nodes.
@timing
def binomial_tree_fast(K,T,S0,r,N,u,d,opttype='C'):
#precompute constants
dt = T/N
q = (np.exp(r*dt) - d) / (u-d)
disc = np.exp(-r*dt)
# initialise asset prices at maturity - Time step N
C = S0 * d ** (np.arange(N,-1,-1)) * u ** (np.arange(0,N+1,1))
# initialise option values at maturity
C = np.maximum( C - K , np.zeros(N+1) )
# step backwards through tree
for i in np.arange(N,0,-1):
C = disc * ( q * C[1:i+1] + (1-q) * C[0:i] )
return C[0]
binomial_tree_fast(K,T,S0,r,N,u,d,opttype='C')
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]:
binomial_tree_slow(K,T,S0,r,N,u,d,opttype='C')
binomial_tree_fast(K,T,S0,r,N,u,d,opttype='C')