- Discuss how random numbers are important in modeling and simulation
- Discuss the kind of answers that should interest you when random numbers are needed.
- Describe how a Monte-Carlo simulation is different from other simulations.
A model or simulation where no randomness is involved.
A model or simulation that uses random numbers so that the system states and the output results are not exactly predictable from run to run.
Check Your Understanding
- Are random effects present in nearly every real-world system?
- Do random effects make it difficult to analyze a system because the same input does not always produce the same output?
- Are there techniques that allow us to analyze systems based on the results from many runs?
Introduction to Monte Carlo Methods
Many people think of a computer as just a fancy calculator, a device that takes an input and calculates a value. Further, if you give it the same value over and over, it will always calculate the same result. This is in sharp contrast with everyday experiences of flipping a coin, throwing dice, dealing cards, and somehow always ending up in the slowest checkout line at the grocery. The computer literate know that sophisticated software models often use random numbers to simulate flipping a coin, throwing dice, and waiting in line. Models that rely on random numbers are called stochastic (as opposed to deterministic) and simulations that rely on random numbers are called Monte Carlo simulations5.
Almost any simulation that attempts to model real-world behavior relies to some extent on Monte Carlo techniques. Uncertainty about input values and the way they change over time along with noise and other disturbances can be modeled and analyzed using random numbers and Monte Carlo techniques. The same techniques allow us to model and simulate systems that are too complex to model any other way. For example, simulating the behavior of atoms in an atomic bomb was the first recognized application of Monte Carlo simulation in 1945 (Metropolis 1987). Since then, Monte Carlo techniques have been used to model economics, fluid dynamics, explosions, and yes, even waiting in line.
Think about the pool-filling example in the “Continuous Simulation” section. If someone asked you how long it would take to fill the pool you could find the answer as long as you knew the flow rate and the size of the pool. Suppose I told you that the faucet isn’t very reliable and turns on with a slightly different flow rate every time. Now what would you say about how long it will take to fill the pool? If you want to be accurate, you need to qualify your answer with something like, the fastest, the slowest, or on the average. What if I make the problem a little harder by telling you to use five unreliable faucets instead of one? I could make the problem harder still by telling you that the water pressure, and consequently the flow rate, changes every 5 minutes. At some point, there are too many unknowns affecting the amount of water flowing into the pool, making it difficult, if not impossible, to directly calculate the fastest, slowest, or average time needed to fill it. This situation is a good candidate for a Monte Carlo simulation. As long as we have a good characterization of the potential flow rates and changes, we can make multiple simulation runs using different values and characterize how long it will take to fill the pool. Even though we are using the example from the “Continuous Simulation” section, it is important to realize that a continuous-simulation model is not required. Monte Carlo simulation and the simulation method used to solve each run are separate choices. Monte Carlo techniques can be used with any simulation paradigm (i.e., discrete-event, continuous, agent-based, and system dynamics).
Let’s look at a simple example. Suppose the faucet turns on with a flow rate anywhere between 1 and 3 liters per second and the pool holds 600 liters. The slowest time to fill the pool would be 600 seconds . The fastest would be 200 seconds . What is the average time it would take to fill the pool? The answer to this question is not as easy as it seems. Half way between the slowest time (600 seconds) and the fastest time (200 seconds) is 400 seconds, but that is not the right answer. The average flow rate is 2 liters per second, resulting in a time of 300 seconds, but that is not the right answer either. Finding the average time in this problem is more difficult than it first appears because time is inversely proportional to the rate. Calculus in the form of integration can be used to find the correct answer. A Monte Carlo simulation can also be used to find a very good approximation to the answer. The Monte Carlo procedure first obtains a large number of randomly selected flow rates drawn from the domain of possible rates from some probability density function. Next, a fill time is calculated for each rate. Finally, an average over the resulting fill times is determined.
A plot of 5000 random flow rates is shown in Figure below. The values appear evenly or uniformly distributed between 1 and 3. A plot of fill times is shown in Figure below. Time values are not uniformly distributed between the minimum and maximum, and this is exactly why it isn’t easy to find the average. An average over the 5000 values shown in Figure below is 329.8 seconds compared to the theoretically correct value, calculated by solving the integral, of 329.584. The average is a good approximation but it is not an exact match. Different sets of random flow rates will result in different average values and a larger set of random values will generally result in a better approximation. The theoretically correct value was found by evaluating the following integral,
where is the volume of the pool and is the flow rate. It isn’t important to understand exactly how this equation was derived nor is it important to understand how to evaluate it. The important thing to understand is that Monte Carlo simulation is another way of performing integration. Unlike integration in continuous time or continuous space simulations, this integration targets input values and the range over which they can change. The output isn’t one definitive value but a range of output values we can use to answer interesting questions like fastest, slowest, and average.
Random values for (a) flow rate and (b) corresponding fill times.
Monte-Carlo Simulations in Engineering
In a real-life engineering problem, there is rarely one right answer. Rather, there are usually many answers that satisfy the project requirements. As a system gets more complex, there are increasing number of parameters that can affect the outcome. In most problems, the values of input parameters are not known with absolute certainty. As more parameters affect the outcome of the system, there are more combinations in which different parameters can combine and produce different outcomes. If a system is designed to operate only for when every parameter behaves perfectly, then the system can break when one input parameter does not behave as expected. Engineers need to design systems that are robust, and are able to withstand most probable conditions. Monte Carlo simulations help engineers get a grasp on how a system behaves when the exact value of each parameter impacting the outcome is not known. Let’s illustrate this with an example.
Let’s say NASA is trying to land a rover on the surface of Mars. A rover is a mobile platform or vehicle that carries scientific instruments and cameras. The project scientists have identified an interesting scientific site on the planet’s surface where they would like the rover to land. It is now up to the engineering team responsible for safe landing to place the rover as close to the targeted site as possible. Is it possible to land the rover at the exact location requested by the project scientists? The answer is very unlikely. There are too many uncertainties and too many unknowns to pull off a perfect mission and land the rover with great accuracy. These unknowns include air density, winds, aerodynamic properties of the entry capsule, parachute drag, etc. If the engineers responsible for landing can’t deliver the rover to the surface with pinpoint accuracy, then the scientists would like to know how close the rover could be delivered to the target. Landing engineers are able to provide such information using Monte Carlo simulations. How does Monte Carlo simulation work?
Engineers responsible for safe landing of the rover build computer simulations of the entire landing sequence. Such simulations predict the trajectory of the rover from when it enters the atmosphere all the way to touchdown. The entry, descent, and landing sequence of the Mars Exploration Rovers (MER) is shown graphically in Figure below. The twin rovers both landed successfully on Mars in 2004 using the landing sequence depicted in the diagram.
Mars Exploration Rover Entry, Descent, and Landing Sequence.
The listing below summarizes some of the parameters that affect the landing location of the rover.
- Position of the rover when it enters Mars’s atmosphere.
- The entry angle of the rover with respect to local horizon when entering the atmosphere.
- Aerodynamic drag of the capsule protecting the rover during entry.
- Mars atmospheric density.
- Mars’ winds.
- Aerodynamic drag force on the parachute.
- Aerodynamic drag force on the airbag system.
- Thrust force generated by the retro-rocket engines.
- Timing of all the events during the landing sequence.
The list above is a small subset of all the parameters that determine the trajectory of the rover and its landing location. This list is provided as a representative of the complete set to give the reader an idea about how the process works. Project engineers do not know the value of any of the parameters listed with 100 percent certainty. However, they know an average value for each parameter, and they have approximations for an upper and lower limit on that value. In order to account for all probable landing scenarios, the engineers run thousands to millions of simulations of the entire landing sequence. The value of each parameter is varied randomly with each run in accordance to that parameter’s assumed probability density function using a random number generator. In most engineering problems, the probability density function of the variables is either uniform or Gaussian. For a more in-depth discussion of these distributions refer to the “Monte Carlo Simulations in Math and Science” chapter later in the book. Such Monte Carlo simulations are used to study how the system behaves in a wide variety of conditions. Because of the time delay in getting radio transmissions to Earth and back, Mars missions do not have the luxury of calling home and getting instructions and making adjustments. Monte Carlo simulations are used to design a landing system that is robust and able to react to most probable off-nominal conditions. Figure below shows the predicted landing ellipse footprint for the first of the twin Mars Exploration Rovers. If you place a dot for the landing location from each individual simulation out the Monte Carlo set, and draw a line around all dots, the resulting figure is generally shaped as an ellipse, hence the name “landing ellipse.” Note that the objective of this Mars mission was to land the rover inside the crater. The Gusev crater was thought to have been an ancient Martian lake where conditions may have been suitable for life. The “landing ellipse” could not be larger than the crater itself, otherwise part of the crater rim would fall inside the ellipse. No part of the crater rim could be inside the landing ellipse because crater walls are unsafe regions to land, with cliffs and high slope terrain. Monte Carlo simulations of the entry, descent, and landing sequence provide the necessary data to let the engineers and scientists know that the rover could be delivered inside the crater with a high degree of probability.
Mars Exploration Rover Langing Ellipse
Monte Carlo simulations could be used on any of the simulation methodologies discussed previously, including discrete-event, continuous, agent-based, LVC, system dynamics, or any other methodology not covered in this chapter. Monte Carlo simulations help identify problems that may lie in the outer boundaries of a system design, and gives project planners, engineers, and managers the opportunity to design more robust systems.
- Almost every real system is influenced by random events.
- Random events can be simulated using random numbers
- Monte Carlo simulation requires many runs because the result from each run depends on the random values drawn for various input, initial, and internal conditions.
- Monte Carlo results have to be described based on the results over many runs. The descriptions include values such as minimum, maximum, and average.
- What is the principal difference between a stochastic versus a deterministic simulation?
- Is each run in a Monte Carlo simulation stochastic or deterministic?
- If the flow rate in Figure above uniformly distributed from 1 to 3, why doesn’t the time required to fill the pool in Figure above also appear to be uniformly distributed?
- Why are Monte Carlo results only an approximation?
- How can you reduce the error in the approximate answer?
Further Reading / Supplemental Links
Points to Consider
This section touched on the use of uniformly distributed random variables, that is, every value in the range is equally likely. Throwing dice and drawing cards are good examples of uniform random variables. Most naturally occurring random variables are not uniform but rather Gaussian (i.e., bell shaped). What do you have to do to apply Monte Carlo techniques for Gaussian random variables? (Suggested response: Basically, change the random number generator from a uniform generator to Gaussian and repeat the trials. For advanced students this could be the lead in for a discussion of the central limit theorem.)
5The name comes from the various games of chance at the casinos in Monte Carlo, Monaco.