Aaron Brown
Morgan Stanley
Introduction
Monte Carlo is a beautifully simple and counterintuitive idea: when a problem is too hard to solve rationally, do something random. It has application beyond applied mathematics. In the introduction to The Simple Art of Murder,1 Raymond Chandler explained the secret to keeping the plot moving in hard-boiled fiction, “[T]he demand was for constant action; if you stopped to think you were lost. When in doubt, have a man come through a door with a gun in his hand.” Thirty-three years later, the television show The A Team faced a similar problem. The show’s innovation was to have constant action sequences; there was no tolerance for thinking, investigating, or waiting. The screenwriters were forced to make such frequent use of the phrase “It’s so crazy, it just might work” to explain essentially random actions by the main characters, it became a tagline of the show. Of course, by that time the action stakes had been raised. A man with a gun was not enough—the A Team’s plan was usually something like build an armored assault vehicle out of a can of tuna fish and a used-up cigarette lighter, then drive down Main Street and hope the bad guys shoot and reveal their hideout.
Older readers will remember hand-soldered electronics with vacuum tubes. When these worked badly, people learned that a sharp slap on the side often corrected the problem. We used to tap meters and feather dials to get more accurate results. With modern solid-state components, randomness usually hurts rather than helps performance, but we still randomly jiggle papers to get them to line up and gently shake powders to get them smooth. Improvisational theatre teaches actors to respond to everything with, “yes, but . . . ,” and add some random element. “Yes” and “no” both stop the action. You need added randomness to keep the skit going and, of course, random mutations are the reason this chapter has been included in this book.
Pi and Canfield
A classic early application of Monte Carlo analysis is described in Hammersley and Handscomb’s Monte Carlo Methods.2 In 1864, an army officer named Fox was wounded in the American Civil War. He amused himself while recovering by tossing a needle onto a lined sheet of paper to determine the proportion of times the needle intersected a line. Georges-Louis Leclerc, Comte de Buffon, tried to calculate this proportion in 1777, so the experiment is known as “Buffon’s Needle.” Pierre-Simon Laplace derived the correct mathematical expression in 1812. The probability is equal to two times the length of the needle divided by pi times the distance between the lines. Fox reversed the logic and used the experimental result to estimate pi (two times the length of the needle divided by the proportion of hits times the distance between the lines should equal pi in the long run). This is the key idea of Monte Carlo analysis, to use a random experiment to get an approximate answer to a mathematical problem.
Eighty years later, Stanislaw Ulam was convalescing from an illness and wondering about the probability of winning a game of Canfield Solitaire. After failing to get an analytic solution, he thought about playing a large number of games to get the answer. There were three reasons that Ulam’s musings led to Monte Carlo analysis while Fox’s needle tossing remains a historical footnote. First, Ulam had computers, which make the Monte Carlo idea much more powerful. Even primitive computers could toss a lot more needles than a wounded Army captain. Secondly, Ulam knew a lot of important physics problems that could be attacked profitably with Monte Carlo methods. People already knew pi to more accuracy than any experiment could produce. Thirdly, Ulam knew John von Neumann and Nicholas Metropolis, who helped with the mathematical development (and Metropolis had a gambler grandfather who coined the term “Monte Carlo,” after the famed gambling resort, which did much to popularize the technique).
Unfortunately, there are three problems with the Canfield example, which blur important distinctions and have led to considerable confusion. Fox did pure Monte Carlo. He had a deterministic mathematics problem (what is the ratio of the circumference of a circle to its diameter?) and he introduced randomness in order to get an answer. There was no randomness in the initial problem.
Ulam’s problem can be viewed as deterministic. The probability of winning a game of Canfield Solitaire is a deterministic constant, just like pi. But it can also be viewed as a question about a random variable; what is the expected value of X where X = 0 if you lose a game of Canfield and X = 1 if you win? Estimating the expected value of a random variable by taking the mean of observed values is not Monte Carlo, it is inferential statistics. This may seem like hair-splitting in this example, but the distinction is crucial in other problems.
Another confusion is that Fox did only Monte Carlo, while Ulam did Monte Carlo followed by simulation. Fox only recorded the observations of his experiments, the calculation to get pi happened only after the results were in. Ulam randomly shuffled a deck of cards and then went through a complex simulation to figure out if the arrangement was a winning or losing one. He did calculations on each random draw, not only at the end of the experiment. Even worse, you can regard his entire experiment as a simulation; he simulates someone playing a game of Canfield, including the shuffling. As there is no introduced randomness, he does not need the idea of Monte Carlo. He could describe his experiment entirely as a simulation of what he wanted to measure
Monte Carlo and Simulation
While Monte Carlo simulation is a powerful combination of tools, it is essential to understand the two distinct ideas and do each one correctly. Moreover, many Monte Carlo problems need no simulation, and many simulation problems need no Monte Carlo. Fusing the two ideas into one weakens both of them.
To see the distinction, consider the Monte Carlo part (shuffling the deck) and the simulation (playing out a game of Canfield) separately. Why use Monte Carlo? Because it would take too much computer time to try all 52 (8 × 1067) arrangements of a deck of cards. If there were fewer cards in the deck, or if there were symmetries that could reduce the number of combinations that had to be considered, we would get a better answer by stepping through all relevant combinations, one at a time. If we had a fast enough computer, we would not need Monte Carlo.
Why simulate? Because it is the fastest way to determine whether a combination of cards results in winning or losing a game of Canfield. If a clever person figured out a faster way, we would use it. It would not matter how fast our computer was, or whether we wanted an exact or approximate answer. If the game were simpler, for example, if we could tell whether a deck arrangement was winning or losing by locating the ace of spades in the deck, we would not bother simulating a game.
So for small decks and simple games, we need neither Monte Carlo nor simulation. For large decks, we need Monte Carlo. For complicated games, we need simulation. When we have complicated games played with large decks, we use Monte Carlo simulation.
Captain Fox did not need simulation. Once he saw whether the needle crossed the line or not, no further analysis was necessary. But he did need Monte Carlo. Whether the needle crosses the line depends on two factors: the distance from the center of the needle to the nearest line and the angle of the needle with respect to the lines. He could try to measure these systematically. He could place the needle at different distances from the line and rotate it to estimate the range of angles that would cause it to intersect a line. His error would depend on the fineness of his grid and the accuracy of his measurements. If he were only concerned with one dimension, either the position of the center of the needle or the angle of the needle, the systematic measurement would probably give smaller error for the same effort. Two dimensions make Monte Carlo more attractive; the simpler measurement saves so much effort that it more than compensates for the lower efficiency of random versus systematic sampling. With more dimensions, say he was also interested in making the needle length random and using paper with irregularly spaced lines, Monte Carlo would be no harder, but systematic sampling would increase dramatically in difficulty.
Moving from pi and solitaire to more general applied mathematics, we can say the same thing. We need Monte Carlo when a problem has many dimensions. It takes too much computer time to try every combination of many variables, even if each variable can only take on a few values. Monte Carlo gives only an approximate answer, but if done properly, the quality of that approximation is independent of the number of dimensions.
We need simulation when we cannot solve a differential equation analytically or (what amounts to the same thing to an applied mathematician) when the analytic solution requires numerical evaluation that takes longer than simulation. The differential equation tells us how to get from one state to the next, just like the rules of Canfield Solitaire. Solving it allows us to look at the boundary conditions (the arrangement of the shuffled deck in Canfield) and determine directly whether it is winning or losing. If we can’t solve the differential equation, we can still simulate, going from the boundary conditions one step at a time until we discover the result we want. A differential equation is like a recipe, a series of instructions that get you from boundary condition to solution; an analytic solution is like a blueprint. Both tell you how to make something, but the recipe requires going through all the steps in order while a blueprint illustrates the finished product directly.
This brings up the third problem with the Canfield example. The rules of Canfield are not a differential equation (or a difference equation, in this case, because the moves are discrete). The player has choices. One state does not determine the next; it only determines a range of next states from which the player makes a choice. A straightforward exact solution requires playing every game every possible way, which is why the Canfield Solitaire problem remains unsolved. People have pretty good estimates of the winning probability, but they rely on a combination of analysis, guesswork, and simulation. You might think the player choice only adds another dimension to the problem so, as Monte Carlo is independent of the number of dimensions, it shouldn’t make the problem harder. The problem is you cannot treat a choice as a random event (i.e., a common mistake in finance).
Derivative Pricing
Derivative pricing has the same three features that make Canfield Solitaire a bad example from which to learn Monte Carlo.
- The problems contain their own randomness (the unknown future price movements of the underlying), which is easily confused with the artificial randomness injected into the problem for Monte Carlo.
- Complex derivatives are often valued by simulation, with or without Monte Carlo, which can blur the distinction between the two tools.
- Many derivatives, such as American options, involve some choice by one or both parties to the contract. This creates another potential confusion, between randomness and choice.
Unfortunately for finance, derivative pricing is the way many quants are introduced to Monte Carlo, so they learn the latter incorrectly. This leads to problems when they later tackle problems other than pricing.
The most basic derivative pricing technique is the binomial tree, which involves neither Monte Carlo nor simulation (although it is often confused with those two things). Suppose a stock sells for US$100 today and tomorrow I know it will be either US$101 or US$99. The risk-free rate of interest is 0.02 percent per day. A one-day European call option on 100 shares with a strike price of US$100 will be worth either US$100 tomorrow (if the stock price is US$101) or zero (if the stock price is US$99). I can get the same result by buying 50 shares of stock and borrowing US$4,949 for one day. Tomorrow I will need US$4,950 to repay the loan. If the stock price is US$99, my 50 shares will just cover the repayment. If the stock price is US$101, I have US$100 profit. As the cost of buying 50 shares (US$5,000) minus the US$4,949 borrowed is US$51, that must be the price of the call option, or arbitrage is possible.
Notice that there is no randomness in this argument. It does not matter what the probability of the stock going up or down is, just what the two possible values are. There is also no simulation, just a calculation. The argument depends on some financial assumptions and simple arithmetic.
There is a convenient shortcut, however, that people often use to solve problems like this. If you invest US$10,000, the price of 100 shares, at the risk-free rate of 0.02 percent for one day, you have US$10,002. If the stock has a 51 percent chance of going up to US$101 and a 49 percent chance of going down to US$99, the expected value of 100 shares of stock is also US$10,002. If we compute the expected value of the option under this “risk-neutral probability,” we get the correct US$51 price (51 percent of US$100 and 49 percent of zero). The risk-neutral probability is not the actual probability, but it gives the correct derivative price.
The value of this shortcut can be seen if we imagine the stock continuing to move up or down US$1 in value every day for N days. I can price an N day option using the method outlined earlier, but I need to simulate (N+1) × (N+2)/2 nodes in a binomial tree. If I remember the risk-neutral probability trick, I can just compute the expected value of the derivative until a binomial distribution with p = 0.51 and discount it back to the present at the risk-free rate of interest.
Beyond Binomial Pricing
Simulation enters the picture when it is not enough to consider only the terminal nodes of the tree, when the path the security price takes makes a difference to the derivative valuation. This can happen because the derivative itself is path-dependent, that is to say the payoff depends not only on the terminal price of the underlying, but on previous prices. Asian options, for example, depend on the average price of the underlying over the interval and barrier options pay off or not depending on the maximum or minimum price reached. Another reason is the path might affect the option holder’s action, as in an American option that can be exercised any time up to expiry. Finally, we are often evaluating a dynamic position, say a hedged option position, so the outcome of the strategy depends on the path even if the derivative itself does not. Another common term for this is “non-recombining tree.” That means if the underlying ticks up in price and back down, it creates a different state of the world than if the underlying ticks down in price and back up; although the underlying price is the same, the world states do not recombine.
We try tricks to avoid considering every path. We include additional state variables, use Brownian bridges or collapse portions of the tree. But sometimes, simulation is the fastest way to price a derivative. A binomial tree with N time steps has N+1 final nodes and (N+1) (N+2)/2 total nodes, but 2N-1 possible paths through the tree. That makes exhaustive simulation practical only for small N. For some problems we can get away with a coarse time step and small N, but often we get more accuracy with a larger N, but only simulating a fraction of the possible paths.
Monte Carlo is a way to reduce the number of paths. You simulate the derivative price on some paths selected at random and hope that the average of the sampled paths is close to the average of all paths. In this case, the Monte Carlo randomness and the selection of random paths is the same randomness as the underlying security. We can think of the underlying security as picking a path at random through the tree, in which case we can think of our pricing algorithm as pure simulation, mimicking the behavior of the underlying, rather than Monte Carlo simulation.
It is usually better, however, to select another form of randomness to reduce the number of paths considered. This is particularly true when we are not doing pricing but another application such as risk management, hedge design or trading strategy analysis. Analysts who know only Monte Carlo simulation may not think about this.
Consider, for example, estimating the one-day 99 percent VaR of a short down-and-in call option (i.e., we want X, such that the contract will lose US$X or more 1 percent of the time; a down-and-in call option is one that pays off only if the underlying price falls below the knock-in level, then rises above the strike price; as we are short the option, our VaR is set in situations when the option increases in price). Monte Carlo simulation is wasteful, because we only care about a few paths (the ones that fall to the knock-in point, then go up a lot). Moreover, we have to simulate all the way to option expiry, which could be months or years away, in order to estimate the distribution of the option’s value after one day.
A more important problem with Monte Carlo simulation is we need to use the actual probability distribution of the underlying (which we typically do not know very well) to determine whether or not it knocks in, and the risk-neutral probability (which we can typically measure with precision) to compute its value at the end of one day. Any simulation with a single set of probabilities will give inaccurate answers (and it does not work to switch from actual to risk-neutral after the knock-in barrier is hit).
A better approach is to consider the nodes one day in the future that have high values for the vanilla version of the call (the same option without the knock-in feature). All we need to know is the actual probabilities of getting to these nodes after knock-in and we only need to compute enough nodes (counting down from the highest) to add up to a 1 percent probability of knock-in. Depending on the complexity of our actual probability model, this is something we might be able to compute, but if not, we could estimate it from an efficient Monte Carlo integration. This is not Monte Carlo simulation, because we are not simulating the price movements of the underlying and we are not pricing the option from the path the underlying takes. We are taking a random selection of paths in order to estimate the probability that a path from the origin to the selected one-day node hits the knock-in point. There are other ways to attack this problem, some of which involve Monte Carlo, some of which do not. My point is the Monte Carlo simulation is not a good approach, but that is no reason to reject Monte Carlo entirely.
Beyond Binomial
The other major reason trees get big in derivative analysis is when we have more than two forward branches out of each node. An N step tree with K choices at each node can have up to KN-1 terminal nodes. Recombining reduces this number, but it still can be more nodes than can be easily processed even if K and N are moderate-sized.
For example, suppose I have an underlying that can tick up or down by 0.1 percent each step (i.e., it can be multiplied by 1.001 or divided by 1.001) but that the tick size (the volatility) can increase or decrease by 10 percent each step (so 0.1 percent can go to 1.1 × 0.1 percent = 0.11 percent or 0.1 percent/1.1 =0.0909 percent). After 100 times steps, that gives 1.3 billion different terminal values for the underlying. That is too many to examine individually. This causes problems even if we are pricing a vanilla derivative whose payout is determined only by the underlying price at expiry.
Simulating paths of the underlying just increases our computation effort without benefit, as only the terminal value of the path matters. We can use Monte Carlo for this problem, however. We can select terminal values at random and compute their probabilities. This will allow us to integrate the vanilla derivative payoff to get an expected value. Note that our randomness is not the randomness of the underlying security. We pick terminal values without regard to their probabilities (in fact, we do not know their probabilities until after we pick one).
There is a crucial financial distinction among multinomial tree models. If we have K paths out of every node, we need the prices of K securities at each node in order to generate arbitrage prices for all securities (and those K securities must not be linearly dependent among the paths). In simple binomial option pricing, we use the price of the underlying security (which we know at each node because that is what goes up and down) and the risk-free security (which we know because it depends only on time step, not node within time step) to price all the options on the underlying. The assumption is sometimes called “complete markets,” as in complete markets for each possible state we can construct a security that pays US$1 in that state and nothing in all the other states.
One of the main reasons for going to multinomial trees is different derivatives on the same underlying have inconsistent prices in a binomial tree. With K paths out of each node, we can calibrate the tree to K—2 derivatives (plus the underlying price and the risk-free asset). If we do this we can obtain an arbitrage price for each remaining derivative (i.e., if the actual market price differs from our computed price, we can construct a riskless portfolio with a return better than the risk-free rate). Of course, that is only in theory; if we have to calibrate to 40 different instruments, only an optimist believes that the 41st instrument will fall perfectly into line. These models are sometimes called “local volatility” because, in principle, the entire future tree is known today.
Multinomial trees are also used for the opposite reason; that markets are not complete. In order to model the essential unhedgeable risk of positions, we need more paths leaving a node than we have securities to use as hedges. These are called “stochastic volatility” models. They do not give arbitrage prices for derivatives; instead they give a probability distribution of future values from which a price can be estimated.
In the first case, we can use Monte Carlo to determine the risk-neutral terminal distribution on the underlying that prices all our calibration instruments correctly, then use that risk-neutral distribution to price any other path-independent derivative. A superior approach recognizes there is an error in the measurement of market prices and calibrates to minimize the squared error with more calibration instruments than paths out of each node. In the second case, we use Monte Carlo to determine the actual probability distribution directly.
Going Farther with Monte Carlo
The objective of this chapter has been to give a clear idea of what Monte Carlo is and how it can be used effectively, or inefficiently. Whenever you use it, ask yourself what is the full experiment you would do if you had infinite computer time, and make sure you have a good random sample of that very large or infinite experiment. Make sure you introduce the precise randomness you need, rather than taking whatever randomness happens to be lying around. Ask yourself why the problem is high-dimensional, and if Monte Carlo is the best way to get around that. Do not automatically use Monte Carlo because you are simulating and do not neglect to consider Monte Carlo because you are not simulating. And most importantly, learn to say, “It’s so crazy, it just might work,” with a straight face.
There are many other things to learn about Monte Carlo. Some important ones are variance reduction, dimensionality reduction, proxy distributions, quasi-random numbers, control variates, antithetic variates and stratified sampling. These are all simple and easily implemented ideas that will reduce your Monte Carlo error and processing time. To paraphrase an old saying about the game of poker, “I can explain Monte Carlo in five minutes, to understand it takes a lifetime.”