擬似乱数生成器

擬似乱数生成器とは、初期シードから、単位区間上の一様分布からの独立した抽出を模倣する、再現性のある長い数列を生成する決定論的な漸化式である。

Definition

擬似乱数生成器とは、状態、状態を進める遷移関数、および各状態を数値にマッピングする出力関数によって定義されるアルゴリズムであり、一様乱数と統計的に区別できないことを意図した周期的な数列を生成する。

Scope

このトピックでは、一様生成器（線形合同法、ラグ付きフィボナッチ法、一般化フィードバックシフトレジスタ法、結合生成器）の構築、周期長や格子構造、等分布挙動といった品質を決定する構造的特性、およびそれらを検証するために用いられる経験的および理論的テストについて扱う。暗号論的に安全な生成器は、対照的な設計目標としてのみ言及される。

Core questions

• どのような漸化式が長い周期と良好な高次元一様性をもたらすのか？
• 生成器の品質は、その格子構造と等分布によってどのように測定されるのか？
• どのような経験的テストバッテリーがランダム性からの逸脱を検出するのか？
• 周期を延長し、統計的特性を改善するために、生成器はどのようにシードされ、結合されるのか？

Key concepts

• シードと状態
• 周期長
• 等分布
• 格子構造
• スペクトルテスト
• 結合生成器

Key theories

線形漸化式生成器

線形合同法およびシフトレジスタ漸化式は、モジュラー算術によって整数状態を進める。それらの周期と連続する出力の格子構造は、乗数と法数の数論的特性によって決定される。

等分布とメルセンヌツイスター

ねじれ一般化フィードバックシフトレジスタに基づく生成器は、非常に長い周期と多くの次元での証明可能な等分布を達成し、統計シミュレーションの広く採用されているデフォルトとなっている。

Clinical relevance

統計パッケージのデフォルトの生成器は、それが生成するすべてのシミュレーション、ブートストラップ、モンテカルロの結果の再現性と妥当性を決定する。周期と等分布を理解することは、隠れた規則性が高次元シミュレーションを損なう可能性のある生成器を実務者が避けるのに役立つ。

History

レーマーは1949年に線形合同法を提案した。その後の分析により、不適切に選択されたパラメータの格子欠陥が明らかになり、スペクトルテスト、結合生成器、そして最終的には1998年のメルセンヌツイスターのような長周期等分布設計が動機付けられた。

Key figures

• Donald Knuth
• Pierre L'Ecuyer
• Makoto Matsumoto
• Derrick Henry Lehmer

Seminal works

• knuth1997
• matsumoto1998

Frequently asked questions

ある擬似乱数生成器が他の生成器よりも優れているのはなぜか？

優れた生成器は、非常に長い周期を持ち、多次元でも出力を均一に分布させ、標準的な統計テストバッテリーに合格し、高速で再現性がある。劣悪な生成器は、周期が短かったり、シミュレーションに偏りをもたらす目に見える格子パターンを持っていたりすることがある。

なぜシードが重要なのか？

シードは開始状態を固定するため、数列全体がそれによって決定される。シードを記録することでシミュレーションは正確に再現可能となるが、シードを不用意に選択すると、並行実行間で重複したり相関したりするストリームが生じる可能性がある。