F#: Monte Carlo Simulation using Tail Recursion

Previously we used lists or arrays to implement Monte Carlo simulation, where in the beginning of the code we draw a fixed number of random numbers and keep all of them in memory throughout the execution of the code. Needless to say it's very memory-consuming. Indeed, if I increase the number of simulation runs to 100 millions, the code (either the List or Array version) throws  System.OutOfMemoryException on my laptop.

We in fact don't really need to keep all the random numbers in memory, if the option price is the only thing we want to calculate, which is the case in the simple option pricing problem we are handling. At the end of the day, what really matters and hence we have to keep track of is the sum of all simulated option payouts rather than individual simulated payouts. In other words, every time when we generate a random number to simulate an option payout, there's no harm to throw away the random number as long as we have added the simulated payout to a partial sum value we keep track of.

That's where tail recursion can help. We want to use tail recursion with the accumulator pattern to achieve constant space complexity. In the code below,  the sum parameter of the loop function keeps track of the partial sum and plays the role of accumulator.

Well, here is the performance results for 10 million simulation runs on my laptop:

version	option price	CPU time (ms)	absolute time (ms)
List	10.118465	5,335	5,467
Array	10.118465	1,606	1,639
Tail Recursion	10.118465	2,730	2,732

The performance of the tail-recursive version is quite OK relative to List and Array. Anyhow, the following results show the true power of tail recursion when it comes to 100 million runs.

version	option price	CPU time (ms)	absolute time (ms)
List	out of memory	out of memory	out of memory
Array	out of memory	out of memory	out of memory
Tail Recursion	10.118305	26,800	26,898

Perhaps memory consumption is a more important factor to monitor than CPU time or absolute time. If I manually bring up Windows Task Manager, I can see that the memory use of the tail-recursive code remains steadily at the level of 1.4MB while the memory use of either the List or Array version keeps growing up to 1.8GB until it eventually throws out the out-of-memory exception and crashes.

///////////////////////////////////////////////////////////////////////////////
open System
open System.Diagnostics

let N = 10000000
let rnd = new Random(1)

let box_muller_transform (u1,u2) = sqrt(-2.0*log(u1)) * cos(2.0*Math.PI*u2)

let call_payout K S = max (S-K) 0.0

let European_Option_Price (payout:float->float) S0 r vol T =
    let S_T x = S0 * exp((r - 0.5*(vol**2.0))*T + vol*sqrt(T)*x)
    let rec loop n sum =
        if n = N then sum
        else let new_sample = (rnd.NextDouble(),rnd.NextDouble())
                              |> box_muller_transform|> S_T |> payout
             loop (n+1) (sum+new_sample)
    (loop 0 0.0) / (float N) |> (*) (exp(-r*T))

let S0 = 50.0
let K = 40.0
let r = 0.01
let vol = 0.2
let T = 0.25
let price() =
    let price = European_Option_Price (call_payout K) S0 r vol T
    printfn "option_price = %f" price

let time f =
    let proc = Process.GetCurrentProcess()
    let cpu_time_stamp = proc.TotalProcessorTime
    let timer = new Stopwatch()
    timer.Start()
    try
        f()
    finally
        let cpu_time = (proc.TotalProcessorTime-cpu_time_stamp).TotalMilliseconds
        printfn "CPU time = %dms" (int64 cpu_time)
        printfn "Absolute time = %dms" timer.ElapsedMilliseconds

time price