Monte Carlo algorithm
Monte Carlo algorithms are randomized algorithms that are allowed to produce a wrong result with a non-trivial upwardly restricted probability. On the other hand, they are often more efficient compared to deterministic algorithms. Their disadvantage is that the calculated result can be wrong. By repeating the algorithm with independent random bits, however, the probability of errors can be reduced ( Probability Amplification , further details in the article Randomized Algorithm ). In contrast to Monte Carlo algorithms, Las Vegas algorithms are only allowed to calculate correct solutions.
According to N. Metropolis, the name Monte-Carlo is related to the method as follows: Stan Ulam had an uncle who always borrowed money from relatives to play games because “he had to go to Monte Carlo”.
One and two sided error
Monte Carlo algorithms are available for
- Search problems
-
Decision problems . A distinction is made between one-sided and two-sided errors:
- In the event of a two-sided error, a Monte Carlo algorithm may return false positives (i.e. the output yes, although no would be correct) and false negatives (i.e. the output no although yes would be correct).
- In the case of a one-sided error, only one of the two possible errors is allowed. A common agreement is to speak of a one-sided error, meaning "false negatives".
These concepts are clarified in the following section, which defines complexity classes for problems with Monte Carlo algorithms.
Complexity classes for decision problems with randomized algorithms
- BPP (from English bounded error probabilistic polynomial time ) is the set of decision problems for which there is a polynomial time-constrained randomized algorithm with the following properties: If the correct output is yes (no), the probability that the algorithm is yes (or No) outputs at least 2/3.
- RP (from English randomized polynomial time ) is the set of decision problems for which there is a polynomial time-constrained randomized algorithm with the following properties: If the correct output is yes, the probability that the algorithm outputs yes is at least 1/2. If the correct output is no, the likelihood that the algorithm will return no is 1.
- co-RP is the set of decision problems for which there is a polynomial time-constrained randomized algorithm with the following properties: If the correct output is yes, then the probability that the algorithm will return yes is 1; if the correct output is no, then the probability that the algorithm will output no is at least 1/2. Thus co-RP contains the complements of the problems in RP.
The specified bounds for the probabilities must apply to all inputs; the probabilities relate only to the random bits used by the algorithm (and not to the input, so the input is not considered to be random). With the help of Probability Amplification we can show that the constant 2/3 from the definition of BPP can be replaced by any other constant from the interval (1 / 2.1) without changing the set BPP; Likewise, in the definitions of RP and co-RP, the constant 1/2 can be replaced by any constant from the interval (0,1).
Although BPP and RP are sets of problems, terms such as BPP algorithms or RP algorithms are often used in common parlance to refer to algorithms with the properties defined above.
To clarify the definition of RP: If an RP algorithm produces the output Yes, we know for sure that the output Yes is correct (since the definition ensures that if the output is correct, No, it is definitely output). If, on the other hand, an RP algorithm returns no, we do not know anything about the correct output (since according to the definition, the output no is possible if yes or no were correct).
Methods
Metropolis algorithm
The published by Nicholas Metropolis Metropolis algorithm for investigating statistical-mechanical systems using computer simulation derived from Monte Carlo integration-of the.
Sequential Monte Carlo Method (SMC)
Sequential Monte Carlo methods are suitable for Bayesian state estimation of dynamic systems. The aim is to estimate the system status as a function of time based on a series of observations of the system and a priori knowledge of the system dynamics. For this purpose, the complicated probability density of the state is discretely approximated by a set of particles. Sequential Monte Carlo methods are also called particle filters.
Quantum Monte Carlo Methods (QMC)
Quantum Monte Carlo methods are used to calculate physical observables in quantum field theoretical models. Examples are models from theoretical solid state physics such as the Hubbard model or the tJ model.
Kinetic Monte Carlo method
The kinetic Monte Carlo method makes it possible to simulate the progress of a system over time.
Cluster algorithms
Cluster algorithms are non-local methods. These include the Swendsen-Wang algorithm and the Wolff algorithm .
Hybrid Monte Carlo Algorithm
The hybrid Monte Carlo algorithm is a Monte Carlo algorithm for generating systems in the canonical state. The process creates a combination of molecular dynamics and random motion.
See also
literature
- R. Motwani, P. Raghavan: Randomized Algorithms . Cambridge University Press, Cambridge 1995, ISBN 0-521-47465-5 .
- Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo algorithms. Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6 .