## Wednesday, August 15, 2012

### 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