FACTOID # 1: Idaho produces more milk than Iowa, Indiana and Illinois combined.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Monte Carlo method
The Monte Carlo method can be illustrated as a game of battleship. First a player makes some random shots. Next the player applies algorithms (ie. a battleship is four dots in the vertical or horizontal direction). Finally based on the outcome of the random sampling and the algorithm the player can determine the likely locations of the other player's ships.
The Monte Carlo method can be illustrated as a game of battleship. First a player makes some random shots. Next the player applies algorithms (ie. a battleship is four dots in the vertical or horizontal direction). Finally based on the outcome of the random sampling and the algorithm the player can determine the likely locations of the other player's ships.

Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used when simulating physical and mathematical systems. Because of their reliance on repeated computation and random or pseudo-random numbers, Monte Carlo methods are most suited to calculation by a computer. Monte Carlo methods tend to be used when it is infeasible or impossible to compute an exact result with a deterministic algorithm.[1] Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... pencil and paper game version The game Battleship is a guessing game played by two people. ... Look up computation in Wiktionary, the free dictionary. ... Flowcharts are often used to graphically represent algorithms. ... Random redirects here. ... It has been suggested that simulation software be merged into this article or section. ... A magnet levitating above a high-temperature superconductor demonstrates the Meissner effect. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... Random number may refer to: A number generated for or part of a set exhibiting statistical randomness. ... A pseudorandom process is a process that appears random but is not. ... This article is about the machine. ... In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. ...


The term Monte Carlo was coined in the 1940s by physicists working on nuclear weapon projects in the Los Alamos National Laboratory.[2] Los Alamos National Laboratory, aerial view from 1995. ...

Contents

Overview

There is no single Monte Carlo method; instead, the term describes a large and widely-used class of approaches. However, these approaches tend to follow a particular pattern:

  1. Define a domain of possible inputs.
  2. Generate inputs randomly from the domain, and perform a deterministic computation on them.
  3. Aggregate the results of the individual computations into the final result.

For example, the value of π can be approximated using a Monte Carlo method. Draw a square of area 1 on the ground, then inscribe a circle within it. Now, scatter some small objects (for example, grains of rice or sand) throughout the square. If the objects are scattered uniformly, then the proportion of objects within the circle should be approximately π/4, which is the ratio of the circle's area to the square's area. Thus, if we count the number of objects in the circle, multiply by four, and divide by the number of objects in the square, we get an approximation to π. When a circles diameter is 1, its circumference is Ï€. Pi or Ï€ is the ratio of a circles circumference to its diameter in Euclidean geometry, approximately 3. ... In probability theory and statistics, the continuous uniform distribution is a family of probability distributions such that for each member of the family, all intervals of the same length on the distributions support are equally probable. ...


Notice how the π approximation follows the general pattern of Monte Carlo algorithms. First, we define a domain of inputs: in this case, it's the square which circumscribes our circle. Next, we generate inputs randomly (scatter individual grains within the square), then perform a computation on each input (test whether it falls within the circle). At the end, we aggregate the results into our final result, the approximation of π. Note, also, two other common properties of Monte Carlo methods: the computation's reliance on good random numbers, and its slow convergence to a better approximation as more data points are sampled. If we just drop our grains in the center of the circle, they might simply build up in a pile within the circle: they won't be uniformly distributed, and so our approximation will be way off. But if they are uniformly distributed, then the more grains we drop, the more accurate our approximation of π will become.


History

The name "Monte Carlo" was popularized by physics researchers Stanislaw Ulam, Enrico Fermi, John von Neumann, and Nicholas Metropolis, among others; the name is a reference to a famous casino in Monaco where Ulam's uncle would borrow money to gamble.[3] The use of randomness and the repetitive nature of the process are analogous to the activities conducted at a casino. Stanisław Ulam in the 1950s. ... Fermi redirects here. ... For other persons named John Neumann, see John Neumann (disambiguation). ... Nicholas Constantine Metropolis (June 11, 1915 – October 17, 1999) was a Greek-American mathematician, physicist, and computer scientist. ... This article or section does not adequately cite its references or sources. ... Random redirects here. ...


Random methods of computation and experimentation (generally considered forms of stochastic simulation) can be arguably traced back to the earliest pioneers of probability theory (see, e.g., Buffon's needle, and the work on small samples by William Gosset), but are more specifically traced to the pre-electronic computing era. The general difference usually described about a Monte Carlo form of simulation is that it systematically "inverts" the typical mode of simulation, treating deterministic problems by first finding a probabilistic analog. Previous methods of simulation and statistical sampling generally did the opposite: using simulation to test a previously understood deterministic problem. Though examples of an "inverted" approach do exist historically, they were not considered a general method until the popularity of the Monte Carlo method spread. Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems. ... In mathematics, Buffons needle problem is a question first posed in the 18th century by Georges-Louis Leclerc, Comte de Buffon: suppose we have a floor made of parallel strips of wood, each the same width, and we drop a needle onto the floor. ... William Sealy Gosset (June 13, 1876 – October 16, 1937) was a chemist and statistician, better known by his pen name Student. ...


Perhaps the most famous early use was by Enrico Fermi in 1930, when he used a random method to calculate the properties of the newly-discovered neutron. Monte Carlo methods were central to the simulations required for the Manhattan Project, though were severely limited by the computational tools at the time. Therefore, it was only after electronic computers were first built (from 1945 on) that Monte Carlo methods began to be studied in depth. In the 1950s they were used at Los Alamos for early work relating to the development of the hydrogen bomb, and became popularized in the fields of physics, physical chemistry, and operations research. The Rand Corporation and the U.S. Air Force were two of the major organizations responsible for funding and disseminating information on Monte Carlo methods during this time, and they began to find a wide application in many different fields. This article or section does not adequately cite its references or sources. ... This article is about the general term. ... This article is about the World War II nuclear project. ... Los Alamos National Laboratory, aerial view from 1995. ... The mushroom cloud of the atomic bombing of Nagasaki, Japan, in 1945 lifted nuclear fallout some 18 km (60,000 feet) above the epicenter. ... A magnet levitating above a high-temperature superconductor demonstrates the Meissner effect. ... Physical chemistry, is the application of physics to macroscopic, microscopic, atomic, subatomic, and particulate phenomena in chemical systems[1] within the field of chemistry traditionally using the principles, practices and concepts of thermodynamics, quantum chemistry, statistical mechanics and kinetics. ... Operations Research or Operational Research (OR) is an interdisciplinary branch of mathematics which uses methods like mathematical modeling, statistics, and algorithms to arrive at optimal or good decisions in complex problems which are concerned with optimizing the maxima (profit, faster assembly line, greater crop yield, higher bandwidth, etc) or minima... Alternate meanings: See RAND (disambiguation) The RAND Corporation is an American think tank first formed to offer research and analysis to the U.S. military. ... Seal of the Air Force. ...


Uses of Monte Carlo methods require large amounts of random numbers, and it was their use that spurred the development of pseudorandom number generators, which were far quicker to use than the tables of random numbers which had been previously used for statistical sampling. A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. ...


Applications

Monte Carlo simulation methods are especially useful in studying systems with a large number of coupled degrees of freedom, such as liquids, disordered materials, strongly coupled solids, and cellular structures (see cellular Potts model). More broadly, Monte Carlo methods are useful for modeling phenomena with significant uncertainty in inputs, such as the calculation of risk in business (for its use in the insurance industry, see stochastic modelling). A classic use is for the evaluation of definite integrals, particularly multidimensional integrals with complicated boundary conditions. In physics, two systems are coupled if they are interacting with each other. ... The cellular Potts model (CPM) is a lattice-based computational modeling method to simulate the collective behavior of cellular structures. ... “Uncertain” redirects here. ... For the Parker Brothers board game, see Risk (game) For other uses, see Risk (disambiguation). ... This page is concerned with the stochastic modelling as applied to the insurance industry. ... This article deals with the concept of an integral in calculus. ...


Monte Carlo methods in finance are often used to calculate the value of companies, to evaluate investments in projects at corporate level or to evaluate financial derivatives. The Monte Carlo method is intended for financial analysts who want to construct stochastic or probabilistic financial models as opposed to the traditional static and deterministic models. In the field of financial mathematics, many problems, for instance the problem of finding the arbitrage-free value of a particular derivative, boil down to the computation of a particular integral. ...


Monte Carlo methods are very important in computational physics, physical chemistry, and related applied fields, and have diverse applications from complicated quantum chromodynamics calculations to designing heat shields and aerodynamic forms. Computational physics is the study and implementation of numerical algorithms in order to solve problems in physics for which a quantitative theory already exists. ... Physical chemistry, is the application of physics to macroscopic, microscopic, atomic, subatomic, and particulate phenomena in chemical systems[1] within the field of chemistry traditionally using the principles, practices and concepts of thermodynamics, quantum chemistry, statistical mechanics and kinetics. ... Quantum chromodynamics (abbreviated as QCD) is the theory of the strong interaction (color force), a fundamental force describing the interactions of the quarks and gluons found in hadrons (such as the proton, neutron or pion). ... In aeronautics, a heat shield is a protective layer on a spacecraft or ballistic missile that is designed to protect it from high temperatures, usually those that result from aerobraking during entry into a planets atmosphere. ... For the Daft Punk song, see Aerodynamic (song). ...


Monte Carlo methods have also proven efficient in solving coupled integral differential equations of radiation fields and energy transport, and thus these methods have been used in global illumination computations which produce photorealistic images of virtual 3D models, with applications in video games, architecture, design, computer generated films, special effects in cinema, business, economics and other fields. Global illumination algorithms used in 3D computer graphics are commonly used to add realistic lighting to 3D scenes. ... This article is about computer and video games. ... This article is about building architecture. ... All Saints Chapel in the Cathedral Basilica of St. ... This article is about motion pictures. ...


Monte Carlo methods are useful in many areas of computational mathematics, where a lucky choice can find the correct result. A classic example is Rabin's algorithm for primality testing: for any n which is not prime, a random x has at least a 75% chance of proving that n is not prime. Hence, if n is not prime, but x says that it might be, we have observed at most a 1-in-4 event. If 10 different random x say that "n is probably prime" when it is not, we have observed a one-in-a-million event. In general a Monte Carlo algorithm of this kind produces one correct answer with a guarantee n is composite, and x proves it so, but another one without, but with a guarantee of not getting this answer when it is wrong too often — in this case at most 25% of the time. See also Las Vegas algorithm for a related, but different, idea. The Miller-Rabin primality test or Rabin-Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay-Strassen primality test. ... In computing, a Las Vegas algorithm is a randomized algorithm that is correct; that is, it always produces the correct result. ...


Application areas

Areas of application include:

  • Graphics, particularly for ray tracing; a version of the Metropolis-Hastings algorithm is also used for ray tracing where it is known as Metropolis light transport
  • Modeling light transport in biological tissue
  • Monte Carlo methods in finance
  • Reliability engineering
  • In simulated annealing for protein structure prediction
  • In semiconductor device research, to model the transport of current carriers
  • Environmental science, dealing with contaminant behavior
  • Monte Carlo method in statistical physics; in particular, Monte Carlo molecular modeling as an alternative for computational molecular dynamics.
  • Search And Rescue and Counter-Pollution. Models used to predict the drift of a life raft or movement of an oil slick at sea.
  • In Probabilistic design for simulating and understanding the effects of variability
  • In Physical chemistry, particularly for simulations involving atomic clusters
  • In computer science
  • Modeling the movement of impurity atoms (or ions) in plasmas in existing and tokamaks (e.g.: DIVIMP).
  • In experimental particle physics, for designing detectors, understanding their behavior and comparing experimental data to theory
  • Nuclear and particle physics codes using the Monte Carlo method:
    • GEANT - CERN's simulation of high energy particles interacting with a detector.
    • CompHEP, PYTHIA - Monte-Carlo generators of particle collisions
    • MCNP(X) - LANL's radiation transport codes
    • EGS - Stanford's simulation code for coupled transport of electrons and photons
    • PEREGRINE - LLNL's Monte Carlo tool for radiation therapy dose calculations
    • BEAMnrc - Monte Carlo code system for modeling radiotherapy sources (LINAC's)
    • PENELOPE - Monte Carlo for coupled transport of photons and electrons, with applications in radiotherapy
    • MONK - Serco Assurance's code for the calculation of k-effective of nuclear systems
    • Modelling of foam and cellular structures
    • Modeling of tissue morphogenesis

A ray traced scene. ... The Proposal distribution Q proposes the next point that the random walk might move to. ... This SIGGRAPH 1997 paper by Eric Veach and Leonidas J. Guibas describes an application of a variant of the Monte Carlo method called the Metropolis-Hastings algorithm to the rendering equation for generating images from detailed physical descriptions of three dimensional scenes. ... In the field of financial mathematics, many problems, for instance the problem of finding the arbitrage-free value of a particular derivative, boil down to the computation of a particular integral. ... Reliability engineering is an engineering field, that deals with the study of reliability: the ability of a system or component to perform its required functions under stated conditions for a specified period of time. ... Monte Carlo in statistical physics refers to the application of the Monte Carlo method to problems in statistical physics, or statistical mechanics. ... Statistical physics, one of the fundamental theories of physics, uses methods of statistics in solving physical problems. ... Monte Carlo molecular modeling, particularly Metropolis Monte Carlo simulation is the application of Monte Carlo methods to problems which would otherwise be solved by molecular dynamics. ... Molecular dynamics (MD) is a form of computer simulation wherein atoms and molecules are allowed to interact for a period of time under known laws of physics, giving a view of the motion of the atoms. ... // Probabilistic design is a discipline within Engineering Design. ... Physical chemistry, is the application of physics to macroscopic, microscopic, atomic, subatomic, and particulate phenomena in chemical systems[1] within the field of chemistry traditionally using the principles, practices and concepts of thermodynamics, quantum chemistry, statistical mechanics and kinetics. ... In computing, a Las Vegas algorithm is a randomized algorithm that is correct; that is, it always produces the correct result. ... Lurch is the fictional manservant to The Addams Family created by cartoonist Charles Addams. ... Computer go is the field of artificial intelligence (AI) dedicated to creating a computer program that plays go, an ancient board game. ... General Game Playing refers to the design of artificial Intelligence programs to be able to play more than one game successfully. ... Thousands of particles explode from the collision point of two relativistic (100 GeV per nucleon) gold ions in the STAR detector of the Relativistic Heavy Ion Collider. ... The Compact Muon Solenoid (CMS) is an example of a large particle detector. ... GEANT is a simulation program designed to describe the passage of elementary particles through matter. ... CERN is the European Organization for Nuclear Research, the worlds largest particle physics laboratory, situated on the border between France and Switzerland, just west of Geneva. ... CompHEP is a software package for automatic computations in High Energy Physics from Lagrangians to collision events or particle decays. ... For other uses, see Pythia (disambiguation). ... Monte Carlo N-Particle Transport Code (MCNP) is a software package for simulating nuclear processes. ... The EGS (Electron Gamma Shower) computer code system is a general purpose package for the Monte Carlo simulation of the coupled transport of electrons and photons in an arbitrary geometry for particles with energies from a few keV up to several TeV. It is developed at SLAC. See also GEANT... The Stanford Linear Accelerator Center (SLAC) is a U.S. national laboratory operated by Stanford University for the U.S. Department of Energy. ... BEAMnrc is a Monte Carlo (see Monte Carlo Method) code system for simulating radiation therapy sources. ... Linear accelerator (LINAC) used for medical radiation therapy; example made by Siemens AG. A linear particle accelerator (also called a LINAC) is an electrical device for the acceleration of subatomic particles. ... For other uses, see Monk (disambiguation). ... // A schematic nuclear fission chain reaction. ... Sea foam on the beach Foam on a cappuccino Fire-retardant, foamed plastic being used as a temporary dam for firestop mortar in a cable penetration in a pulp and paper mill on Vancouver Island, British Columbia, Canada. ... Biological tissue is a collection of interconnected cells that perform a similar function within an organism. ... Morphogenesis (from the Greek morphê shape and genesis creation) is one of three fundamental aspects of developmental biology along with the control of cell growth and cellular differentiation. ...

Other methods employing Monte Carlo

Self-organization refers to a process in which the internal organization of a system, normally an open system, increases automatically without being guided or managed by an outside source. ... Direct simulation Monte Carlo (DSMC) is a computational Monte Carlo algorithm for the stochastic simulation of rarefied gas flows. ... In chemistry, Dynamic Monte Carlo (DMC) is a method for modeling the dynamic behaviors of molecules by comparing the rates of individual steps with random numbers. ... The kinetic Monte Carlo (KMC) method is a Monte Carlo method computer simulation intended to simulate the time evolution of some processes occurring in nature. ... This article or section is in need of attention from an expert on the subject. ... In numerical analysis, a quasi-Monte Carlo method is a method for the computation of an integral (or some other problem) which is based on low-discrepancy sequences. ... In mathematics, a low-discrepancy sequence is a sequence with the property that for all N, the subsequence x1, ..., xN is almost uniformly distributed (in a sense to be made precise), and x1, ..., xN+1 is almost uniformly distributed as well. ... The electron microscope is a microscope that can magnify very small details with high resolving power due to the use of electrons rather than light to scatter off material, magnifying at levels up to 500,000 times. ... Stochastic optimization (SO) methods are optimization algorithms which incorporate probabilistic (random) elements, either in the problem data (the objective function, the constraints, etc. ... The cellular Potts model (CPM) is a lattice-based computational modeling method to simulate the collective behavior of cellular structures. ... Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods) are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its stationary distribution. ... The cross-entropy (CE) method attributed to Reuven Rubinstein is a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling. ... The creator of or main contributor to this page may have a conflict of interest with the subject of this article. ... In robotics and sensors, Monte Carlo localization, or MCL, is a Monte Carlo method to determine the position of a robot given a map of its environment based on Markov localization. ...

Use in mathematics

In general, Monte Carlo methods are used in mathematics to solve various problems by generating suitable random numbers and observing that fraction of the numbers obeying some property or properties. The method is useful for obtaining numerical solutions to problems which are too complicated to solve analytically. The most common application of the Monte Carlo method is Monte Carlo integration.


Integration

Deterministic methods of numerical integration operate by taking a number of evenly spaced samples from a function. In general, this works very well for functions of one variable. However, for functions of vectors, deterministic quadrature methods can be very inefficient. To numerically integrate a function of a two-dimensional vector, equally spaced grid points over a two-dimensional surface are required. For instance a 10x10 grid requires 100 points. If the vector has 100 dimensions, the same spacing on the grid would require 10100 points—far too many to be computed. 100 dimensions is by no means unreasonable, since in many physical problems, a "dimension" is equivalent to a degree of freedom. (See Curse of dimensionality.) This article describes multidimensional Monte Carlo integration. ... Numerical Integration with the Monte Carlo method: Nodes are random equally distributed. ... In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ... For the Internet company, see Google. ... 2-dimensional renderings (ie. ... Degrees of freedom is a general term used in explaining dependence on parameters, and implying the possibility of counting the number of those parameters. ... Curse of dimensionality is a term coined by Richard Bellman applied to the problem caused by the rapid increase in volume associated with adding extra dimensions to a (mathematical) space. ...


Monte Carlo methods provide a way out of this exponential time-increase. As long as the function in question is reasonably well-behaved, it can be estimated by randomly selecting points in 100-dimensional space, and taking some kind of average of the function values at these points. By the law of large numbers, this method will display 1/sqrt{N} convergence—i.e. quadrupling the number of sampled points will halve the error, regardless of the number of dimensions. Mathematicians (and those in related sciences) very frequently speak of whether a mathematical object -- a number, a function, a set, a space of one sort or another -- is well-behaved or not. ... // The law of large numbers (LLN) is any of several theorems in probability. ...


A refinement of this method is to somehow make the points random, but more likely to come from regions of high contribution to the integral than from regions of low contribution. In other words, the points should be drawn from a distribution similar in form to the integrand. Understandably, doing this precisely is just as difficult as solving the integral in the first place, but there are approximate methods available: from simply making up an integrable function thought to be similar, to one of the adaptive routines discussed in the topics listed below.


A similar approach involves using low-discrepancy sequences instead—the quasi-Monte Carlo method. Quasi-Monte Carlo methods can often be more efficient at numerical integration because the sequence "fills" the area better in a sense and samples more of the most important points that can make the simulation converge to the desired solution more quickly. In mathematics, a low-discrepancy sequence is a sequence with the property that for all N, the subsequence x1, ..., xN is almost uniformly distributed (in a sense to be made precise), and x1, ..., xN+1 is almost uniformly distributed as well. ... In numerical analysis, a quasi-Monte Carlo method is a method for the computation of an integral (or some other problem) which is based on low-discrepancy sequences. ...


Integration methods

Importance sampling is a general technique for estimating the properties of a particular distribution, while only having samples generated from a different distribution than the distribution of interest. ... In statistics, stratified sampling is a method of sampling from a population. ... The VEGAS algorithm is a method for reducing error in the Monte Carlo simulation by using a known or approximate probability distribution function to concentrate the search in those areas of the graph that make the greatest contribution to the final integral. ... Random walk Monte Carlo methods (sometimes called Markov chain Monte Carlo methods, or MCMC methods) are a class of algorithms to numerically calculate multi-dimensional integrals. ... In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property. ... The Proposal distribution Q proposes the next point that the random walk might move to. ... In mathematics and physics, Gibbs sampling is an algorithm to generate a sequence of samples from the joint probability distribution of two or more random variables. ...

Optimization

Another powerful and very popular application for random numbers in numerical simulation is in numerical optimization. These problems use functions of some often large-dimensional vector that are to be minimized (or maximized). Many problems can be phrased in this way: for example a computer chess program could be seen as trying to find the optimal set of, say, 10 moves which produces the best evaluation function at the end. The traveling salesman problem is another optimization problem. There are also applications to engineering design, such as multidisciplinary design optimization. In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ... 1990s Pressure-sensory Chess Computer with LCD screen The idea of creating a chess-playing machine dates back to the eighteenth century. ... The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ... Multidisciplinary design optimization (MDO) is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. ...


Most Monte Carlo optimization methods are based on random walks. Essentially, the program will move around a marker in multi-dimensional space, tending to move in directions which lead to a lower function, but sometimes moving against the gradient. Example of eight random walks in one dimension starting at 0. ... For other uses, see Gradient (disambiguation). ...


Optimization methods

In computer science, evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. ... A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. ... Parallel tempering is a simulation method aimed at improving the dynamic properties of Monte Carlo method simulations. ... For other uses, see Annealing. ... Stochastic optimization (SO) methods are optimization algorithms which incorporate probabilistic (random) elements, either in the problem data (the objective function, the constraints, etc. ... Stochastic tunneling (STUN) is one approach to global optimization among several others and is based on the Monte Carlo method-sampling of the function to be minimized. ...

Inverse problems

Probabilistic formulation of inverse problems leads to the definition of a probability distribution in the model space. This probability distribution combines a priori information with new information obtained by measuring some observable parameters (data). As, in the general case, the theory linking data with model parameters is nonlinear, the a posteriori probability in the model space may not be easy to describe (it may be multimodal, some moments may not be defined, etc.). An inverse problem is the task that often occurs in many branches of science and mathematics where the values of some model parameter(s) must be obtained from the observed data. ... A probability distribution describes the values and probabilities that a random event can take place. ...


When analyzing an inverse problem, obtaining a maximum likelihood model is usually not sufficient, as we normally also wish to have information on the resolution power of the data. In the general case we may have a large number of model parameters, and an inspection of the marginal probability densities of interest may be impractical, or even useless. But it is possible to pseudorandomly generate a large collection of models according to the posterior probability distribution and to analyze and display the models in such a way that information on the relative likelihoods of model properties is conveyed to the spectator. This can be accomplished by means of an efficient Monte Carlo method, even in cases where no explicit formula for the a priori distribution is available.


The best-known importance sampling method, the Metropolis algorithm, can be generalized, and this gives a method that allows analysis of (possibly highly nonlinear) inverse problems with complex a priori information and data with an arbitrary noise distribution. For details, see Mosegaard and Tarantola (1995) [1] , or Tarantola (2005) [2] .


Monte Carlo and random numbers

Interestingly, Monte Carlo simulation methods do not generally require truly random numbers to be useful - for other applications, such as primality testing, unpredictability is vital (see Davenport (1995)).[4] Many of the most useful techniques use deterministic, pseudo-random sequences, making it easy to test and re-run simulations. The only quality usually necessary to make good simulations is for the pseudo-random sequence to appear "random enough" in a certain sense. Random number may refer to: A number generated for or part of a set exhibiting statistical randomness. ... A primality test is an algorithm for determining whether an input number is prime. ... A pseudo-random number is a number belonging to a sequence which appears to be random, but can in fact be generated by a finite computation. ... This article is about the general term. ...


What this means depends on the application, but typically they should pass a series of statistical tests. Testing that the numbers are uniformly distributed or follow another desired distribution when a large enough number of elements of the sequence are considered is one of the simplest, and most common ones. In mathematics, the uniform distributions are simple probability distributions. ...


An alternative to the basic Monte Carlo method

Applied information economics (AIE) is a decision analysis method used in business and government that addresses some of the shortcomings of the Monte Carlo method - at least how it is usually employed in practical situations. The most important components AIE adds to the Monte Carlo method are: The creator of or main contributor to this page may have a conflict of interest with the subject of this article. ...

1) Accounting for the systemic overconfidence of human estimators with calibrated probability assessment
2) Computing the economic value of information to guide additional empirical measurements
3) Using the results of Monte Carlos as input to portfolio analysis

When Monte Carlo simulations are used in most decision analysis settings, human experts are used to estimate the probabilities and ranges in the model. However, decision psychology research in the field of calibrated probability assessments shows that humans - especially experts in various fields - tend to be statistically overconfident. That is, they put too high a probability that a forecasted outcome will occur and they tend to use ranges that are too narrow to reflect their uncertainty. AIE involves training human estimators so that the probabilities and ranges they provide realistically reflect uncertainty (eg., a subjective 90% confidence interval as a 90% chance of containing the true value). Without such training, Monte Carlo models will invariably underestimate the uncertainty of a decision and therefore the risk. Calibrated Probability Assessments are subjective probabilities assigned by individuals who have been trained to assess probabilities in a way that historically represents their uncertainty[1][2]. In other words, when a calibrated person says they are 80% confident in each of 100 predictions they made, they will get about 80...


Another shortcoming is that, in practice, most users of Monte Carlo simulations rely entirely on the initial subjective estimates and almost never follow up with empirical observation. This may be due to the overwhelming number of variables in many models and the inability of analysts to choose economically justified variables to measure further. AIE addresses this by using methods from decision theory to compute the economic value of additional information. This usually eliminates the need to measure most variables and puts pragmatic constraints on the methods used to measure those variables that have a significant information value.


The final shortcoming addressed by AIE is that the output of a Monte Carlo - at least for the analysis of business decisions - is simply the histogram of the resulting returns. No criteria is presented to determine if a particular distribution of results is acceptable or not. AIE uses Modern Portfolio Theory to determine which investments are desirable and what their relative priorities should be. Capital Market Line Modern portfolio theory (MPT) proposes how rational investors will use diversification to optimize their portfolios, and how a risky asset should be priced. ...


See also

It has been suggested that this article or section be merged with Bootstrap (statistics). ... In computing, a Las Vegas algorithm is a randomized algorithm that is correct; that is, it always produces the correct result. ... In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property. ... Molecular dynamics (MD) is a form of computer simulation wherein atoms and molecules are allowed to interact for a period of time under known laws of physics, giving a view of the motion of the atoms. ... In numerical analysis, a quasi-Monte Carlo method is a method for the computation of an integral (or some other problem) which is based on low-discrepancy sequences. ... A random number generator is a computational or physical device designed to generate a sequence of elements (usually numbers), such that the sequence can be used as a random one. ... Random redirects here. ... In statistics, resampling is any of a variety of methods for doing one of the following: Estimating the precision of sample statistics (medians, variances, percentiles) by using subsets of available data (jackknife) or drawing randomly with replacement from a set of data points (bootstrapping) Exchanging labels on data points when...

Notes

  1. ^ Douglas Hubbard "How to Measure Anything: Finding the Value of Intangibles in Business" pg. 46, John Wiley & Sons, 2007
  2. ^ [The beginning of the Monte Carlo method http://library.lanl.gov/la-pubs/00326866.pdf]
  3. ^ Douglas Hubbard "How to Measure Anything: Finding the Value of Intangibles in Business" pg. 46, John Wiley & Sons, 2007
  4. ^ Davenport, J. H.. Primality testing revisited. DOI:http://doi.acm.org/10.1145/143242.143290. Retrieved on 2007-08-19.

A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... is the 231st day of the year (232nd in leap years) in the Gregorian calendar. ...

References

  • Bernd A. Berg, Markov Chain Monte Carlo Simulations and Their Statistical Analysis (With Web-Based Fortran Code), World Scientific 2004, ISBN 981-238-935-0.
  • Arnaud Doucet, Nando de Freitas and Neil Gordon, Sequential Monte Carlo methods in practice, 2001, ISBN 0-387-95146-6.
  • P. Kevin MacKeown, Stochastic Simulation in Physics, 1997, ISBN 981-3083-26-3
  • Harvey Gould & Jan Tobochnik, An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems, 1988, ISBN 0-201-16504-X
  • C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004, ISBN 0-387-21239-6
  • R.Y. Rubinstein and D.P. Kroese (2007). "Simulation and the Monte Carlo Method" (second edition). New York: John Wiley & Sons, ISBN 978-0-470-17793-8.
  • Mosegaard, Klaus., and Tarantola, Albert, 1995. Monte Carlo sampling of solutions to inverse problems. J. Geophys. Res., 100, B7, 12431-12447.
  • Tarantola, Albert, Inverse Problem Theory (free PDF version), Society for Industrial and Applied Mathematics, 2005. ISBN 0-89871-572-5
  • Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller and Edward Teller, "Equation of State Calculations by Fast Computing Machines", Journal of Chemical Physics, volume 21, p. 1087 (1953) (doi:10.1063/1.1699114)
  • N. Metropolis and S. Ulam, "The Monte Carlo Method", Journal of the American Statistical Association, volume 44, number 247, pp. 335–341 (1949) (doi:10.2307/2280232)
  • Fishman, G.S., (1995) Monte Carlo: Concepts, Algorithms, and Applications, Springer Verlag, New York.
  • Judgement under Uncertainty: Heuristics and Biases, ed. D. Kahneman and A. Tversky,(Cambridge University Press, 1982)
  • R. E. Caflisch, Monte Carlo and quasi-Monte Carlo methods, Acta Numerica vol. 7, Cambridge University Press, 1998, pp. 1-49. [3]

Year 2004 (MMIV) was a leap year starting on Thursday of the Gregorian calendar. ... This article is about the year. ... For the band, see 1997 (band). ... Year 1988 (MCMLXXXVIII) was a leap year starting on Friday (link displays 1988 Gregorian calendar). ... Year 2004 (MMIV) was a leap year starting on Thursday of the Gregorian calendar. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ...

External links

The University of Nebraska–Lincoln is a state-supported institution of higher learning located in Lincoln, Nebraska, USA. Often referred to as simply Nebraska or UNL, it is the flagship and largest campus of the University of Nebraska system. ... Microsoft Excel (full name Microsoft Office Excel) is a spreadsheet application written and distributed by Microsoft for Microsoft Windows and Mac OS. It features calculation and graphing tools which, along with aggressive marketing, have made Excel one of the most popular microcomputer applications to date. ... The Cooper Union for the Advancement of Science and Art is a privately funded college in Lower Manhattan of New York City. ...

Software

Min - Optimization, MD - Molecular Dynamics, MC - Monte Carlo, QM - Quantum mechanics. ... “Rutgers” redirects here. ...

  Results from FactBites:
 
Monte Carlo method (596 words)
Monte Carlo methods are methods for solving various kinds of computational problems by using random numbers (or more often pseudo-random numbers), as opposed to deterministic algorithms.
Monte Carlo methods are extremely important in computational physics and related applied fields, and have diverse applications from esoteric quantum chromodynamics calculations, to use by engineers in designing heat shields and aerodynamic forms.
The "Monte Carlo" designation is a reference to the famous casino in that area, and was popularized by early pioneers in the field such as Stanislaw Marcin Ulam, Enrico Fermi, Jon von Neumann and Nick Metropolis[?].
Monte Carlo Method (636 words)
Monte Carlo methods—named after the famous European gambling casino—are a means of numerically simulating chance events in order to predict the most likely future outcome.
Monte Carlo simulations are distinguished from other types of simulation techniques by their extensive use of random numbers and repeated trials.
Advanced Monte Carlo methods involve the use of Markov chains and the Gibbs sampler, statistical tools that consider the probability of moving through a multistage process given multiple variables and uncertainties.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m