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')