モンテカルロ法,乱数,および疑似乱数

杉 田  洋
大阪大学大学院理学研究科数学専攻
説明: C:\Users\sugita\Documents\MacBackup\Sites\mail_addr.gif

モンテカルロ法って何でしょうか?
乱数って何でしょうか?
なぜモンテカルロ法には乱数が必要だと言われるのでしょうか?
コンピュータで生成される疑似乱数は本当に乱数の代用にしてよいのでしょうか?...

To English page

Home


モンテカルロ法って何でしょうか?

 モンテカルロ法では問題に応じて確率空間 --- 簡単のため,L 回の硬貨投げの確率空間

( {0,1}L, PL = 一様確率測度 ),  L N

とします --- と,その上で定義された確率変数 S を設定します.ここでは L=100,000,000,すなわち S ω{0,1}100,000,000の関数としましょう.ωを一つ選んで S(ω) の値を求めることをサンプリング(標本抽出)といいます.モンテカルロ法の目的は S 一般的な値(Sのとりうる値のうちで例外的でない値)をサンプリングすることです.

説明: C:\Users\sugita\Documents\MacBackup\Sites\generic.GIF

 モンテカルロ法は確率的ゲーム,すなわち賭け,の一種と捉えるのが適切です.プレーヤー(以下,アリスと呼ぶ)は S のサンプリングを行い,もし得られた値が S の一般的な値ならば勝ち,もし例外的な値なら負け,とします.S の例外的な値を与えるようなωの全体の集合を A としましょう.繰り返しになりますが,アリスの選んだωA の元でなければアリスの勝ち,A の元ならばアリスの負けです. S は滅多に例外的な値をとりませんから,A {0,1}100,000,000のとても小さな部分集合です.一様確率測度 PL の下での彼女の負ける確率 q

q = A の元の個数 ) / 2100,000,000

でとても小さくなります.ですから,この賭けはアリスに大変有利な賭けです.


乱数って何でしょうか?
なぜモンテカルロ法には乱数が必要だと言われるのでしょうか?


 ところが,アリスがこの賭けに勝つのは,じつは容易なことではないのです.理由を説明しましょう.S のサンプリングを行うためにアリスは100,000,000 ビットのデータωを選ばなければなりません.それにはデータの大きさから言ってコンピュータを用いるよりないでしょう.もちろん,そのような巨大なデータをキーボードから直接入力することなど事実上不可能です.何らかの道具が必要です.じつはどんな道具を用いても,アリスが自分の意思で選ぶことのできるωはきわめて少数なのです.実際,アリスがキーボードから入力できるデータが高々1,000ビットだったとすると,アリスが選ぶことのできるωの総数は高々21,001個に過ぎません(k ビットの入力の総数は 2k なので,21+22+...+21,000=21,001-2){0,1}100,000,000 の元は全部で 2100,000,000個もあるのですから,アリスの選ぶことのできるωがいかに少数であるか分かるでしょう.彼女の負ける確率 q はとても小さい,と述べましたが,それはあくまで「すべての{0,1}100,000,000 の元を同様に確からしく選ぶ」という仮定に基づいているのであって,実際にはこの仮定が満たされない以上,この賭けがアリスにとって有利かどうか分からなくなってしまいます.

 「アリスの負ける確率 q 」に実質的な意味を持たせるためには,{0,1}100,000,000 の大部分を占める「アリスの意思では選ぶことのできないようなω --- そのようなωをコルモゴロフは乱数と呼びました --- によるサンプリングが必要であると考えるのは当然です.これが「モンテカルロ法には乱数が必要である」と言われる理由です.


コンピュータで生成される疑似乱数は本当に乱数の代用にしてよいのでしょうか?

 では,乱数は絶対に必要なのでしょうか? いいえ,そうとも限りません.疑似乱数(擬似乱数とも書く)が乱数の役割を果たしてくれるかも知れないからです.いま,アリスが 1,000 ビットのデータ ω' を自分の意思で選び,コンピュータにキーボードから入力するとします.コンピュータはあるプログラム g でそれを100,000,000のビットのデータg(ω') に変換し,さらにそれを用いて S のサンプリングを行い S(g(ω')) を出力します.プログラム g は数学的には1,000 ビットの入力から 100,000,000 ビットを出力する関数で疑似乱数生成器と呼ばれ,ω' g(ω') 疑似乱数と呼ばれます.

 疑似乱数生成器 g を用いることによってアリスは新しい賭けをすることになります.すなわち,g(ω') A の元であれば負け,そうでなければ勝ち,という賭けです.この賭けでは,アリスは長さ 1,000 のどのようなビット列 ω' も選ぶことができますから,アリスの負ける確率 q' は実質的な意味で

q' = ( g(ω') A となるような ω' の個数 ) / 21,000

となります.ここでもし,q' q とほぼ等しいようであれば,アリスは実際に高い確率でこの新しい賭けに勝つことができるでしょう.そのような g 安全な疑似乱数生成器と呼びます.g を用いてもアリスの負けるリスクが増えないので安全と呼ぶのです.安全な疑似乱数生成器が存在するならそれが生成する疑似乱数を乱数の代用にしてかまいません

 現時点では残念ながら,どんな確率変数 S に対しても安全であるようなオールマイティの疑似乱数生成器の存在は知られていません.しかし S モンテカルロ積分で扱われる確率変数,すなわちある独立同分布確率変数列の標本平均であるような場合には,S に対して安全な疑似乱数生成器が存在し,大きすぎない規模のモンテカルロ積分ではすでに実用化されています(ランダム-ワイル-サンプリング(RWS)).つまりその場合は問題は完全に解決されているのです.


...つづきは,以下をご参照ください.

(1)  杉田洋,「確率と乱数」,日本数学会市民講演会,20133
講演映像: http://mathsoc.jp/videos/2013spring/05-0002.html
講演記録pdf (数学通信,第18巻第2号,20138) : Download

(2)  杉田洋,「確率と乱数」,数学書房,数学書房選書420147月,はじめに,目次
英語訳: http://www.worldscientific.com/worldscibooks/10.1142/10662

(3)  H.Sugita, Monte Carlo Method, Random Number, and Pseudorandom Number, MSJ Memoirs vol.25 (2011), pp.xiv+133.
冊子体配給: World Scientific
電子媒体Project Euclid : Download page
正誤表 (2016.09.01): Download

(4)  杉田洋,「モンテカルロ法,乱数,および疑似乱数」,(3)邦訳改訂版 (ver. 20160624) : Download

(5)  杉田洋,「モンテカルロ法の数学的定式化」,(3)の邦訳抜粋版(2012.11.22改訂): Download


Home

Last update: 2017.10.10

End of page