Saturday 8 October 2011

A Monte-Carlo simulation is a way of numerically solving problems that involve randomness. This tutorial explains how they can be used in the context of financial valuation, with examples in Ruby.

I’m going to propose a contract: I will flip a coin ten times, and if I get three heads in a row I will give you $1. How much will you pay me to enter into that contract? To work out how much this contract is worth, I’m going to start by writing a simulation of ten coin flips:
>> def do_10_flips
>>   (1..10).map{rand > 0.5 ? "H" : "T"}.join ""
>> end
=> nil
>> do_10_flips
=> "THTHHTHHHT"
>> do_10_flips
=> "HTTHTHHHTH"
>> do_10_flips
=> "TTHHHHHTHH"
This is the most important part of Monte-Carlo simulation - how you define the underlying process. I’ve made many assumptions in my function; all coin flips are independent, and all have the same probability of coming up as heads. “rand” returns a number between zero inclusive and one exclusive. This means my coin is ever-so-slightly biased towards heads - to be fair the comparison should be greater-or-equals, not strictly-greater-than (an exercise: see what difference this makes). If I were simulating a stock price instead of a coin flip I’d have a very different function with a much different set of assumptions.

For a single set of ten coin flips, I’m going to work out what the payoff of my contract would be (one if it has three successive heads - i.e. the string contains “HHH” and zero otherwise):
>> def payoff
>>   (do_10_flips.include? "HHH") ? 1.0 : 0.0
>> end
=> nil
>> payoff
=> 0.0
>> payoff
=> 0.0
>> payoff
=> 1.0
This is a single simulation of the value of the contract - a Monte-Carlo simulation essentially estimates the value of this contract by running many simulations (called “steps”) and taking the mean of the values predicted by each step:
>> def monte_carlo_solve n
>>   ret = 0.0;n.times{ret += payoff};ret /= n
>> end
=> nil
Using a Monte-Carlo simulation isn’t a silver bullet - If I attempt a valuation using a single step I’ll either get zero or one. More simulation steps means a more believable answer, but not necessarily a more accurate one. (We've also made the assumption that the "rand" function doesn't return the same numbers for each simulation step, and that each random number is uniformly distributed). Maybe we should pick a precision and increase the number of simulation steps until the valuation to that precision doesn't change? More simulation steps means the valuation takes more time, but the two are not necessarily related by a constant factor (unless you make an assumption about how the "rand" function scales).
>> monte_carlo_solve 1
=> 1.0
>> monte_carlo_solve 10
=> 0.7
>> monte_carlo_solve 1000
=> 0.49
>> monte_carlo_solve 100000
=> 0.50733
>> monte_carlo_solve 1000000
=> 0.507764
In summary, the value of the contract I proposed is 51 cents according to the longest Monte-Carlo simulation I ran. Would you be happy paying that?

1 comment:

  1. Actually I believe >= would only further increase the bias towards heads...

    If my ruby holds true ... the first value in that shorthand if statement is for true... making it >= would only increase the chances it would evaluate as true.

    ReplyDelete