モンテカルロ法

乱数を使って数値的な答えを得る手法の総称。

$$\int f(x)p(x)dx=𝔼[f(X)]\approx \frac{1}{N}\sum _{i=1}^{N}f(x_i)$$

誤差が次元に依存しない#

中心極限定理により

$$\text{誤差}=𝒪\left(\frac{\sigma }{\sqrt{N}}\right)$$

次元 $d$ が現れない。 これが決定的な利点で、 $m^d$ 点を要する求積法が 高次元で破綻するのに対し、モンテカルロは影響を受けない。

代わりに収束は遅い（精度 1 桁で 100 倍の標本）。 低次元では求積法に大きく劣る。

分散削減#

誤差は $\sigma$ にも比例するので、$\sigma$ を下げる工夫が効く。

手法	考え方
重点サンプリング	寄与の大きい領域から多く引く
制御変量	期待値が既知の相関する量で補正
層化抽出	領域を分けて各々から引く
準モンテカルロ	低食い違い量列で $𝒪(1/N)$ に近づける

この分野での登場#

• 量子測定 — 期待値の推定そのものがモンテカルロ
• MCMC — 複雑な分布からの標本抽出
• 量子モンテカルロ
• 確率的最適化全般

参考文献#

• Nicholas Metropolis, Stanislaw Ulam. The Monte Carlo Method. Journal of the American Statistical Association 44(247), 1949. https://doi.org/10.1080/01621459.1949.10483310
• William H. Press et al. Numerical Recipes, 3rd ed. Cambridge University Press, 2007. https://numerical.recipes/
• Christian P. Robert, George Casella. Monte Carlo Statistical Methods, 2nd ed. Springer, 2004. https://doi.org/10.1007/978-1-4757-4145-2