Why the Monte Carlo Method is so important today

Article ID Dirk P. Kroese The University of Queensland Tim Brereton Ulm University Thomas Taimre The University of Queensland Zdravko I. Botev The University of New South Wales Keywords: Monte Carlo method, simulation, MCMC, estimation, randomized optimization

Abstract: Since the beginning of electronic computing, people have been interested in carrying out random experiments on a computer. Such Monte Carlo techniques are now an essential ingredient in many quantitative investigations.

Why is the Monte Carlo method (MCM) so important today? This article explores the reasons why the MCM has evolved from a last resort solution to a leading methodology that permeates much of contemporary science, finance, and engineering. Uses of the MCM Monte Carlo simulation is, in essence, the generation of random objects or processes by means of a computer. These objects could arise naturally as part of the modeling of a real-life system, such as a complex road network, the transport of neutrons, or the evolution of the stock market. In many cases, however, the random objects in Monte Carlo techniques are introduced artificially in order to solve purely deterministic problems. In this case the MCM simply involves random sampling from certain probability distributions. In either the natural or artificial setting of Monte Carlo techniques the idea is to repeat the experiment many times (or use a sufficiently long simulation run) to obtain many quantities of interest using the Law of Large Numbers and other methods of statistical inference. Here are some typical uses of the MCM: 1 Sampling. Here the objective is to gather information about a random object by observing many realizations of it. An example is simulation modeling, where a random process mimics the behavior of some real-life system, such as a production line or telecommunications network. Another example is found in Bayesian statistics, where Markov chain Monte Carlo (MCMC) is often used to sample from a posterior distribution. Estimation. In this case the emphasis is on estimating certain numerical quantities related to a simulation model. An example in the natural setting of Monte Carlo techniques is the estimation of the expected throughput in a production line. An example in the artificial context is the evaluation of multi-dimensional integrals via Monte Carlo techniques by writing the integral as the expectation of a random variable. Optimization. The MCM is a powerful tool for the optimization of complicated objective functions. In many applications these functions are deterministic and randomness is introduced artificially in order to more efficiently search the domain of the objective function. Monte Carlo techniques are also used to optimize noisy functions, where the function itself is random for example, the result of a Monte Carlo simulation. Why the MCM? Why are Monte Carlo techniques so popular today? We identify a number of reasons. Easy and Efficient. Monte Carlo algorithms tend to be simple, flexible, and scalable. When applied to physical systems, Monte Carlo techniques can reduce complex models to a set of basic events and interactions, opening the possibility to encode model behavior through a set of rules which can be efficiently implemented on a computer. This in turn allows much more general models to be implemented and studied on a computer than is possible using analytic methods. These implementations tend to be highly scalable. For example, the complexity of a simulation program for a machine repair facility would typically not depend on the number of machines or repairers involved. Finally, Monte Carlo algorithms are eminently parallelizabe, in particular when various parts can be run independently. This allows the parts to be run on different computers and/or processors, therefore significantly reducing the computation time. Randomness as a Strength. The inherent randomness of the MCM is not only essential for the simulation of real-life random systems, it is also of great benefit for deterministic numerical computation. For example, when employed for randomized optimization, the randomness permits stochastic algorithms to naturally escape local optima enabling better exploration of the search space a quality which is not usually shared by their deterministic counterparts. Insight into Randomness. The MCM has great didactic value as a vehicle for exploring and understanding the behavior of random systems and data. Indeed we feel 2 that an essential ingredient for properly understanding probability and statistics is to actually carry out random experiments on a computer and observe the outcomes of these experiments that is, to use Monte Carlo simulation [30]. In addition, modern statistics increasingly relies on computational tools such as resampling and MCMC to analyze very large and/or high dimensional data sets. Theoretical Justification. There is a vast (and rapidly growing) body of mathematical and statistical knowledge underpinning Monte Carlo techniques, allowing, for example, precise statements on the accuracy of a given Monte Carlo estimator (for example, square-root convergence) or the efficiency of Monte Carlo algorithms. Much of the current-day research in Monte Carlo techniques is devoted to finding improved sets of rules and/or encodings of events to boost computational efficiency for difficult sampling, estimation, and optimization problems. Application Areas Many quantitative problems in science, engineering, and finance are nowadays solved via Monte Carlo techniques. We list some important areas of application. Industrial Engineering and Operations Research. This is one of the main application areas of simulation modeling. Typical applications involve the simulation of inventory processes, job scheduling, vehicle routing, queueing networks, and reliability systems. See, for example, [14, 15, 33, 47]. An important part of Operations Research is Mathematical Programming (mathematical optimization), and here Monte Carlo techniques have proven very useful for providing optimal design, scheduling, and control of industrial systems, as well offering new approaches to solve classical optimization problems such as the traveling salesman problem, the quadratic assignment problem, and the satisfiability problem [32, 46]. The MCM is also used increasingly in the design and control of autonomous machines and robots [7, 29]. Physical Processes and Structures. The direct simulation of the process of neutron transport [39, 40] was the first application of the MCM in the modern era, and Monte Carlo techniques continue to be important for the simulation of physical processes (for example, [34, 49]). In chemistry, the study of chemical kinetics by means of stochastic simulation methods came to the fore in the 1970s [22, 23]. In addition to classical transport problems, Monte Carlo techniques have enabled the simulation of photon transport through biological tissue a complicated inhomogeneous multi-layered structure with scattering and absorption [53]. Monte Carlo techniques now play an important role in materials science, where they are used in the development and analysis of new materials and structures, such as organic LEDs [2, 38], organic solar cells [50] and Lithium-Ion batteries [52]. In particular, Monte Carlo techniques play a key role in virtual materials design, where experimental data is used to produce stochasti materials. Realizations of these materials can then be simulated and numerical experiments can be performed on them. The physical development and analysis of new materials is often very expensive and time consuming. The virtual materials design approach allows for the generation of more data than can easily be obtained from physical experiments and also allows for the virtual production and study of materials using many different production parameters. Random Graphs and Combinatorial Structures. From a more mathematical and probabilistic point of view, Monte Carlo techniques have proven to be very effective in studying the properties of random structures and graphs that arise in statistical physics, probability theory, and computer science. The classical models of ferromagnetism, the Ising model and the Potts model, are examples of these random structures, where a common problem is the estimation of the partition function; see, for example, [51]. Monte Carlo techniques also play a key role in the study of percolation theory, which lies at the intersection of probability theory and statistical physics. Monte Carlo techniques have made possible the identification of such important quantities as the critical exponents in many percolation models long before these results have been obtained theoretically (see, for example, [16], as an early example of work in this area). A good introduction to research in this field can be found in [26]. In computer science, one problem may be to determine the number of routes in a travelling salesman problem which have length less than a certain number or else state that there are none. The computational complexity class for such problems is known as #P. In particular, solving a problem in this class is at least as difficult as solving the corresponding problem. Randomized algorithms have seen considerable success in tackling these difficult computational problems see for example [27, 35, 41, 42, 48]. Economics and Finance. As financial products continue to grow in complexity, Monte Carlo techniques have become increasingly important tools for analyzing them. The MCM is not only used to price financial instruments, but also plays a critical role in risk analysis. The use of Monte Carlo techniques in financial option pricing was popularized in [3]. These techniques are particularly effective in solving problems involving a number of different sources of uncertainty (for example, pricing basket options, which are based on a portfolio of stocks). Recently, there have been some significant advances in Monte Carlo techniques for stochastic differential equations, which are used to model many financial time series see, in particular, [20] and subsequent papers. The MCM has also proved particularly useful in the analysis of the risk of large portfolios of financial products (such as mortgages), see [37]. A great strength of Monte Carlo techniques for risk analysis is that they can be easily used to run scenario analysis that is, they can be used to compute risk outcomes under a number of different model assumptions. A classic reference for Monte Carlo techniques in finance is [24]. Some more recent work is mentioned in [19]. 4 Computational Statistics. MCM has dramatically changed the way in which Statistics is used in todays analysis of data. The ever increasing complexity of data (big data) requires radically different statistical models and analysis techniques from those that were used 20100 years ago. By using Monte Carlo techniques, the statistician is no longer restricted to use basic (and often inappropriate) models to describe data. Now any probabilistic model that can be simulated on a computer can serve as the basis for a statistical analysis. This Monte Carlo revolution has had impact in both Bayesian and frequentist statistics. In particular, in classical frequentist statistics, Monte Carlo methods are often referred to as resampling techniques. An important example is the well-known bootstrap method [13], where various statistical quantities such as p-values for statistical tests and confidence intervals can simply be determined by simulation without the need of a sophisticated analysis of the underlying probability distributions; see, for example, [30] for simple applications. The impact of MCMC sampling methods on Bayesian statistics has been profound. MCMC techniques originated in statistical physics [40], but were not widely adopted by the statistical community until the publication of the seminal paper [17]. MCMC samplers construct a Markov process which converges in distribution to a desired high-dimensional density. This convergence in distribution justifies using a finite run of the Markov process as an approximate random realization from the target density. The MCMC approach has rapidly gained popularity as a versatile heuristic approximation, partly due to its simple computer implementation and trade-off between computational cost and accuracy; namely, the longer one runs the Markov process, the better the approximation. Nowadays, MCMC methods are indispensable for analyzing posterior distributions for inference and model selection; see [21] and [44]. A recent monograph on the topic is [4]. The Future of MCM There are many avenues relating to the MCM which warrant greater study. We elaborate on those which we find particularly relevant today. Parallel Computing. Most Monte Carlo techniques have evolved directly from methods developed in the early years of computing. These methods were designed for machines with a single (and at that time, powerful) processor. Modern high performance computing, however, is increasingly shifting towards the use of many processors running in parallel. While many Monte Carlo algorithms are inherently parallelizabe, others cannot be easily adapted to this new computing paradigm. As it stands, relatively little work has been done to develop Monte Carlo techniques that perform efficiently in the parallel processing framework. In addition, as parallel processing continues to become more important, it may become necessary to reconsider the efficacy of algorithms that are now considered state of the 5 art but that are not easily parallelizabe. A related issue is the development of effective random number generation techniques for parallel computing. Non-asymptotic Error Analysis. Traditional theoretical analysis of Monte Carlo estimators has focused on their performance in asymptotic settings (for example, as the sample size grows to infinity or as a system parameter is allowed to become very large or very small). Although these approaches have yielded valuable insight into the theoretical properties of Monte Carlo estimators, they often fail to characterize their performance in practice. This is because many real world applications of Monte Carlo techniques are in situations that are far from asymptotic. While there have been some attempts to characterize the non-asymptotic performance of Monte Carlo algorithms, we feel that much work remains to be done. Adaptive Monte Carlo Algorithms. Many Monte Carlo algorithms are reflexive in the sense that they use their own random output to change their behavior. Examples of these algorithms include most genetic algorithms and the cross-entropy method. These algorithms perform very well in solving many complicated optimization and estimation problems. However, the theoretical properties of these estimators are often hard or impossible (using current mathematical tools) to study. While some progress has been made in this regard [8, 25, 36], many open problems remain. Improved Simulation of Spatial Processes An area of Monte Carlo simulation that is relatively undeveloped is the simulation of spatial processes. Many spatial processes lack features such as independent increments and stationarity that make simulation straightforward. In addition, when simulating spatial processes, it is often the process itself which is of interest, rather than a functional of it. This makes the use of approximations more problematic. The current state of the art for simulating many spatial processes is based on MCMC techniques. The convergence of MCMC samplers is difficult to establish (unless using often unwieldy perfect simulation techniques) and it takes a very large simulation run to produce samples that are sufficiently independent of one another. A major breakthrough would be the development of more efficient techniques to generate realizations of these processes. Rare Events. The simulation of rare events is difficult for the very reason that the events do not show up often in a typical simulation run. Rare-events occur naturally in problems such as estimating high-dimensional integrals or finding rare objects in large search spaces; see, for example, [31, 46]. By using wellknown variance reduction techniques such as importance sampling or splitting it is possible to dramatically increase the efficiency in estimating rare event probabilities; see [32, Chapter 9] for an overview. The theory of large deviations [5] and adaptive estimation methods [6, 9, 46] give some insights into how the system behaves under a rare event, but simulating a system conditional on a rare event occurring is a difficult and interesting problem, which deserves much more 6 attention. As an extreme example, it could be argued that the laws of physics are conditional on the occurrence of the rare event that human beings exist (or on a rare event that is still to happen!). Quasi Monte Carlo. The adaption of Monte Carlo techniques for use with quasi-random number generators remains attractive in particular, for multi-dimensional integration problems due to their faster rate of convergence than traditional techniques. While there has been significant work in this area [12, 11, 43], the wholesale replacement of random number generators with quasi-random counterparts can lead to difficulties, for example the under- or over-sampling of the sample space via inverse-transform techniques. Conclusion The MCM continues to be one of the most useful approaches to scientific computing due to its simplicity and general applicability. The next generation of Monte Carlo techniques will provide important tools for solving ever more complex estimation and optimisation problems in engineering, finance, statistics, mathematics, computer science, and the physical and life sciences.

Why the Monte Carlo Method is so important today uploaded to the homework. Please write a one page summary of this article. Make sure that you have your reflections at the end of your review of the article. Have your references