American Options [Financial Engineering Programming #7]

Remember the American option I name-dropped a tiny bit earlier? Time to actually talk about it.

Quick recap of what I said back then: the binomial model can price both European and American options. (Strictly speaking American options should be done with Black-Scholes, but whatever.)

So… what’s actually the difference between the two?

Honestly? Just one difference. But it’s a chunky one. heh.

A European option can only be exercised at expiration. Only at expiration. End of story. An American option? Exercise whenever you want. Any time before expiration is fair game. Early exercise — totally allowed.

(I don’t really know the history here, but doesn’t America have a bit of a gangster vibe? lol. The whole “if things aren’t going my way I’m pulling the trigger right now” energy. lol lol)

OK so before, at the very~~~ end of the tree, we had

$$c_{u^{j}d^{n-j}}$$

which was $S \cdot u^{j}d^{n-j} - K$ or zero.

One of the two values got locked in, we present-valued it, and swoosh — added everything up. Right?!

But now that whole picture changes.

For a European option, the path doesn’t matter. Whatever the value was at intermediate nodes — doesn’t matter. If it ended up at zero by expiration, the whole path is just zero. Done.

But for an American option:

among these nodes — if the value was positive somewhere along the way and then crashed to zero by the end, anyone with early-exercise rights would’ve already pulled the trigger before it went to zero.

And at that node, you’d say something like:

So we have to check the call value at every single node.

The person sitting at each node is thinking: “Hmm… should I exercise now? Or hold?”

“If I exercise right now vs. what’s the expected value at the next step from here?”

That’s the call they’re making.

OK so each point in time has its own situation.

The folks sitting at expiration? They’ve got nothing to compare against — there’s no next step. So they just go with $\max(S_{ud} - K, 0)$. No choice.

But the folks in the middle…

Yeah, there’s gonna be a lot of chatter at these nodes lol lol lol so much chatter, for real lol lol lol lol lol.

If you’re not at expiration yet, you compare against the expected call value in the next state — and pick whichever is higher. You’d compare against the present-valued option value at that point… heh.

(Or equivalently: take the immediate exercise value $S_u - K$, future-value it, and compare against the value at expiration. The formula handles both ways of thinking. Same thing.)

Honestly, this whole thing is way easier to feel through code.

So if we write code a certain way, can it represent the current $c$ for the situation above?

Quick high-level: you do option pricing from the very back, and as you walk forward through the tree, you throw out anything that goes to zero. Meaning — if the value is gonna drop in the future, that person just exercises the moment they see it.

Code for that situation looks like this. heh.

Sub ~ End Sub.

But you can also build a tree where you can see the whole interval at once.

Don’t try to write the full thing right out of the gate. First let’s look at how to build a tree with code, get how the tree gets put together, and then we’ll do the option price tree!! heh.

So, first up — coding a simple tree looks like this. I’ll skip the variable declarations.

n=5: k=0:
For i=n To 0 step -1
    For j=i To 0 step -1
        k = k+1
        Cells(2 * j + ( n - j ) + 1, i + 1)
    Next
Next

If you just run this, a tree shows up on the sheet. Done.

But honestly? I had a hard time with this at first. So I went full brute-force interpretation mode…… (T_T)

First I looked at how j changes when one i goes in, and how k changes each time j changes.

Then, to see how this maps into the Cell coordinates, I matched up the i, j to each Cell.

In that order, the Cell gets k = 1, 2, 3, 4, 6, 7, ... written into it.

After working through this much, the pattern clicked, so I stopped. Turned into one shape only at $i=5$. heh.

OK. So we roughly get how the tree is drawn.

Now let’s code it so Excel draws the binomial tree we drew earlier. Aaaaahh — well, not us doing the coding from scratch, but us looking at the already-coded version and trying to understand it!

S = 100: k = 100: rf = 0.05: t=1: n=5: up=1.1: dn=1/up:
dt = t/n: r = exp(rf*dt): df = 1/r
rho=(r-dn)/(up-dn)
z=0
With WorkSheetFunction
For i=5 To 0 step -1
    For j=i To 0 step -1
        if i=n then
            z = .Max((up)^(i-j))*((dn)^(j)*S - K , 0)   'i=5 means we're at the very end
        elseif 0<i and i<n then
            z = .Max((up)^(i-j))*((dn)^(j)*S - K , (rho*cells(2*j+(n-i), i+2) +_
                (1-rho)*cells(2*j+(n-i)+2, i+2))*df)
        else
            z = (rho*cells(2*j+(n-i), i+2) + (1-rho)*cells(2*j+(n-i)+2, i+2))*df
        End if
        cells(2*j+1+(n-i), i+1) = z
    Next
Next
End With

Before reading the if / elseif / else, let’s first look at Cells( ~ ) — the part that tells us where each i, j lands.

Here’s how I worked it out:

Then,

Oh — now I see how what’s getting written can actually be written as a tree.

Now the conditionals.

I get why i = n is its own case. At expiration it’s $\max(\text{something}, 0)$. Whereas for $0 < i < 4$, it’s $\max(\text{something}, \text{something else})$.

But why does the very first initial point — i = 0 — also need its own else branch?

Because the option value here can’t possibly be $S - K$. Nobody exercises an option the very second they buy it, so there’d be no point using Max()… heh???

import pandas as pd
import os
path = r'C:\Users\GD Park\Desktop\금융공학'
os.chdir(path)
name = 'make a simple tree'
# make a tree with n slots
n=10; k=0
n_col = [x for x in range(0, 200)]
n_row = [x for x in range(0, 200)]
df = pd.DataFrame(columns=n_col, index=n_row)
for y in range(n, 0, -1):
    for x in range(y, 0, -1):
        k+=1
        df.loc[2*x-1+(n-y), y] = k
df.dropna(how='all', inplace=True, axis=0)
df.dropna(how='all', inplace=True, axis=1)
writer = pd.ExcelWriter('make a simple tree.xlsx' , engine='xlsxwriter')
df.to_excel(writer, sheet_name='make a simple tree')
writer.save()
writer.close()

import math
import pandas as pd
S=100; k=100; rf=0.05; t=1; n=5
up=1.1; dn=1/up
dt = t/n
r = math.exp(rf * dt)
d_factor = 1/r
rho = (r-dn)/(up-dn)
n_col = [x for x in range(0, 200)]
n_row = [x for x in range(0, 200)]
df = pd.DataFrame(columns=n_col, index=n_row)
n=5
for y in range(n, 0-1, -1):
    for x in range(y, 0-1, -1):
        if y == n:
            z = max((up ** (y-x)) * (dn ** x) * S - k, 0)
        elif 0 < y < n:
            z = max((up ** (y-x)) * (dn ** x) * S - k,
                    ((rho * df.loc[2*x + (n-y), y+2]) +
                     ((1-rho)*df.loc[2*x+(n-y)+2, y+2]))*d_factor)
        else:
            z = (rho * df.loc[2*x +(n-y), y+2]) + ((1-rho)*df.loc[2*x+(n-y)+2, y+2])
        df.loc[2*x + (n-y) + 1, y+1] = z
df.dropna(how='all', inplace=True, axis=0)
df.dropna(how='all', inplace=True, axis=1)
df = df.reset_index(drop='index')
df.columns = range(df.shape[1])

Originally written in Korean on my Naver blog (2016-10). Translated to English for gdpark.blog.