Monte Carlo Techniques

Type of physical science: Computation

Field of study: Numerical methods

Monte Carlo techniques involve the solution of problems through the computation of random numbers and their incorporation into the construction of simulation models of physical systems or the computation of characteristics of those systems.

Overview

In any science, once a problem is exactly defined, it may be categorized as one of the following successively more difficult cases: analytically solvable, analytically describable but not analytically solvable, and not analytically describable. Analytically solvable problems can be described by equations that can be solved. Familiar examples are the motion of a normal ball under gravity or a block on an inclined plane.

In the second (worse) category are problems that can be described by equations that cannot be solved exactly. Instead, approximation methods are required because those equations are too complex to solve. Exactly solving higher-degree algebraic and most nonalgebraic equations is a rarity. A differential equation may be too hard to solve exactly, may not have an answer in finite terms, or may have no solutions. Approximation methods may be used.

The third and worst category are problems that can be described, but not completely, by one or a set of equations. Perhaps the relationships in the equations describe much of the system, but not all of it or not enough of it for solution. Sometimes, a system may be too complex, analyzed at an inappropriate level, or behave "probabilistically" because of the contribution of massive numbers of particle influences. Some problems involve distributions and not direct numbers. In studying these complex systems where a desired function f(x) is not defined explicitly or in closed form, standard approximation techniques and analytic methods may be deficient.

At times, no systematic means exist for evaluating the sum (or average) of all cases in a system. For example, if one asked, "In any arbitrary chessboard, how many pieces are threatened at any moment?" there is no method that exists for summing up all cases effectively. Similarly, in physics, configuration problems arise for which there is no way to evaluate all cases. The best one can do is to compute a large representative sample of cases.

Problems in this worst category require this most powerful (and unfortunately slowest) of techniques: simulation and Monte Carlo methods. While these methods are capable of attacking almost any problem and are interesting as modeling tools, they are last-resort methods because of slow convergence. Nevertheless, simulations can test models under easily modified constraints, thereby answering "what-if" questions and permitting sensitivity analysis of systems.

The restricted or classical definition of Monte Carlo methods deals with the computation of pseudorandom numbers and their use in computing integrals. A computer cannot compute pure random numbers because, by definition, they are not computable. Truly random number sequences are an abstract construction, having no pattern because each next number is infinitely hard to compute. Instead, programs called random number generators can compute numbers that appear to have no pattern and that satisfy certain statistical conditions. For brevity, pseudorandom numbers are called random numbers. Fast random number generators can produce millions of random numbers in minutes on personal computers. Prior to computers, these methods would be too inefficient for practical purposes. This random number generator would then be incorporated into a larger program, which computes integrals. An integral is a mathematical tool in calculus that can compute areas under curves, volumes under surfaces, and other important characteristics of objects. If one has a function f(x) and two points A and B on the x-axis (where A < B), then the area under the curve f(x) and bounded on the left and right by A and B is often a desired value. In simulation, a program can compute, for example, a million values of x randomly distributed between A and B and from each value x compute a value for f(x). Taking the average of those values (call it AVE), one has a good estimate of the average value or height of f(x)in the interval. Since the length of the interval is (B - A), the program computes AREA = (B-A)*AVE, the old formula for the area of a rectangle as a product of base times height.

In this way, a Monte Carlo program can compute areas under arbitrary curves. Where the symbolic methods of integration in calculus fail and even approximation techniques such as the trapezoidal method and Simpson's rule are inadequate, Monte Carlo methods can succeed.

Monte Carlo methods can compute volumes and higher-dimensional analogues of area, too.

A more general usage of the term "Monte Carlo method" is as a synonym for probabilistic simulation. In probabilistic simulation, a program is written that duplicates the behavior of a real-world system and uses a random number generator to model the probabilistic aspects of that system. Classical Monte Carlo methods are a subset of this broader concept.

For example, to simulate the behavior of one thousand coin tosses and to compute the resulting statistics, a program can be written with the following design (written in English for convenience):

STEP 1: SET TALLY T = 0.

STEP 2: GENERATE A RANDOM NUMBER R WITH VALUE 0 OR 1.

STEP 3: IF R HAS VALUE 1, THEN ADD 1 TO TALLY T.

STEP 4: REPEAT STEPS 2 AND 3 FOR 1000 TIMES.

STEP 5: PRINT TALLY.

This program will count in variable TALLY how many times heads was the result of a toss. By convention, it is assumed that 1 stands for heads and 0 is associated with tails. By the end of the program, one can print the total number of heads. Note that the whole process "duplicates" reality so that a real one thousand-toss experiment could be conducted by hand.

This example seems trivial but can be modified to attack harder questions. Step 2 could be modified so that a die is tossed instead of a coin. Likewise, a few steps could be added that would simulate the tossing of arbitrarily many dice and compute their sums, a nontrivial situation. This capacity for easy modification demonstrates the power of these methods to model and observe new behaviors of systems under alternate constraints or assumptions.

Often, probabilistic simulations are conducted for the computation of final statistics.

Sometimes, the goal is an interactive model with graphical imaging. In this way, molecular systems are modeled and simulated on a graphical computer screen. Each moment on the screen is an instantaneous snapshot of the system. As a pedagogical tool or a research tool, simulations are used for their capacity to create an "artificial reality" in a dynamic manner.

One important subcategory of probabilistic simulations is the queuing model. A queue is a waiting line, a first-in, first-out system. Queues occur wherever resources are shared and as flows with backlogs develop. Notable examples are airport flights using a runway, bank teller lines, and data-packets flowing down networks. Many special simulation programming languages exist for designing queuing models.

Besides probabilistic simulation, the other major type of simulation is deterministic.

Deterministic simulations programs duplicate real-world systems, which have no randomness.

"Determinism" here implies a system being characterized by rules that result in the same next state given the same history, initial state, and inputs for the system. Examples of deterministic systems are quite common, constituting most experiments in beginning physics. The trajectory of a baseball, blocks on inclined planes, weights on a spring, and basic pulley problems are standard deterministic simulation problems.

Simulations can also be classified as discrete-event or continuous. Continuous simulations involve systems that have change occurring continuously, in which smaller increments of time have smaller effects and change occurs gradually. Examples of continuous simulation systems include the motion of planets, heat emission of a steady flame, and many other physical phenomena.

Discrete-event simulations have change occurring in critical points in time, in incidents called events. Generally, the discrete events are a matter of perspective. Queuing models are popular examples of discrete-event systems. In a bank waiting line, examples of events are: customer arrives and is queued, customer moves off the queue to be served by a teller, and customer leaves. Perspective comes to play in that even pool table simulations can be programmed as discrete-event systems, with each ball collision being an event. Although the balls move continuously, the "critical" (from our perspective) events occur only when a collision disrupts the inertia. Note that a rough simulation can be improved by taking into account factors that would otherwise be neglected. In the pool table model, factors such as table vibration, spin, and atmospheric conditions could be added.

Applications

Applications of Monte Carlo methods encompass the spectrum of all sciences. In most subdisciplines of physics, the computation of volumes, areas, and arc-lengths (or path lengths) of arbitrary subspaces, surfaces, and curves is essential. One study computed the volume of nine-dimensional spheres. The classical Monte Carlo method for integral computation can also compute the center of gravity and moment of inertia of arbitrary objects, especially in the nonuniform density case. Nonconvex shapes and surfaces defined implicitly are prime candidates for the Monte Carlo approach. Fluid pressures and forces acting on the surfaces of submerged objects have been calculated through these methods. Total work done by forces acting on objects and other integrals occur in every facet of physics and have been attacked by classical Monte Carlo methods.

Rocket launching is a critical situation in physics, one where errors could result in catastrophes. Simulation of rocket launchings and subsequent activities are repeatedly conducted.

Simulations are applied in calculating paths of orbiting satellites and several probes exploring the solar system.

Missile trajectories and antimissile missile systems have been simulated numerous times. A simplified programming exercise for computing and plotting trajectories may require less than thirty lines of program code. While some curves of pursuit have been analyzed formally, simulation is the preferred methodology.

Combat simulation can be quite complicated. Even the locally planar motion of tanks involves many issues of timing, turning, terrain, its friction, projectile trajectories, the physics of explosions, and its dual, structural stability. Again, intensive simulation prior to production of even one physical model can avoid prohibitively costly mistakes and trial-and-error redesigning of prototypes. If one combination of features is nonoptimal in battle simulations, others must be simulated. Testing new designs requires only rewriting some simulation code or modifying inputs and rerunning.

Simulation serves a prominent role in designing networks for data transfer. Protocols, access methods, packet sizes, cabling, and node or site location are critical variables. Once physically implemented, these characteristics are very expensive to modify. All "what-if" questions must be initially addressed in the simulation phase. This situation is similar to the simulation of traffic models in the design of highways, roads, and their policies. This optimizing of the distribution of limited resources among competing consumers, components, or users is one of the primary goals of simulations. Cities "compete" for electric power usage at different peak load times. Species compete for biochemical resources. Concurrently executing computer programs compete to access disk drives. Simulation by computer of these diverse systems has been a recurrent theme in their respective literatures.

Simulation is used to duplicate the behavior of electric circuits. Components are specified and "connected" in a high-level simulation-oriented programming language or package.

This is followed by program execution, either to determine the behavior of the system, to confirm a theoretical model, or to verify the model prior to physical construction. Where inputs are required, random, semirandom, or preconditioned inputs could be supplied and feedback recorded. Trying all possible input patterns is not always feasible. This approach has been employed in testing computers as large-scale circuitry.

Simulations can determine if different components work compatibly and which components will observably affect performance, thereby justifying added costs. Simulations can determine if components cannot synchronize properly with others. In a cost-effective engineering design example, a standard presupposition equates adding memory caches with increased computer processing speed. Memory caches are extremely fast but have very expensive memory that reduces access time to standard memory on a computer. While larger caches will decrease memory access time, the speed benefits diminish after a point, while the cost of cache is linear, each extra chip costing a fixed price. Probabilistic simulations show that even doubling cache size could produce insignificant improvements (less than 5 percent) under the prevalent usage.

Small caches are generally sufficient. Other simulations compare disk drives, disk caches, and other subsystems in the computer.

Numerous simulations are conducted of multiuser computer time-sharing policies.

Each user or concurrent process gets a fraction of execute time in every second. How long each task has to run on the computer (called a time slice) before being temporarily suspended is critical. Too many time slices wastes much system overhead going from one task to another, while too few causes other problems. Some tasks are resource hogs and should run at night.

Other key processes are tightly coupled to the operation of the computer and must have high priority to avoid system freeze-ups. Simulations resolve these delicate balance problems that defy analytical solution.

In pure physics, random-walks and Brownian motion are popular simulations.

Particle-oriented simulation, especially with massive numbers of particles, is in the forefront of physics research. Simulation of clouds, fluid diffusion, mixing, and dispersion phenomena are central topics of concern in dynamics and chaos theory. Some boundary-value problems can be solved using Monte Carlo methods, too.

Simulations are used extensively in meteorology and forecasting. Several simulations have been conducted on the "greenhouse effect" on the atmosphere as well as more conventional subjects. Similar types of simulations have been used in studying another popular doom scenario, the "nuclear winter."

Chemical pollutant distributions in soil, air, and water are continually being simulated.

Reservoir facilities have also been modeled. The design of toxic waste facilities involves simulations with parameters such as depth, porosity of the adjacent rock beds and sediment layers, precipitation, barrier decay rates, and decomposition rates of toxic compounds. Acid rain damage of forests is another illustration.

Simulation is a powerful tool in chemical engineering. Maximizing yields in production processes while maintaining optimal conditions for reaction rates and delicate balances requires simulation. Effects of drugs and combinations of them have also been tested by computer first. Diffusion and fluid transfer is a common simulation area. Salinity in tanks with sources and sinks is an elementary programming exercise.

Paralleling those in chemical engineering, simulations of assembly lines, machine repair shops, and other physical production processes serve central roles in modeling and scheduling. Prior to automating, simulations can ascertain where robotic technology would be most advantageous. Queuing models can locate bottlenecks.

In a different type of simulation, salinity was an ecological issue. Dams, irrigation, seasonal droughts, and other factors were amalgamated into a program. Saline water from seas and oceans creeps upstream as freshwater flow decreases. Simulations have modeled the calamitous system. Inland irrigation and dams benefited some farmers but caused salinity increases in downstream δs and marshes, destroying highly productive farmlands and ecosystems. Simulations often express complexities in real systems that careful analytical methods overlook. Simulation can represent complex "second-order" relationships not expressed analytically.

Context

The earliest probabilistic simulations occurred in prehistory. Predating any computers, board games using dice were used as a source of random numbers and sums. The game "Monopoly" simulates real estate investment systems, with serious papers in the mathematical literature interpreting it as a Markov chain. Simulation programs are used for instruction in ecology and other sciences. Even simple microcomputer pool-table simulation games teach concepts of, and have game-setting options for, collisions, momentum, energy dissipation, static friction, and dynamic friction, all principles of physics.

The earliest example of Monte Carlo methods as a computational tool is Buffon's needle problem. By tossing needles (similar to generating random numbers) on the appropriate geometric structure and collecting statistics, π can be computed.

On a more formal note, an early scientific research application of Monte Carlo methods is the neutron diffusion problem. A program can simulate the zigzag path of random collisions of a neutron and determine the number of neutrons penetrating a shielding barrier. A popular location to gamblers, the term "Monte Carlo" method was first used as a humorous code name for the secret neutron diffusion project, which contributed to the 1940's atomic bomb effort.

Stochastic processes such as particle transport, reactor design, particle cascades, and quantum many-body problems can be solved through Monte Carlo techniques.

The N-body problem is one physical problem that can be solved by simulation. It involves the motion of many bodies under the collective influence of one another. For example, four stars "orbit" around one another under gravitational influence. This problem cannot be resolved analytically.

Simulations are useful in molecular modeling. Monte Carlo methods in chemistry are used in the computation of the equation of state for gases and liquids. John M. Hammersley and D. C. Handscomb's monograph MONTE CARLO METHODS (1964) presents Monte Carlo solutions to this and other problems in statistical mechanics as well as polymer modeling.

Many simulations in astronomy involve computing the cumulative effects of massive numbers of particles moving under the influence of forces. Models of chaos have been applied to astrophysics from the level of clouds up to galactic structures. R. W. Hockney and J. W.

Eastwood's COMPUTER SIMULATION USING PARTICLES (1981) describes some progress along these lines.

Probabilistic programs have an even more pronounced, yet strange role in theoretical computer science. Random numbers, being among the "hardest" to compute, have whole theories of complexity based on them. In contraposition, probabilistic programs have been designed that offer speed-ups beyond standard algorithms, solving otherwise intractable problems.

Animation, fractal, and graphical simulations are growing areas. Dynamics of gases and fluids are major research topics. Many teams of university physicists are working on particle-oriented simulations executed on highly parallel computers. Computers with tens of thousands of CPUs (central processing units) are being designed to investigate and answer deep questions about these systems for future generations.

With simulation, real-world systems can be explored without building them physically or even having explicit formulas characterizing the specific properties considered. As new string theories and very high dimensional physical theories emerge, Monte Carlo methods of integrations may adopt an even greater role in computation, perhaps an exclusive one.

Principal terms

CONVERGENCE: the process of approaching successively closer to an exact numerical answer through further computation

DYNAMICS: the study of motion and inducing forces

PROGRAM: an ordered sequence of instructions that determines the behavior of a computer and effectively computes numerical values as a result

RANDOM NUMBERS: a sequence of numbers that cannot be predictably computed using a formula; the next number in the sequence cannot be determined from previous ones

SIMULATION: a duplication of the behavior of a real-world system by a program

Bibliography

Aburdene, Maurice F. COMPUTER SIMULATION OF DYNAMIC SYSTEMS. Dubuque, Iowa: Wm. C. Brown, 1988. A wide variety of applications make this an exceptional but nontrivial textbook in simulation design and programming. Diffusion, network designs, economics, circuit modeling, thermal systems, networks, trajectories, arms races, and oscillators are but some examples. Requires slow reading, but some of the more technical chapters can be skimmed or skipped. Some simple BASIC and Pascal programs are worth running. Most of the texts below are easier but not as holistic and oriented toward dynamics.

Barrodale, Ian, Frank D. K. Roberts, and Byron Ehle. ELEMENTARY COMPUTER APPLICATIONS IN SCIENCE, ENGINEERING, AND BUSINESS. New York: Wiley, 1971. As self-contained introductions, few texts come close to the unadorned elegance of this one in presenting numerical methods and the design of programs for them. Chapter 2 includes classical Monte Carlo methods. Chapters 3 and 4 cover deterministic and probabilistic simulation as a series of modeling applications, complete with explanations, flowcharts, programs, and informative exercises. Excellent resource for self-instruction in foundations. For a textbook, it requires minimal background. A simple but not dilute text.

Gleick, James. CHAOS: MAKING A NEW SCIENCE. New York: Viking, 1987. An account of the development of chaos theory and its applications in mathematics and science. Devoid of equations, exercises, or other textbook features, this highly readable bestseller is geared for the general public. Simulations, chaos, dynamics, fractals, and strange attractors are combined into a historical depiction of the personalities, theorems, and the intensely fascinating process of discovery. Diagrams and stunning photographs enhance the narrative.

Neelamkavil, Francis. COMPUTER SIMULATION AND MODELLING. Chichester, England: Wiley, 1987. While not easy reading, this simulation textbook has numerous applications discussed in several sciences such as circuit design, beam bending, springs, and predator-prey models.

Rice, John K., and John R. Rice. INTRODUCTION TO COMPUTER SCIENCE. New York: Holt, 1969. Chapter 7-5 is an introduction to simulation programming concepts, notably pursuit and the N-body problem. Programming is stressed, but it is quite readable and requires little mathematics.

Roberts, Nancy, et al. INTRODUCTION TO COMPUTER SIMULATION. Reading, Mass.: Addison-Wesley, 1983. A readable textbook with a minimum of mathematical analysis and a maximum of assorted applications, modeling, descriptive discourse, and conceptual development.

Shannon, Robert E. SYSTEMS SIMULATION. Englewood Cliffs, N.J.: Prentice-Hall, 1975. Few purely descriptive textbooks on simulation exist; this one comes close. Some technical chapters.

Nonlinear Maps and Chaos

Numerical Solution of Differential Equations