統計的ランダム性
数値列は、認識可能なパターンや規則性が含まれていない場合、統計的にランダムであると言われます。理想的なサイコロの出目やπの数字などの列は、統計的ランダム性を示します。[ 1 ]
統計的ランダム性は必ずしも「真の」ランダム性、すなわち客観的な予測不可能性を意味するものではありません。統計など多くの用途では擬似ランダム性で十分であるため、統計的ランダム性と呼ばれます。
グローバルランダム性とローカルランダム性は異なります。ランダム性に関する哲学的概念のほとんどはグローバルです。なぜなら、それらは「長期的には」あるシーケンスは真にランダムに見えるものの、一部の部分シーケンスはランダムに見えないという考えに基づいているからです。例えば、十分な長さを持つ「真に」ランダムな数列では、シーケンス全体としてはランダムである可能性はありますが、繰り返し数字だけの長いシーケンスが存在する可能性があります。ローカルランダム性とは、ランダム分布に近似するシーケンスの最小の長さが存在する可能性があるという考えです。同じ数字が長く続く場合、たとえそれが「真に」ランダムなプロセスによって生成されたものであっても、サンプルの「ローカルランダム性」は低下します（例えば、10,000個のシーケンスの場合のみローカルランダムである可能性があり、1,000個未満のシーケンスでは全くランダムに見えない可能性があります）。
パターンを示す配列は、統計的にランダムではないと証明されるわけではない。ラムゼー理論の原理によれば、十分に大きな物体は必ず所定の部分構造を含んでいなければならない（「完全な無秩序は不可能」）。
ギャンブルに関する法律では、スロットマシンに統計的ランダム性に関する一定の基準を課しています。
検定
乱数の最初の検定は、1938年にMGケンドールとバーナード・バビントン・スミスによって王立統計学会誌に発表されました。 [ 2 ]これらは、実験現象が理論上の確率と一致するかどうかを区別するために開発されたピアソンのカイ二乗検定などの統計ツールに基づいて構築されました。ピアソンは、WFRウェルドンによるいくつかのサイコロ実験が「ランダム」な挙動を示さないことを示すことで、 この検定を最初に開発しました
ケンドールとスミスの最初の 4 つのテストは仮説検定であり、与えられたランダムなシーケンス内の各数字の発生確率は等しく、データ内のその他のさまざまなパターンも等確率で分布するはずであるという考えを帰無仮説として採用しました。
- 頻度テストは非常に基本的なもので、0、1、2、3 などの数がほぼ同じであるかどうかを確認するものでした。
- シリアルテストでは、同じことを行いますが、一度に 2 つの数字のシーケンス (00、01、02 など) に対して、観測された頻度と、それらが均等に分布しているという仮説的予測を比較します。
- ポーカーテストは、ポーカーゲームのハンドに基づいて、一度に 5 つの数字の特定のシーケンス (AAAAAA、AAAAB、AAABB など) をテストします。
- ギャップテストでは、ゼロ間の距離を調べました (00 は距離 0、030 は距離 1、02250 は距離 3 など)。
あるシーケンスが、これらのテストを全て、所定の有意水準（通常5%）内でパスした場合、彼らの言葉を借りれば「局所ランダム」であると判断されました。ケンドールとスミスは、「局所ランダム性」と「真のランダム性」を区別しました。真のランダム手法で生成されたシーケンスの多くは、所定の程度まで「局所ランダム性」を示さない可能性があるからです。非常に大きなシーケンスには、1桁の数字の行が多数含まれる場合があります。これはシーケンス全体のスケールでは「ランダム」かもしれませんが、小さなブロックでは「ランダム」ではなく（彼らのテストに合格しないため）、多くの統計アプリケーションには役に立ちません。
乱数セットが一般的になるにつれて、より高度な検定法が用いられるようになりました。現代の検定法の中には、乱数を三次元平面上の点としてプロットし、それを回転させることによって隠れたパターンを探すものもあります。1995年、統計学者のジョージ・マルサリアはダイハード検定として知られる検定法を開発し、50億個の疑似乱数を収録したCD-ROMに同梱して配布しています。2015年には、ヨンゲ・ワンが統計的距離に基づく乱数検定のための Javaソフトウェアパッケージ[ 3 ]を配布しました。
疑似乱数生成器は、 「真にランダムな」プロセスではなく、決定論的なアルゴリズムによって生成されるため、「ランダム性」の検証にはテストのみが必要です。乱数生成の歴史において、テストでは「ランダム」に見えると思われていた数値源の多くが、後に特定の種類のテストを行うと非常に非ランダムであることが発見されました。準乱数の概念はこれらの問題の一部を回避するために開発されましたが、疑似乱数生成器は多くのアプリケーション（極めて「非ランダム」であることが知られているものも含む）で依然として広く使用されています。これは、ほとんどのアプリケーションにおいて「十分に優れている」ためです。
その他のテスト：
- モノビットテストは、乱数生成器の各出力ビットをコイン投げテストとして扱い、観測された表と裏の数が予想される50%の頻度に近いかどうかを判断します。コイン投げの回数は二項分布を形成します
- Wald –Wolfowitz 法では、 0 ビットと 1 ビットの間のビット遷移の数をテストし、観測された頻度をランダム ビット シーケンスの予想頻度と比較します。
- 情報エントロピー
- 自己相関検定
- コルモゴロフ・スミルノフ検定
- 統計的距離に基づくランダム性検定。Yongge Wangは[ 4 ] [ 5 ] NIST SP800-22の検定基準ではランダム性生成器の弱点を検出するのに不十分であることを示し、統計的距離に基づくランダム性検定を提案した。
- スペクトル密度推定[ 6 ] - ランダムな信号にフーリエ変換を施すことで、周期関数の和に変換し、ランダムでない繰り返し傾向を検出する。
- マウラーの普遍統計検定
- ダイハードテスト
参照
参考文献
- ^円周率は優れた乱数生成器のように見えるが、必ずしも最良とは限らない、チャド・ブーティン、パデュー大学
- ^ Kendall, MG ; Smith, B. Babington (1938). 「ランダム性とランダムサンプリング数」. Journal of the Royal Statistical Society . 101 (1): 147– 166. doi : 10.2307/2980655 . JSTOR 2980655 .
- ^ Yongge Wang. 擬似乱数生成のための統計的検定手法. http://webpages.uncc.edu/yonwang/liltest/
- ^ Yongge Wang: (擬似)乱数発生器のLILテストの設計といくつかの実験結果について。PDF
- ^ Wang, Yongge; Nicol, Tony (2015). 「擬似乱数列の統計的特性とPHPおよびDebian OpenSSLを用いた実験」. Computers and Security . 53 : 44–64 . doi : 10.1016/j.cose.2015.05.005 .
- ^ドナルド・クヌース (1998). 『コンピュータプログラミングの技法 第2巻 半数値アルゴリズム』 アディソン・ウェズリー. pp. 93– 118. ISBN 978-0-201-89684-8。
外部リンク
