Importance sampling

Importance Sampling (in German sometimes also called sampling according to importance , or sampling according to importance ) is a term from the field of stochastic processes that describes the technique of generating samples based on a probability distribution . Importance Sampling is one of several ways to reduce variance , i.e. to increase the efficiency of Monte Carlo simulations .

Basics

Monte Carlo simulations are often used to calculate expected values ​​of a quantity (here referred to as, otherwise - especially in mathematics - often as shown), ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \left\langle {\mathcal {A}}\right\rangle }$ ${\displaystyle \operatorname {E} ({\mathcal {A}})}$

${\displaystyle \left\langle {\mathcal {A}}\right\rangle =\sum _{x\in \Omega }P(x)\,{\mathcal {A}}(x),}$

to calculate, where a normalized statistical weight such as a Boltzmann weight is. is the value of the size in the state . The summation (or integration) runs over a space , e.g. B. the phase space of the particles in the system. Since this phase space is generally very high-dimensional, the sum or the integral cannot generally be calculated. Instead of calculating the true expected value, one calculates an estimator using a random sample S, which has the scope . ${\displaystyle P(x)}$ ${\displaystyle {\mathcal {A}}(x)}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle x}$ ${\displaystyle \Omega }$ ${\displaystyle {\overline {\mathcal {A}}}}$ ${\displaystyle N}$

For the simplest case (simple sampling, English simple sampling ) uniformly at random selected states is obtained for the mean value:

${\displaystyle {\overline {\mathcal {A}}}={\frac {\sum _{x\in S}P(x)\,{\mathcal {A}}(x)}{\sum _{x\in S}P(x)}},}$

where (for example proportional to ) and after the random choice of x are calculated. For a large sample, the estimator approaches the mean: ${\displaystyle P(x)}$ ${\displaystyle \exp(-\beta E(x))}$ ${\displaystyle {\mathcal {A}}(x)}$

${\displaystyle \lim _{N\to \infty }{\overline {\mathcal {A}}}=\left\langle {\mathcal {A}}\right\rangle }$

This method is usually not very efficient because often only a few relevant states are included in the mean value formation. To work around this problem and so the standard deviation to reduce the measured average value for the same sample size, it states tried with a larger weight common in the averaging respond to let as states with less weight: The above estimates of the Simple Sampling can by expanding with even can be expressed as follows: ${\displaystyle 1=W(x)/W(x)}$

${\displaystyle {\overline {\mathcal {A}}}={\frac {\sum _{x\in S}P(x)/W(x)\,{\mathcal {A}}(x)W(x)}{\sum _{x\in S}P(x)/W(x)W(x)}}.}$

If states are generated with the probability (sampling according to importance English importance sampling ), the mean value is then simply calculated using ${\displaystyle x}$ ${\displaystyle W(x)}$

${\displaystyle {\overline {\mathcal {A}}}={\frac {\sum _{x\in S}P(x)/W(x){\mathcal {A}}(x)}{\sum _{x\in S}P(x)\,/\,W(x)}}.}$

example

Are the system states z. B. to be generated arbitrarily with a probability proportional (that is precisely the choice of metropolis), this results ${\displaystyle W(x)}$ ${\displaystyle P(x)}$

${\displaystyle {\overline {\mathcal {A}}}={\frac {1}{N}}\sum _{x\in S}{\mathcal {A}}(x).}$

The fact that only proportionality is required here is an advantage of the method. ${\displaystyle W(x)\propto P(x)}$

In order to achieve a sampling based on importance in practice, a start configuration is assumed and a Markov chain of system states is generated using the Metropolis algorithm .

In addition to the metropolis choice for the sampling probability, there are other options. For example, with the choice , where that density of states is the energy that is assigned to the state , the multicanonical ensemble can be simulated. ${\displaystyle W(x)}$ ${\displaystyle W(x)=1/D(E(x))}$ ${\displaystyle D(E(x))}$ ${\displaystyle x}$

literature

• WK Hastings: Monte Carlo Sampling Methods Using Markov Chains and Their Applications . In: Biometrika . tape 57 , 1970, pp. 97-109 .
• R. Srinivasan: Importance sampling - Applications in communications and detection . Springer-Verlag, Berlin 2002, ISBN 978-3-540-43420-7 .
• Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo algorithms. Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6 , section 5.4, pp. 155-165.

Individual evidence

1. ↑ International Statistical Institute : Glossary of statistical terms.