Report

Monte Carlo Simulation Brett Foster Monte Carlo In A Nutshell • Using a large number of simulated trials in order to approximate a solution to a problem • Generating random numbers – Computer not required, though extremely helpful A Brief History • Earliest well documented use of Monte Carlo: – Late 18th Century France • Comte de Buffon performed an experiment involving the repeated tossing of a needle onto a plane • Wanted to determine probability of needle intersecting a string Modern Monte Carlo Method • Named after Monte Carlo Casino in 1940’s by a group of men working on the nuclear bomb – John von Neumann, Stanislaw Ulam and Nicholas Metropolis • Ulam’s Uncle supposedly often frequented this Casino Onset of Computers • Invention and popularization of computer – Much more practical to implement Monte Carlo – Popularity has taken off since 1950’s Random Numbers • Key aspect of computers: allow us to quickly generate thousands of “random” numbers. – Food for thought: • Computers are ultimately deterministic devices – How then can the numbers be “random?” – We will leave this thought for the philosophers and assume that we do actually have random numbers A Simple Example • Using Monte Carlo to approximate pi – Will give us a better understanding of how to implement and analyze a Monte Carlo Simulation • Obviously, there are more efficient ways to figure out digits of pi • This example will help build a conceptual understanding before looking at another example • Consider a unit circle inscribed within a square – The ratio of the area of the circle to the area of the square is π/4 • We will use this key fact in order to estimate π by randomly selecting points with the square, and checking whether they are within the circle • We will generate n points uniformly distributed within the square • Let X denote a binomial random variable which takes the value 1 if a randomly generated point falls within the circle and 0 if the point falls outside of the circle • X is a Bernoulli R.V. with p = π/4 • Notice: E(X) = π/4 E(4X) = π • For convenience, let Y = 4X. Now, we estimate π with The Simulation: • This simulation can easily be programmed into a computer: – I used VBA in Excel to write a short function to run our simulation • We input n, number of trials, and function will repeatedly select points uniformly distributed within the square and determine how many fall within the circle • Function computes sample mean and returns our estimate for π : VBA Code: Function EstimatePi(n As Integer) c=0 'loop through proceedure n times For i = 1 To n 'generate point uniformly within square x = -1 + 2 * Rnd() y = -1 + 2 * Rnd() 'Check if within circle If (x ^ 2 + y ^ 2 < 1) Then c=c+1 End If Next 'compute our estimate for pi EstimatePi = 4 * c / n End Function How accurate is this method? • Consider the variance of our estimate: • Since X is a Bernoulli R.V. with p = π/4, Var(X) = (π/4)(1- π/4), however we will assume we don’t know π. Hence, we shall compute the sample variance of X. Sample Variance of X • We can calculate this retrospectively, since X is a Bernoulli R.V: – Ex: When n = 1000, we estimate pi to be 3.188. That is, – Hence, 797 of our points fell within the circle, making x = 1 for 797 of our trials, and zero for the other 203 – Now, can be easily calculated Confidence Intervals • Central limit theorem: tells us that approximately normal (for large n) • Then, is – the (1 – α) Confidence Interval is given by where is the inverse of the standard normal cumulative distribution function A note on variance • The variance of our estimate decreases with n, since • As n changes, we have • For large n, this gets very small • What are the implications for Monte Carlo? Results n c 100 84 3.36 1,000 797 3.188 10,000 7,797 3.1188 100,000 78,757 3.15028 1,000,000 785,327 3.141308 10,000,000 7,854,333 3.1417332 S2(X) 0.13576 0.16195 0.17179 0.16731 0.16859 0.16853 S2() 0.02172121 0.00259125 0.00027486 0.00002677 0.00000270 0.00000027 S() 0.14738 0.05090 0.01658 0.00517 0.00164 0.00052 95% CI LB 3.07113 3.08823 3.08631 3.14014 3.13809 3.14072 95% CI UB 3.64887 3.28777 3.15129 3.16042 3.14453 3.14275 • For n = 10,000,000 our estimate is accurate to three decimal places when compared with π – Not exactly efficient Hypothetically… • With this method for estimating π, how many trials are necessary for us to be at least 95% sure that our error is less than 1x10-10? • About 1.036x1021 • Clearly, Monte Carlo is not best method for figuring out digits of pi – So what is a practical application??? A Real World Example: Valuing a Financial Option • An option is a financial derivative – Its value is derived from some other object, such as a stock • Payoff is dependent upon the value of the stock at the expiration date of the option – For a call option, the owner has the right to buy or sell the underlying asset at a specified price, known as the “Strike Price,” at the “expiration date” specified in the option contract Example • Consider a call option written on Apple stock with a strike price of $450 and an expiration date in 6 months. – In 6 months, if the stock price is above $450 (say $475 perhaps), the owner will exercise the option and purchase the stock for $450 (getting a payoff of $25) • If the stock price is below $450, the owner will simply let the option expire, making a payoff of $0 • More succinctly, the payoff at expiration is given by Payoff = Max{0, S – 450} Where S is the stock price and 450 is the strike price – Note that the payoff is never negative! • How can we value this sort of derivative? – Requires some assumptions about the behavior of stock prices: • Rate of return on a stock is normally distributed – Implies that stock prices are Lognormal » If X is a normal random variable, then exp(X) is a lognormal random variable Specifically, we say • Where we define: is the current stock price is the stock price at time t > 0 is the expected rate of return on the stock is the variance of the annual rate of return on the stock and its square root is called volatility is a standard normal random variable • Using historical data, one can easily obtain estimates for the expected return and volatility of a stock • Under the lognormal stock price model, predicting a future stock price boils down to generating a standard normal random variable The Black-Scholes Equation • Most options (such as the one which we examined earlier) can easily be valued using the Black-Scholes equation • So why would we want to use Monte-Carlo? – Not all options can be valued with Black-Scholes • Why not??? A rough description • Recall, the payoff function for a call option discussed previously was given by Payoff = Max{0, S-450} If S is lognormal, the payoff of the option has to do with the probability that S > 450 (and by how much) – What if instead of a strike price of 450, we have a strike price that is also a random variable? What if that random variable is not lognormal? • Consider an option which gives the owner the right (but not the obligation) to purchase a share of stock A for the average of the prices of stock B and stock C • Then, our payoff function is given by • This is called a “basket option” and no formula exists to calculate its value Enter…. Monte Carlo! • Scenario: – Suppose that Apple would like to encourage innovation and dedication by issuing its employees a stock option which pays off if the price of Apple stock exceeds the average of Google and Amazon stock 1 year from now – Why value this option? • Accounting purposes: what is this worth? • Employee interest: what is the value of this option? • The payoff is that of a basket option: Payoff = Max{0, Sapple - .5(Sgoogle + SAmazon)} • How can we value this? – Monte Carlo Simulation: • Run many trials where we calculate the average future value of the option for these trials. Then discount this to the present value using the risk free rate Parameters • In order to run the simulation, we need to estimate the expected return and annual volatility for each of the three stocks – For expected return, we can use the CAPM model – Volatility is calculated using historical data – Need starting price (end of day November 4th) – Need risk free rate of return: LIBOR = 0.95% –t=1 Stock Apple Google Amazon Expected Return () .087 .081 .074 Estimated Annual Volatility () 0.2532 0.2917 0.3688 Starting price 395.28 600.95 211.22 Standard Normal • In our first example, we only needed to generate uniform random variables on (0,1) – We now need to generate standard normal random variables to simulate future stock prices • Generate uniform random variables on (0,1) • Treat as a percentile from standard normal distribution, and take the inverse – This gives you a random draw from the standard normal distribution Another Issue • Stock prices do not move independently of one another – We will need to calculate the correlation coefficient for the returns on Apple, Google and Amazon stock. Again, we can use historical data: Corr(Apple,Google) Corr(Google,Amazon) , , 0.6357 0.5258 Corr(Apple,Amazon) , 0.5193 How do we generate correlated R.V.’s? • Let Z(ap), Z(g), and Z(az) be the standard normal random variables used to simuate the future stock prices of Apple, Google, and Amazon respectively. Let ‘s be independent standard normal random variables Now, define: • One can easily verify that Z(ap), Z(g) and Z(az) are all standard normal random variables, with Corr(Z(ap), Z(g)) = Corr(Z(g), Z(az)) = Corr(Z(ap), Z(az)) = The Simulation • We now have all the information necessary to run our simulation. The procedure can roughly be described as follows: 1. Simulate the future stock price for each of the companies 2. Compute the option’s payoff for the simulated future stock prices 3. Repeat steps 1 and 2 until you have reached the desired number of trials 4. Compute the sample mean of the option payoff 5. Discount at the risk free rate to determine our estimate for the value of the option • As before, this can be done using VBA in Excel: Function ValueBasketCall(s1 As Double, s2 As Double, s3 As Double, C12 As Double, C13 As Double, C23 As Double, v1 As Double, v2 As Double, v3 As Double, a1 As Double, a2 As Double, a3 As Double, r As Double, t As Double, n As Integer) p=0 m1 = s1 * Exp((a1 - 0.5 * (v1) ^ 2) * t) m2 = s2 * Exp((a2 - 0.5 * (v2) ^ 2) * t) m3 = s3 * Exp((a3 - 0.5 * (v3) ^ 2) * t) For i = 1 To n u1 = Rnd() Z1 = WorksheetFunction.NormSInv(u1) u2 = Rnd() X2 = WorksheetFunction.NormSInv(u2) Z2 = C12 * Z1 + X2 * (1 - C12 ^ 2) ^ 0.5 u3 = Rnd() X3 = WorksheetFunction.NormSInv(u3) Z3 = C13 * Z1 + X1 * (C23 - C13 * C12) / ((1 - (C12) ^ 2) ^ 0.5) + X3 * ((1 - (C13) ^ 2 - ((C23 - C13 * C12) ^ 2 / (1 - C12 ^ 2))) ^ 0.5) q1 = m1 * Exp(Z1 * v1 * (t) ^ 0.5) q2 = m2 * Exp(Z2 * v2 * (t) ^ 0.5) q3 = m3 * Exp(Z3 * v3 * (t) ^ 0.5) payoff = WorksheetFunction.Max(0, q1 - 0.5 * (q2 + q3)) p = p + payoff Next ValueBasketCall = p * Exp(-r * t) / n End Function Analyzing the results: • As in our pi example, the results are much more meaningful if we have some idea of their accuracy • Define V as the value of the option for a single trial. Then, our estimate is given by • CLT is approximately normal • Also, • How do we calculate Var(V)? • Recall how we previously retrospectively determined the sample variance – Since X was Bernoulli, we could recover the values of X and estimate S2(X) – That approach does not work here, since V is certainly not Bernoulli. Need to store each V as we go, and calculate S2(V) last • My solution: Estimate S2(V) using 1,000,000 trials with n = 1, and use to compute sample variance for simulations with n>1 • Estimated S2(V) = 2293.63 Results n 95 % CI LB 95% CI UB 100 24.20 22.9363 4.789 14.82 33.59 1000 32.38 2.2936 1.514 29.41 35.35 10000 29.72 0.2294 0.479 28.78 30.66 100000 29.81 0.0229 0.151 29.52 30.11 1000000 29.99 0.0023 0.048 29.90 30.09 • With n = 1,000,000 we are about 95% sure that the actual value is within $0.10 of $29.99 – Probably accurate enough for most practical purposes Conclusion • Monte Carlo provides a numerical method to obtain an estimate for a solution that needs to be close, but not necessarily exact • We showed two specific examples, but the applications of Monte Carlo are very diverse • Questions??? Sources: • • • • Bodie, Zvi, Alex Kane, and Alan Marcus. Essentials of Investments. Eighth Edition. New York: Mcgraw-Hill, 2010. Kalos, Malvin H., and Paula A. Whitlock. Monte Carlo Methods Volume 1: Basics. New York: John Wiley & Sons, 1986. McDonald, Robert obert Lynch. Derivatives Markets. 2nd. Boston: Pearson Education Inc., 2006. Print. Sobol, IIya. A Primer for the Monte Carlo Method. Boca Raton: CRC Press, 1994.