Monte Carlo Methods
Monte Carlo methods are a computational technique used to solve problems through random sampling. They are particularly useful for estimating complex mathematical expressions or simulating systems with many variables. By generating a large number of random samples, Monte Carlo methods provide approximate solutions to problems that may be difficult or impossible to solve using traditional deterministic algorithms.
7 Key excerpts on "Monte Carlo Methods"
eBook - ePubData Science and Machine Learning
Mathematical and Statistical Methods
- Dirk P. Kroese, Zdravko Botev, Thomas Taimre, Radislav Vaisman(Authors)
- 2019(Publication Date)
- Chapman and Hall/CRC(Publisher)
...CHAPTER 3 M ONTE C ARLO M ETHODS Many algorithms in machine learning and data science make use of Monte Carlo techniques. This chapter gives an introduction to the three main uses of Monte Carlo simulation: to (1) simulate random objects and processes in order to observe their behavior, (2) estimate numerical quantities by repeated sampling, and (3) solve complicated optimization problems through randomized algorithms. 3.1 Introduction Briefly put, Monte Carlo simulation is the generation of random data by means of a computer. These data could arise from simple models, such as those described in Chapter 2, or from very complicated models describing real-life systems, such as the positions of vehicles on a complex road network, or the evolution of security prices in the stock market. In many cases, Monte Carlo simulation simply involves random sampling from certain probability distributions. The idea is to repeat the random experiment that is described by the model many times to obtain a large quantity of data that can be used to answer questions about the model. The three main uses of Monte Carlo simulation are: M onte C arlo simulation Sampling. Here the objective is to gather information about a random object by observing many realizations of it. For instance, this could be a random process that mimics the behavior of some real-life system such as a production line or telecommunications network. Another usage is found in Bayesian statistics, where Markov chains are often used to sample from a posterior distribution. ☞ 48 Estimation. In this case the emphasis is on estimating certain numerical quantities related to a simulation model. An example is the evaluation of multidimensional integrals via Monte Carlo techniques. This is achieved by writing the integral as the expectation of a random variable, which is then approximated by the sample mean...
eBook - ePub- Patrick O'Connor, Andre Kleyner(Authors)
- 2011(Publication Date)
- Wiley(Publisher)
...4 Monte Carlo Simulation 4.1 Introduction Monte Carlo (MC) simulation is a useful tool for modelling phenomena with significant uncertainty in inputs and has a multitude of applications including reliability, availability and logistics forecasting, risk analysis, load-strength interference analysis (Chapter 5), random processes simulation including repairable systems (Chapter 13), probabilistic design, uncertainty propagation, geometric dimensioning and tolerancing, and a variety of business applications. The concept of the Monte Carlo method comes from the gaming tables at the casinos of Monte Carlo. It is a class of probabilistic computational algorithms that rely on repeated sampling of random variables of interest to compute the results. Simplistic simulation can be done with spreadsheet software, while more sophisticated modelling can be done with the use of software packages, like Palisade @Risk ®, Minitab ®, Crystal Ball ® and many others. 4.2 Monte Carlo Simulation Basics Monte Carlo simulation can be defined as a method for iteratively evaluating a deterministic model using sets of random numbers as inputs. It is a fairly simple mathematical procedure, with random inputs and random outputs: y = f (x 1, x 2, …, x n), where the input values are sampled and the output values are recorded and analysed as illustrated in Figure 4.1. Figure 4.1 Simplified Monte Carlo simulation procedure with y = f(x 1, x 2, …, x n). In order to run Monte Carlo simulation we need to generate random variables that follow an arbitrary statistical distribution. The inputs are randomly generated from probability distributions to simulate the process of sampling from an actual population, therefore we choose a distribution for each input that best represents our current state of knowledge...
- Bruce B. Frey(Author)
- 2018(Publication Date)
- SAGE Publications, Inc(Publisher)
...Given the broad-reaching utility of this methodology, it is employed in a variety of fields and subject matters, such as physics, engineering, biology, mathematics, finance, as well as behavioral sciences. This entry explores the methods and basic procedures of the Monte Carlo simulation, its application in social and behavioral research, as well as its limitations. Methods and Basic Procedures The most commonly employed application of the Monte Carlo simulation is the examination of sampling distributions, although its application extends to a variety of scenarios for which a complete mathematical analysis is otherwise not feasible or is extremely difficult. Discussion of the enumerable number of applications is beyond the scope of the current entry. Fundamentally, the methodology allows one to examine a very large number of observations that are created from a set of parameters. In part, the utility of the Monte Carlo methodology includes flexibility and the ability to generate a large number of observations based on existing parameters (e.g., summary data for a population of interest). The basic procedure of the Monte Carlo simulation is to first specify the pseudo-population through the development of a computer algorithm to generate data for the desired statistic. This computer algorithm generates artificial data to simulate a population. These data can then be used by the researcher to study and to better understand the behavior of the statistical estimates from the data. A commonly used algorithm is known as “middle-square digits.” For this algorithm, an arbitrary n -unit integer is squared, creating a 2 n -digit product. A new integer is then created by removing the middle n -digits from the product, and then the process is repeated over and over, creating a long chain of integers that will eventually repeat itself. Observations are usually random or pseudorandom and are intended to generalize the population of interest...
eBook - ePub- Andreas Binder, Michael Aichinger(Authors)
- 2013(Publication Date)
- Wiley(Publisher)
...9 Monte Carlo Simulation The objective of this chapter is to convey an understanding of the basic principles of Monte Carlo Methods, with a particular focus on integration 1 problems. Monte Carlo Methods are a class of computational algorithms that rely on stochastic sampling of a (usually high-dimensional) parameter space to achieve an approximation of the desired result. In finance, these methods are used, for instance, in valuating and analyzing instruments, portfolios or investments. The various sources of uncertainty (e.g., the interest rate of a floating rate bond) that affect the result are simulated, a value for each of the simulation paths 2 is computed (e.g., the value of the floating rate bond in each interest rate scenario), and the final value is determined by averaging over the range of outcomes. From a more mathematical viewpoint, each source of uncertainty can be interpreted as a random variable. In probability theory, the expectation (expected value, first moment) of such a random variable is the weighted average of all possible values that this random variable can assume. 3 9.1 THE PRINCIPLES OF MONTE CARLO INTEGRATION The integral of a function f can be expressed by a mean value, (9.1) where a and b are the integration limits and M [ f ] is the mean value of the function over this interval. The basic idea of the Monte Carlo method is to use the sample mean for M [ f ], (9.2) with N sampling points x i drawn from a distribution. With regard to (9.2), the laws of statistics (9.4) ensure that one would achieve exact results (neglecting rounding errors) in the case N → ∞. As an example, consider the integral of a function f over the unit interval, (9.3) We can try to approximate the integral by evaluating f at N uniformly distributed random numbers u i in the interval [0;1], (9.4) Under weak assumptions on f in the unit interval, the law of large numbers mentioned above states that N → I with probability 1 if N → ∞ (Glasserman, 2003)...
- Matthew N.O. Sadiku(Author)
- 2018(Publication Date)
- CRC Press(Publisher)
...The name “Monte Carlo” comes from the city in Monaco, famous for its gambling casinos. MCMs are applied in two ways: simulation and sampling. Simulation refers to methods of providing mathematical imitation of real random phenomena. A typical example is the simulation of a neutron’s motion into a reactor wall, its zigzag path being imitated by a random walk. Sampling refers to methods of deducing properties of a large set of elements by studying only a small, random subset. For example, the average value of f (x) over a < x < b can be estimated from its average over a finite number of points selected randomly in the interval. This amounts to a MCM of numerical integration. MCMs have been applied successfully for solving differential and integral equations, for finding eigenvalues, for inverting matrices, and particularly for evaluating multiple integrals. The simulation of any process or system in which there are inherently random components requires a method of generating or obtaining numbers that are random. Examples of such simulation occur in random collisions of neutrons, in statistics, in queueing models, in games of strategy, and in other competitive enterprises. Monte Carlo calculations require having available sequences of numbers which appear to be drawn at random from particular probability distributions. 8.2 Generation of Random Numbers and Variables Various techniques for generating random numbers are discussed fully in [ 5 – 12 ]. The almost universally used method of generating random numbers is to select a function g (x) that map integers into random numbers. Select x 0 somehow, and generate the next random number as x k + 1 = g (x k). The most common function g (x) takes the form g (x) = (a x + c) mod m (8.1) where x 0 = starting value or a seed (x 0 > 0), a = multiplier (a ≥ 0), c = increment (c ≥ 0), m = the modulus The modulus m is usually 2 t for t -digit binary integers. For a 31-bit computer machine, for example, m may be 2 31–1...
eBook - ePub- Thierry Roncalli(Author)
- 2020(Publication Date)
- Chapman and Hall/CRC(Publisher)
...Chapter 13 Monte Carlo Simulation Methods Monte Carlo Methods consist of solving mathematical problems using random numbers. The term ‘ Monte Carlo ’ was apparently coined by physicists Ulam and von Neumann at Los Alamos in 1940 and refers to gambling casinos in Monaco 1. Until the end of the eighties, Monte Carlo Methods were principally used to calculate numerical integration 2 including mathematical expectations. More recently, the Monte Carlo method designates all numerical methods that involves stochastic simulation and consider random experiments on a computer. This chapter is divided into three sections. In the first section, we present the different approaches to generate random numbers. Section two extends simulation methods when we manipulate stochastic processes. Finally, the last section is dedicated to Monte Carlo and quasi-Monte Carlo Methods. 13.1 Random variate generation Any Monte Carlo method is based on series of random variates that are independent and identically distributed (iid) according to a given probability distribution F. As we will see later, it can be done by generating uniform random numbers. This is why numerical programming softwares already contain uniform random number generators. However, true randomness is impossible to simulate with a computer. In practice, only sequences of ‘ pseudorandom ’ numbers can be produced with statistical properties that are closed from those obtained with iid random variables. 13.1.1 Generating uniform random numbers A first idea is to build a pseudorandom sequence S and repeat this sequence as often as necessary. For instance, for simulating 10 uniform random numbers, we can set S = { 0, 0.5, 1 } and repeat this sequence four times. In this case, the 10 random numbers are: { 0, 0.5, 1, 0, 0.5, 1, 0, 0.5, 1, 0 } We notice that the period length of this sequence is three...
- A. Hasofer, V.R. Beck, I.D. Bennetts(Authors)
- 2006(Publication Date)
- Routledge(Publisher)
...5 The Monte Carlo method 5.1 Introduction There are many situations in probabilistic risk analysis when there is no analytic algorithm that will evaluate the required probabilities. Alternatively, the available algorithm is extremely complex and can only be carried out at great expense of effort and computer time. An alternative method is known as Monte Carlo simulation. It depends on the fact that the histogram of a large random sample approximates the probability function of the underlying random variable. Suppose that the output variable required to carry out the risk analysis, denoted by Y, is given as a function of a vector X of underlying variables: X =(X 1,. . ., X n) in the form In the Monte Carlo method, a random sample of size N of the vector of underlying variables X 1,. . ., X N is generated. Each such vector is called a realization of the vector X. To each realization there corresponds a value of the output variable Y. Thus we obtain a sample of size N from the output variable Y. Provided N is chosen appropriately large, the histogram of Y will approximate its distribution as closely as required. Example As an example, we shall consider a floor of a building consisting of four compartments numbered 1 to 4 and we want to study fire spread from compartment 1 to compartment 4. For the purpose of investigating fire spread from one compartment to an adjacent one, a building can be represented by a network. Each compartment is represented by a vertex, and vertices are connected by an edge if there is between the two corresponding compartments a direct path that the fire can use. To each edge we assign a random variable representing the time taken by the fire to spread from the compartment at the start of the edge to the compartment at the other end...
