American and European option pricing with early exercise detection
| Symbol | Formula | Description |
|---|---|---|
| $\Delta t$ | $T / n$ | Length of each time step |
| $u$ | $e^{\sigma\sqrt{\Delta t}}$ | Up factor |
| $d$ | $e^{-\sigma\sqrt{\Delta t}} = 1/u$ | Down factor |
| $p$ | $\dfrac{e^{(r-q)\Delta t} - d}{u - d}$ | Risk-neutral probability of an up move |
where $\sigma$ is the volatility, $r$ the risk-free rate, $q$ the continuous dividend yield, and $T$ the time to expiration.
$$S_{j,i} = S_0 \; u^{i-j} \; d^{j}$$
$i$ = time step ($0, 1, \dots, n$), $j$ = number of down moves ($0, 1, \dots, i$).
At maturity ($i = n$):
$$C_{j,n} = \max(S_{j,n} - K, \; 0) \quad \text{(call)}, \qquad P_{j,n} = \max(K - S_{j,n}, \; 0) \quad \text{(put)}$$
For earlier nodes ($i < n$):
$$V_{j,i} = e^{-r\Delta t}\Big[p \, V_{j,i+1} + (1-p) \, V_{j+1,i+1}\Big]$$
Same maturity payoff, but at each earlier node we compare continuation value with the intrinsic value:
$$V_{j,i} = \max\!\Big(e^{-r\Delta t}\big[p \, V_{j,i+1} + (1-p) \, V_{j+1,i+1}\big], \; \text{Intrinsic}_{j,i}\Big)$$
Early exercise occurs whenever the intrinsic value exceeds the continuation value.
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatchescrr_parameters computes the up/down factors and the risk-neutral probability. crr_stock builds the full recombining stock-price tree.
def crr_parameters(sigma, n, r, q, T):
dt = T / n
u = np.exp(sigma * np.sqrt(dt))
d = np.exp(-sigma * np.sqrt(dt))
p = (np.exp((r - q) * dt) - d) / (u - d)
return u, d, p
def crr_stock(sigma, n, r, q, S, K, T):
dt = T / n
u, d, p = crr_parameters(sigma, n, r, q, T)
smat = np.zeros((n + 1, n + 1))
for i in range(n + 1):
for j in range(i + 1):
smat[j, i] = S * u ** (i - j) * d ** j
return smatWe set the strike equal to the spot price ($K = S$) so the option is at-the-money.
S = 100.0 # Spot price
K = 100.0 # Strike price (ATM)
T = 1.0 # Time to expiry (years)
r = 0.05 # Risk-free rate
q = 0.0 # Dividend yield
sigma = 0.20 # Volatility
n = 4 # Number of time steps
u, d, p = crr_parameters(sigma, n, r, q, T)
print(f"dt = {T/n:.4f}")
print(f"u = {u:.6f}")
print(f"d = {d:.6f}")
print(f"p = {p:.6f}")
smat = crr_stock(sigma, n, r, q, S, K, T)
print(f"\nStock price tree:\n{np.round(smat, 2)}")Backward induction without early-exercise check: the value at each node is purely the discounted expected value under the risk-neutral measure.
Loop 1, Payoffs at maturity (for j in range(n+1)): We fill the last column of the option matrix (omat[:, -1]). At expiry every node $j$ has a known payoff:
$$\text{call: } \max(S_{j,n} - K,\; 0) \qquad \text{put: } \max(K - S_{j,n},\; 0)$$
$j$ runs from 0 (all ups, highest stock price) down to $n$ (all downs, lowest stock price), so each row in the last column gets its terminal payoff.
Loop 2, Backward induction (for i ... for j ...): We step backwards in time from column $i = n-1$ to $i = 0$. At each time step $i$, there are $i+1$ active nodes ($j = 0, \dots, i$). For each node $(j, i)$ the option value is the discounted risk-neutral expectation of its two children:
$$V_{j,i} = e^{-r\Delta t}\Big[p \cdot V_{j,\,i+1} \;+\; (1-p) \cdot V_{j+1,\,i+1}\Big]$$
$V_{j,\,i+1}$ is the child after an up move (same row, next column). $V_{j+1,\,i+1}$ is the child after a down move (row below, next column).
When the loops finish, omat[0, 0] holds the fair option price at $t = 0$.
def crr_european(sigma, n, r, q, S, K, T, option_type='call'):
dt = T / n
omat = np.zeros((n + 1, n + 1))
u, d, p = crr_parameters(sigma, n, r, q, T)
smat = crr_stock(sigma, n, r, q, S, K, T)
# STEP 1: PAYOFFS at MATURITY
for j in range(0, n + 1):
if option_type == 'call':
omat[j, -1] = max(smat[j, -1] - K, 0)
if option_type == 'put':
omat[j, -1] = max(K - smat[j, -1], 0)
# STEP 2: BACKWARDS INDUCTION
for i in range(n - 1, -1, -1):
for j in range(0, i + 1):
omat[j, i] = (p * omat[j, i + 1] + (1 - p) * omat[j + 1, i + 1]) * np.exp(-r * dt)
return omatomat = crr_european(sigma, n, r, q, S, K, T, option_type='call')
print(f"European Call Price: ${omat[0, 0]:.4f}")The CRR tree converges to the Black-Scholes price as $n \to \infty$. Let's compare them side by side.
from scipy.stats import norm
def bs_price(S, K, T, r, q, sigma, option_type='call'):
d1 = (np.log(S / K) + (r - q + 0.5 * sigma**2) * T) / (sigma * np.sqrt(T))
d2 = d1 - sigma * np.sqrt(T)
if option_type == 'call':
return S * np.exp(-q * T) * norm.cdf(d1) - K * np.exp(-r * T) * norm.cdf(d2)
else:
return K * np.exp(-r * T) * norm.cdf(-d2) - S * np.exp(-q * T) * norm.cdf(-d1)
bs = bs_price(S, K, T, r, q, sigma, option_type='call')
crr = omat[0, 0]
diff = crr - bs
print(f"Black-Scholes Price : ${bs:.4f}")
print(f"CRR European (n={n}) : ${crr:.4f}")
print(f"Difference : ${diff:.4f}")Same backward induction, but at every node we compare the continuation value with the intrinsic value and take the maximum. This captures the early-exercise premium.
$$E_{i,j} = \max(S_{i,j} - K,\; 0) \quad \text{(call)} \qquad E_{i,j} = \max(K - S_{i,j},\; 0) \quad \text{(put)}$$
$$C_{i,j} = e^{-r\Delta t}\Big[p \cdot V_{i+1,\,j} + (1-p) \cdot V_{i+1,\,j+1}\Big]$$
$$V_{i,j} = \max\!\Big(C_{i,j},\;\; E_{i,j}\Big)$$
Loop 1 is identical to European: Terminal payoffs are the same, since at maturity there is no difference between European and American.
Loop 2 adds the early-exercise check: The outer loop walks backwards from $i = n-1$ to $0$, and the inner loop visits each node $j = 0, \dots, i$. The key difference is the max over two quantities:
Continuation value $C_{i,j}$ is the same discounted expectation as European, representing the value of holding the option.
Intrinsic value $E_{i,j}$ is what you would get by exercising right now at node $(i, j)$.
If intrinsic > continuation, the holder exercises early at that node. This is what makes American options at least as valuable as their European counterparts.
def crr_american(sigma, n, r, q, S, K, T, option_type='call'):
dt = T / n
amat = np.zeros((n + 1, n + 1))
u, d, p = crr_parameters(sigma, n, r, q, T)
smat = crr_stock(sigma, n, r, q, S, K, T)
# STEP 1: PAYOFFS at MATURITY
for j in range(0, n + 1):
if option_type == 'call':
amat[j, -1] = max(smat[j, -1] - K, 0)
if option_type == 'put':
amat[j, -1] = max(K - smat[j, -1], 0)
# STEP 2: BACKWARDS INDUCTION with EARLY EXERCISE
for i in range(n - 1, -1, -1):
for j in range(0, i + 1):
if option_type == 'call':
amat[j, i] = max(
(p * amat[j, i + 1] + (1 - p) * amat[j + 1, i + 1]) * np.exp(-r * dt),
max(smat[j, i] - K, 0)
)
if option_type == 'put':
amat[j, i] = max(
(p * amat[j, i + 1] + (1 - p) * amat[j + 1, i + 1]) * np.exp(-r * dt),
max(K - smat[j, i], 0)
)
return amatamat = crr_american(sigma, n, r, q, S, K, T, option_type='call')
print(f"American Call Price: ${amat[0, 0]:.4f}")Each node shows: S for the stock price, C for the American call value, and S − K for the intrinsic value. Nodes where early exercise is optimal (intrinsic > continuation) are highlighted in red.
def plot_crr_tree(sigma, n, r, q, S, K, T, option_type='call'):
dt = T / n
u, d, p = crr_parameters(sigma, n, r, q, T)
smat = crr_stock(sigma, n, r, q, S, K, T)
amat = crr_american(sigma, n, r, q, S, K, T, option_type)
fig, ax = plt.subplots(1, 1, figsize=(4 * (n + 1), 3 * (n + 1)))
for i in range(n + 1):
for j in range(i + 1):
x = i
y = i - 2 * j
stock = smat[j, i]
option_val = amat[j, i]
if option_type == 'call':
intrinsic = max(stock - K, 0)
else:
intrinsic = max(K - stock, 0)
if i < n:
continuation = (p * amat[j, i + 1] + (1 - p) * amat[j + 1, i + 1]) * np.exp(-r * dt)
early_exercise = intrinsic > continuation + 1e-10 and intrinsic > 0
else:
early_exercise = False
color = '#FF6B6B' if early_exercise else '#4ECDC4'
edge_color = '#C0392B' if early_exercise else '#2C3E50'
bbox = dict(boxstyle='round,pad=0.4', facecolor=color,
edgecolor=edge_color, linewidth=2)
label = f"S={stock:.2f}\nC={option_val:.2f}\nS-K={stock - K:.2f}"
ax.text(x, y, label, ha='center', va='center',
fontsize=8, fontweight='bold', bbox=bbox)
if i < n:
x_child = i + 1
y_up = (i + 1) - 2 * j
y_down = (i + 1) - 2 * (j + 1)
ax.annotate('', xy=(x_child - 0.3, y_up),
xytext=(x + 0.3, y),
arrowprops=dict(arrowstyle='->',
color='#2C3E50', lw=1.5))
ax.annotate('', xy=(x_child - 0.3, y_down),
xytext=(x + 0.3, y),
arrowprops=dict(arrowstyle='->',
color='#2C3E50', lw=1.5))
ax.set_xlim(-0.8, n + 0.8)
ax.set_ylim(-(n + 1.5), n + 1.5)
ax.set_xticks(range(n + 1))
ax.set_xticklabels([f"t={i}" for i in range(n + 1)], fontsize=10)
ax.set_yticks([])
ax.set_title(
f"CRR American {option_type.title()} Tree "
f"(S={S}, K={K}, T={T}, n={n}, \u03c3={sigma}, r={r})",
fontsize=14, fontweight='bold')
normal_patch = mpatches.Patch(facecolor='#4ECDC4',
edgecolor='#2C3E50',
label='Continuation optimal')
exercise_patch = mpatches.Patch(facecolor='#FF6B6B',
edgecolor='#C0392B',
label='Early exercise optimal')
ax.legend(handles=[normal_patch, exercise_patch],
loc='upper left', fontsize=10)
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['left'].set_visible(False)
plt.tight_layout()
plt.show()
plot_crr_tree(sigma, n, r, q, S, K, T, option_type='call')