Back to Questions
4.2k
views8
comments
Recombining Binomial Tree in F#
f#

Hi,

I'm looking at how to implement a combining version of a binomial tree which is often used in finance to price options ([link:en.wikipedia.org])

Can someone show me how to do this in F# ?

Many thanks.

Joe

.

Hi,

The algorithm you linked to could be directly translated in F# using imperative
constructs, such as arrays and loops, but it wouldn't demonstrate any interesting
or unique feature of the language (the code would look just the same as its C# or
C++ equivalent).

There are probably many other (and more efficient) ways to implement a binomial
tree pricer, but here is one using a higher order function allowing to independently
specify the discretization scheme and the option payoff as function arguments, and
sequences to represent the collection of states at a given date :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

// the exercise style
type Style =
    | European
    | American

// the common payoffs
let call k s = max 0.0 (s - k)
let put  k s = max 0.0 (k - s)

// the market parameters
type Market = { spot : float; vol : float; rate : float }

// the recursion using sequences
let binomialPrice discretization n payoff style (maturity : float) market =
    let (up, down, prob, discount) = discretization n maturity market
    
    let rec backprop k states =
        if k = 0 then Seq.head states |> snd
        else
            let states' =
                states
                |> Seq.pairwise
                |> Seq.map (fun ((sd, od), (_, ou)) ->
                    let spot = sd / down
                    let expectation = discount * (prob * ou + (1.0 - prob) * od)
                    match style with
                    | European -> (spot, expectation)
                    | American -> (spot, max expectation (payoff spot))
                )
            backprop (k - 1) states'
    
    (n, market.spot * down ** float n)
    |> Seq.unfold (fun (k, s) -> if k < 0 then None else Some(s, (k - 1, s * (up / down))))
    |> Seq.map (fun spot -> (spot, payoff spot))
    |> backprop n


// symmetric discretization
let cox n maturity market =
    let dt   = maturity / float n
    let up   = exp (market.vol * sqrt dt)
    let down = 1.0 / up
    let prob = (exp(market.rate * dt) - down) / (up - down)
    let disc = exp (-market.rate * dt)
    (up, down, prob, disc)

// three moments matching discretization
let tian n maturity market =
    let dt   = maturity / float n
    let r    = exp (market.rate * dt)
    let v    = exp (market.vol * market.vol * dt)
    let up   = 0.5 * r * v * (1.0 + v + sqrt(v * v + 2.0 * v - 3.0))
    let down = 0.5 * r * v * (1.0 + v - sqrt(v * v + 2.0 * v - 3.0))
    let prob = (r - down) / (up - down)
    let disc = 1.0 / r
    (up, down, prob, disc)

// concrete pricers obtained by partial application
let coxECall  n k = binomialPrice cox  n (call k) European
let coxEPut   n k = binomialPrice cox  n (put  k) European
let coxACall  n k = binomialPrice cox  n (call k) American
let coxAPut   n k = binomialPrice cox  n (put  k) American
let tianECall n k = binomialPrice tian n (call k) European
let tianEPut  n k = binomialPrice tian n (put  k) European
let tianACall n k = binomialPrice tian n (call k) American
let tianAPut  n k = binomialPrice tian n (put  k) American

// now we can price some stuff !!!
let coxEC  = coxECall  500 100.0 1.0 {spot = 100.0; vol = 0.2; rate = 0.02}
let coxEP  = coxEPut   500 100.0 1.0 {spot = 100.0; vol = 0.2; rate = 0.02}
let coxAC  = coxACall  500 100.0 1.0 {spot = 100.0; vol = 0.2; rate = 0.02}
let coxAP  = coxAPut   500 100.0 1.0 {spot = 100.0; vol = 0.2; rate = 0.02}
let tianEC = tianECall 500 100.0 1.0 {spot = 100.0; vol = 0.2; rate = 0.02}
let tianEP = tianEPut  500 100.0 1.0 {spot = 100.0; vol = 0.2; rate = 0.02}
let tianAC = tianACall 500 100.0 1.0 {spot = 100.0; vol = 0.2; rate = 0.02}
let tianAP = tianAPut  500 100.0 1.0 {spot = 100.0; vol = 0.2; rate = 0.02}

I hope this was useful.
Cheers, bubo**2.

By on 11/28/2009 10:10 AM ()

Hello Bubo,

I'm having a really hard time understading the following "backdrop" function. Could you pls explain the how it is done. I think I know how the binomial tree works, and the back propagation idea, but having trouble understanding the this recursive function. Among other things, I'm also not seeing where the terminal stock price enters into the picture. Could you pls help

Thank you very much.

Joe

By on 11/29/2009 7:23 PM ()

Hi Joe,
You didn't mention at which point you were in the process of learning / discovering F#, so i'll try to explain
everything step by step at the risk of stating the obvious.

A tree state is defined as a pair of spot price and option price, and the set of states at a given
time is represented as a sequence ordered by ascending spot price.

The algorithm consists of two parts,

(1) Initialization :

The terminal sequence is generated from the lowest possible spot price at time n (s0*down**n : n down moves), to the highest (s0*up**n : n up moves), by incrementally multiplying by up/down (undo a down move and do an up move instead).

This step is accomplished by Seq.unfold which is a very nice function allowing to build a sequence from a recurrence relation :
it takes as arguments a seed state and a function which, given a current state returns None to indicate termination or Some pair of a generated element and a new state. In order to obtain the terminal option prices as well, we just have to apply Seq.map to transform each spot to a pair of the spot and the associated payoff.

(2) Recursion :
Given the states at time k, compute the states at time (k-1) knowing that the new lowest state will be computed from the old lowest state and its successor and so on. Enter another nice function from the Seq module, pairwise, which produces the sequence of pairs (element, successor) we just need.
The remaining map simply implements the elementary backward computation step with a lambda whose argument is a pattern representing the pair of states ((spot down, option down), (spot up, option up)).
Note that the base sequence obtained at the end of the recursion is actually a kind of delayed computation which unfolds only when Seq.head is called.

Seq.unfold can be replaced with the more explicit :

1
2

    [0 .. n]
    |> Seq.map (fun i -> market.spot * (up ** float i) * (down ** float (n - i)))

Sequences can be replaced with lists altogether (change Seq to List and implement List.pairwise !!!).

Surprisingly enough the code performance is not too bad (?) when compared to the most imperative equivalent (one array + in place mutation + for loops) : american put with 500 steps => ~25ms (seq) ~20ms (list) ~5ms (horribly imperative).

Cheers, bubo**2.

By on 11/30/2009 9:19 AM ()

Hi Bubo,

Thanks much for the explanation. Yes, I should have told you this at the beginning, I'm just 2 weeks into F#. Started reading "F#" Oreilly book, but wanted to learn by doing it, and picked what I thought was a non trivial exercise. And sure it turns out to be a non trivial : )

And yes, like you said in the first message I was trying to do it in the functional programming way, not using imperative constructs.

I really appreciate you taking time to explain things. I have to admit, I'm still not able to put everything together. It is the recursive function that's throwing me off. Among other things, you're calling "backprop n" at the end of it, does it not take two variables ?

I'm also wondering if you happen to have a non recursive version of backprop function. I'm thinking it might be easier for me to understand it.

Thanks again for your help.

Joe

By on 12/2/2009 8:40 AM ()

Hi Bubo,

Great posting.

Does the sequence function memoize the joining tree? I would think not as there are roundoff issues.

James

By on 12/1/2009 4:10 AM ()

Actually, having invested the time to understand the code, I see that the sequences are truely replicating the backwards sweep with pair wise combining. So there is no notion of "over doing" it that would need memoization.

Anyways, for fun I wrote a recursive version to compare speeds (not much faster):

let binomialPrice2 discretization n payoff style (maturity : float) market =

let (up, down, prob, discount) = discretization n maturity market

let cache = Array.zeroCreate<float> (4*n*n)

let rec price i j spot =

if i=n then

payoff spot

else

let index = (2*n*i)+(n+j)

let cp = cache.[index]

if cp<>0.0 then

cp-1.0

else

let ou = price (i+1) (j+1) (up*spot)

let od = price (i+1) (j-1) (down*spot)

let expectation = discount * (prob * ou + (1.0 - prob) * od)

let o =

match style with

| European -> expectation

| American -> max expectation (payoff spot)

cache.[index]<-(o+1.0);

o

price 0 0 market.spot

(obviously you see can't understand how to get the formatting to work!, sorry about that)

By on 12/3/2009 2:14 AM ()

Joe, to answer your question about backprop, yes it has two arguments and the second is applied via the pipe-forward (|>) operator. I suggest that you keep reading "Programming F#" through the end of chapter 3 where currying, function composition and recursion are explained and the code above should become clearer (the description of the sequence aggregate operators on the F# MSDN online documentation should be helpful too).

James, I like your recursion on a lattice way of implementing the algorithm, although it seems that some code have gone missing (the cache assignment). Also, I don't quite understand where the cp - 1.0 is coming from (line 11 of the code snippet).

For fun, as well, here is a revised version of the sequence algorithm using only pipelined higher-order functions :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

let binomialPrice discretization n payoff style (maturity : float) market =
    let (up, down, prob, discount) = discretization n maturity market
    
    let backstep ((sd, od), (_, ou)) =
        let spot = sd / down
        let expectation = discount * (prob * ou + (1.0 - prob) * od)
        match style with
        | European -> (spot, expectation)
        | American -> (spot, max expectation (payoff spot))
    
    (n, market.spot * down ** float n)
    |> Seq.unfold (fun (k, s) -> if k < 0 then None else Some(s, (k - 1, s * (up / down))))
    |> Seq.map    (fun s -> (s, payoff s))
    |> Seq.unfold (Seq.pairwise >> Seq.map backstep >> fun x -> Some(x, x))
    |> Seq.skip (n - 1) |> Seq.head |> Seq.head |> snd

Bubo**2.

By on 12/3/2009 8:59 AM ()

Hi Bubo, Very nice, though I'm still trying to digest this ; ), I can see the elegence in your solution. Thank you very much.

Joe.

By on 11/29/2009 7:44 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper