モンテカルロ法のソースを表示

'''【もんてかるろほう (Monte Carlo method)】'''

=== 概要 ===

乱数を使って実験する方法のこと. 第二次世界大戦中に原爆の開発に関する極秘プロジェクトを示す符丁として, フォンノイマン等がカジノで有名なモンテカルロに因んで命名したとされている.本来は, 確率的な変動を含まない問題を解くのに乱数を利用する方法のことであったが, 現在では乱数を使う実験の総称として使われることが多い.

=== 詳説 ===

　システムの特性値などを推定するために, 適当なモデルと乱数を使って実験し, 大数の法則や中心極限定理などを利用して推測を行う方法のこと. システムに確率的な変動が内在する場合だけでなく, 確定的な問題を解くためにも使われる. 

　[[モンテカルロ法]]の原理を簡単な例で示そう. 推定したい特性値を <math>\theta \,</math>とし, これは既知の分布関数 <math>F(y) \,</math>を持つ確率変数 <math>Y \,</math>の関数 <math>g(Y) \,</math>の平均値に等しいものとすれば, 


<center>
<math>
\theta = E[g(Y)]=\int_{-\infty}^\infty g(y)\mathrm{d}F(y) =
\int_0^1 h(u) \mathrm{d}u, \, 
</math>
</center>


と書ける. ただし, <math>h(u)=g(F^{-1}(u)) \,</math>である. そこで, 区間[0,1]上の一様乱数 <math>U_1, U_2, \cdots, U_N \,</math>を発生し, 算術平均


<center>
<math>
A_1(N) = \sum_{i=1}^N h(U_i)/N \, 
</math>
</center>



を<math>\theta \,</math>の推定値とすることが考えられる. <math>A_1(N) \,</math>は<math>\theta \,</math>の不偏推定量であり, 分散は

<center>
<math>
V(A_1(N)) = \frac{\sigma^2}N, \ \ \ \ \ 
\sigma^2 = \int_0^1 h^2(x) \mathrm{d}x-\theta^2 \, 
</math>
</center>


となる. したがって, 推定量 <math>A_1(N) \,</math>に含まれる誤差の標準偏差は <math>\sigma/\sqrt N \,</math>であり, 精度を十進で1桁上げるためには, サンプル数 <math>N \,</math>を10倍に増やさなければならない. このように, モンテカルロ法の収束は遅いので, これを改善するための方法が種々提案されており, [[分散減少法]]と総称されている. ただし, これらは <math>1/\sqrt N \,</math>というオーダーを改善するものではなく, 比例係数を小さくするための工夫である. 

［[[重点サンプリング]]］

　積分区間から一様にサンプルをとるのではなく, 重要と考えられる部分(<math>h(x) \,</math>の絶対値が大きい部分)により多くの重みをおく密度関数<math>w(x) \,</math>に従う乱数<math>X_1,\cdots, \ \ X_N \,</math>を発生し, 


<center>
<math>
A_2(N) = \frac 1 N \sum_{i=1}^N \frac{h(X_i)}{w(X_i)} \, 
</math>
</center>


で<math>\theta \,</math>を推定する. <math>w(x) \,</math>が<math>\left| h(x) \right| \,</math>に比例するように選べれば分散は最小となるので, なるべくそれに近くなるように工夫する. 
 

［[[制御変量法]]］

　<math>\theta \,</math>に対するひとつの不偏推定量を<math>Y \,</math>とする. <math>Y \,</math>と相関があって平均値<math>\zeta \,</math>が既知の確率変数<math>Z \,</math>のことを, <math>Y \,</math>の制御変量という. <math>\alpha \,</math>を定数として


<center>
<math>
Y_\alpha = Y-\alpha(Z-\zeta) \, 
</math>
</center>


と定義すれば, <math>Y_\alpha \,</math>も<math>\theta \,</math>の不偏推定量となり, その分散は<math>\alpha^* = \mathrm{Cov}(Y, Z)/V(Z) \,</math>のとき最小となり, 最小値は


<center>
<math>
V(Y_{\alpha^*})=(1-\rho^2)V(Y) \, 
</math>
</center>


である. ここで<math>\rho \,</math>は<math>Y \,</math>と<math>Z \,</math>の相関係数であるから, <math>Y \,</math>と相関の強い制御変量を選ぶほど効果的である. 

　定積分の例では, <math>h(u) \,</math>に近い関数<math>h_0(u) \,</math>で, その積分の値<math>\zeta \,</math>が正確に計算できるものを選び, 


<center>
<math>
Y_\alpha = h(u)-\alpha(h_0(u)-\zeta) \, 
</math>
</center>


に対して単純な一様サンプリングを適用する. 

［[[負相関変量法]]］

　<math>\theta \,</math>の不偏推定量<math>Y \,</math>と平均値が同じで負の相関を持つ変量<math>Z \,</math>を利用して, <math>W=(Y+Z)/2 \,</math>を<math>\theta \,</math>の推定量とする. この分散は, <math>Y \,</math>に対して2回独立にサンプルをとって平均する場合の分散より小さくなる. 定積分の例では, もし<math>h(u) \,</math>が単調な関数ならば, <math>Y=h(U),\;\;\;Z=h(1-U) \,</math>とするとよい. 

［[[共通乱数法]]］

　二つの特性値<math>\theta,\phi \,</math>をそれぞれ確率変数<math>X,Y \,</math>に関するモンテカルロ実験によって推定し, 比較したいものとし, <math>\theta=E[X], \phi=E[Y] \,</math>とする. 


<center>
<math>
V(X-Y)=V(X)+V(Y)-2 \mathrm{Cov}(X,Y) \, 
</math>
</center>


であるから, <math>{\mathrm{Cov}}(X,Y) \,</math>が大きいほど推定の精度が良くなる. <math>X \,</math>と<math>Y \,</math>の分布関数をそれぞれ<math>F,G \,</math>とし, <math>X \,</math>と<math>Y \,</math>を逆関数法で作るものとする. このとき, <math>X \,</math>と<math>Y \,</math>用に別々の一様乱数列を使う代りに, ひとつの乱数列<math>\{U\} \,</math>を使って, <math>X=F^{-1}(U), Y=G^{-1}(U) \,</math>とすれば, <math>\mathrm{Cov}(X,Y) \,</math>が最大となる. これが共通乱数法の原理である. 



----
'''参考文献'''

[1] 伏見正則, 『確率的方法とシミュレーション』(岩波講座 応用数学), 岩波書店, 1994. 

[2] G. S. Fishman, ''Monte Carlo-Concepts, Algorithms, and Applications'', Springer, 1996.

[3] A. M. Law and W. D. Kelton, ''Simulation Modeling and Analysis, 2nd. ed.'', McGraw-Hill, 1991.

[[category:シミュレーション|もんてかるろほう]]

[[Category:非線形計画|もんてかるろほう]]