知らなくても不都合は無いメルセンヌ・ツイスタの知識

| ← back |
| home |

　日本で生まれた品質の良い擬似乱数生成手法として大きな話題になったメルセンヌ・ツイスタは、いまや各種のプログラミング言語の標準ライブラリに取り込まれて手軽に使える当たり前の存在になったのは喜ばしいことです．

　しかし、当たり前になったらなったでネット上でメルセンヌ・ツイスタを誤解した、あるいは無理解による不適切な言説が見られるのは残念です．　このような誤解・無理解を正すのは、本来は擬似乱数の専門家の方が適任なのですが、知り合いにそのようなことを頼める方がいないので素人が素人向けの解説をしてみたいと思います．（知らなくても不都合は無い無駄知識のようなものですが）

　素人が書いたことなので厳密性に欠ける記述だったり、間違いがあるかもしれませんが、疑問に思うことがあったらご自分で信頼性のある情報を調べてみることをお勧めします．

メルセンヌ・ツイスタはメモリ使用量、コードサイズが大きすぎる（？？？）

　これは意味の無い批判・不満です．　有限長のレジスタの逐次書き換えによる擬似乱数発生法の品質は、定性的にはレジスタ長に比例します．　品質の良いメルセンヌ・ツイスタのメモリ使用量が多いのは当たり前です．　メルセンヌ・ツイスタと同程度の品質の擬似乱数生成手法で、メルセンヌ・ツイスタよりもメモリ使用量の少ないものが存在するのでしょうか？
メルセンヌ・ツイスタ（MT19937）ほどの長周期は必要ないからメモリ使用量の少ない擬似乱数を使いたいというのであれば、TinyMT（Tiny Mersenne Twister）があります．

メルセンヌ・ツイスタには欠陥がある・検定テストに落ちる（？？？）

　物は言いようとはよく言ったもので、メルセンヌ・ツイスタが落ちる検定をパスするからメルセンヌ・ツイスタよりも優れていると称する擬似乱数生成手法があります．
ところが、そのような擬似乱数はメルセンヌ・ツイスタがパスする検定にボロボロ落ちるのです．

　実は上記の文章は正確ではありません．　すこし丁寧に説明しましょう．
正確に表現すると、高次元の分布特性の偏りの検定テストが存在したのなら、メルセンヌ・ツイスタはパスするが他の擬似乱数はボロボロ落ちるのです．　メルセンヌ・ツイスタMT19937は623次元までの高次均等分布が理論的に保証されているので、（623次元まで）パスするのは当然です．
ただし、現実にはそのような検定を厳密におこなう現実的手法は存在しないようです．（残念！　でもメルセンヌ・ツイスタは検定に頼る必要がありません）

　検定にのみ頼ってメルセンヌ・ツイスタより優れていると称する擬似乱数は、検定方法が無いからといって高次元の分布特性を無視している・高次元分布特性が劣っていることを隠していると判断せざるをえません．　意図的に品質についての誤認を誘おうとするようなセールス・トーク、ハッタリをかます擬似乱数生成手法は信用しないのが無難です．
（この種の英文のセールス・トーク、ハッタリを日本語に翻訳して拡散する必要もありません）

　メルセンヌ・ツイスタが落ちる検定テストがあるのは事実のようですが、それをもって現実のアプリケーションでの使用にあたって問題が生ずるのかどうかは丹念に検討する必要があるでしょう．
　有限長のレジスタを用いた擬似乱数生成手法はリングバッファに記録された擬似乱数を逐次読み出しているようなものです．
例えば、レジスタ長32bitであれば長さ2^32-1=4294967295のリング・バッファの内容を出力しているのと同じです．　したがってある値が次に出力されるまで2^32-1=4294967295回かかります．　真の乱数とは異なり、同一の値が短い間隔で出力されることも・連続して出力されることもありません．
　一周期以上の乱数列の観測をしなくても、このような周期性を有する擬似乱数に特徴的な特性を確率的に判定出来る試験方法があるそうです．（真の乱数と周期性のある擬似乱数を判別出来る）　そのような手法でメルセンヌ・ツイスタの出力を調べたのなら、真の乱数では無い周期性を有する擬似乱数だから品質が低いと判定することは可能です．

　確かに整数で組合せ論や数論（Number Theory）の理論的シミュレーション等をするなら、有限長のレジスタを用いた周期を有する擬似乱数を用いるのは不都合があるであろうことは理解出来ます．　しかし浮動小数点演算の物理シミュレーションで、長大な周期を有するメルセンヌ・ツイスタの部分系列を用いるのに何か不都合があるでしょうか？　周期以下の間隔で同一の値が出現することが絶対に無いというような特性が問題なら、そもそも計算機の浮動小数点フォーマットそのものの「欠陥」の方が問題になるのではないでしょうか？（一般的な浮動小数点フォーマットで表わしうる値は数直線上に等間隔では分布しないという偏りがあります）

メルセンヌ・ツイスタMT19937は なぜ桁外れにレジスタ長が大きいのか？

　一般的に用いられるレジスタ長32bitや64bit、128bitの擬似乱数生成手法と比較して、メルセンヌ・ツイスタMT19937は19937bitという極端に長いレジスタ長（＝周期）を持っています．
何故でしょうか？

　特定の検定試験にパスすることのみを目的とした「古い」擬似乱数生成手法と異なり、メルセンヌ・ツイスタは数学的な原理に基づいて特性の良い擬似乱数を出力するように設計されています．（開発者の松本氏の解説をご覧ください〜と書きたいのですが以前読んだ日本語の資料を見つけることができませんでした）
MT19937の設計原理は、高次の分布特性の良好な擬似乱数はそれ以外の特性も概ね良好であるという事実に基づいています．　問題は、これはあくまでも定性的な性質であって擬似乱数としての品位が全般的に良好であることを主張するには、十分に高い次数まで分布特性が均一である必要があります．　そのためには、他の擬似乱数生成手法よりもレジスタ長を大きくする必要があります．（レジスタ長のマージンを大きく取らなければならない）

　様々な設計の場面において、十分にマージンを確保するにはどの程度の倍率・比率を取れば良いでしょうか？
　電子回路で回路特性に直接影響しないような抵抗、コンデンサなら倍／半分程度の誤差があっても良いように値を選びます．　機械系の設計であれば２倍の強度マージンは過大かもしれません．　航空機やロケットの設計では無闇に強度を大きくすると重くて飛べなくなるので、かなり控えめなマージン設定になっているはずです．
　擬似乱数のレジスタ長のマージンはどうでしょう？　擬似乱数の定性的性質に基づいて十分な品質を保証するとすれば、比較対象となる他の擬似乱数に対して最低でも10倍（1 decade）程度のマージンは必要で、他よりも非常に特性の良い擬似乱数を生成したければ10倍の倍、すなわち10倍ｘ10倍で100倍のマージンは欲しいところでしょう．
MT19937は128bit擬似乱数に対して約155倍（19937/128=155.7578）のレジスタ長をもっていますから、上記の推測はいい線をいっていると思います．　設計者の松本氏はこのあたりを丹念に検討した上で19937というレジスタ長を選択されたのでしょうが、結果として品質とメモリ必要量・生成速度のバランスが取れた非常に良い判断ではなかったと思われます．　もしMT19937で性能が足らなければ、松本氏が述べられているようにより大きなメルセンヌ素数を用いた改良版を作って使えば良いのです．
| ← back | ↑top |
| home |