%pylab inline
%precision 2

Populating the interactive namespace from numpy and matplotlib

'%.2f'

# Parameters
u = 1.1
d = .9
S0 = 10
r = .01
N = 90

# Risk neutral probabilities
p = (1 + r - d) / (u-d)
q = (u - 1 -r) / (u - d)

# Up rebate option: Pays A the first time stock price crosses U
A = 1
U = 1.2 * S0

We can compute the arbitrage free price using the following recurrence relations: \begin{gather} 1_{\sigma \geq n} V_n = f_n(S_n)\\ f_N(s) = A 1_{s \geq U} f_n(s) = A 1_{s \geq U} + 1_{\{s < U\}} \frac{\tilde p f_{n+1}(us) + \tilde q f_{n+1}(ds) }{1+r} \end{gather}

# Choose the state process Y = S
# Compute range first. (This requires a forward loop from 0 to N).
# As before, if you use this method, the size of the domain will grow exponentially
# because of floating point errors.
dom = empty( N+1, dtype=object )
dom[0] = set( [S0] )
for n in range(N):
    if len(dom[n]) > 1e9: raise Exception('Out of memory')
    # Only add valuse to the domain when the stock price is below U
    dom[n+1] = set( u*s for s in dom[n] if u*s < U )
    dom[n+1].update( d*s for s in dom[n] if d*s < U )

# Compute price. f[n](s, m) gives the price at time n when stock price is s and running max is m
f = empty( N+1, dtype=object )
f[N] = { s:0 for s in dom[N] } # Option expires worthless
def Rn(n, s):
    # Rollback operator
    En = p* (f[n+1][u*s] if u*s < U else A) \
        + q * (f[n+1][d*s] if d*s < U else A )
    return En/(1+r)
for n in range(N-1, -1, -1):
    f[n] = { s:  Rn(n, s) for s in dom[n] }
    
# The above only computes the AFP when S_n < U.
# So if σ = n, the AFP is A. If σ > n, the AFP is f[n][S_n]

# Print a few values of the arbitrage free price
f[0]

{10: 0.78}

f[1]

{9.00: 0.68, 11.00: 0.88}

This means that if the stock price is $\$9$, and σ > 1, then the AFP is $\$0.68$. Similarly, if the stock price is $\$11$ and σ > 1, then the AFP is $\$0.88$.

# Notice no values above U get added to the domain. This is only the AFP for σ < n. For σ = n, the AFP is just A.
f[5]

{5.90: 0.40, 7.22: 0.52, 8.82: 0.67, 8.82: 0.67, 10.78: 0.83}