乱数生成器 - yuuk1's Digital Garden

# 乱数生成器 ## 定義乱数生成器(random-number generator)は、0と1の間に一様分布する数列を生成する漸化式ベースの手続きである。多くは $x_n=f(x_{n-1},x_{n-2},\ldots)$ の形を持つ決定論的な漸化式で、シード(seed、初期値$x_0$)を与えれば数列を何度でも再現できる。決定論的でありながら統計的検定に合格するという性質から疑似乱数(pseudo-random number)と呼ばれ、真の乱数と異なりシミュレーションの再現性を保証できる点がむしろ利点になる。良い生成器は (1) 効率的に計算できる、(2) 周期(period、数列が繰り返し始めるまでの長さ)が大きい、(3) 逐次値が独立かつ一様分布に従う、という3性質を満たす必要がある。中心的な設計方式は線形合同法(linear-congruential generator, LCG)$x_n=ax_{n-1}+b \bmod m$ で、乗数$a$・増分$b$・法$m$の選び方が周期と統計的な質を決める。LCG以外にもTausworthe生成器・拡張フィボナッチ生成器・複合生成器という代替方式があり、それぞれ異なる長所(暗号応用向けの長いビット列、LCGを超える長周期、複数生成器の弱点の相殺)を持つ。生成器を作る・選ぶ側の設計論は本ページが扱い、生成器の統計的検定は乱数生成器の検定([[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 27 Testing Random-Number Generators]])、乱数の列を任意の確率分布へ変換する乱数変量生成は[[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 28 Random-Variate Generation]]の主題であり、本ページの対象外とする(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] §26.1-§26.8)。 ## 横断的知見 - **第24章は本概念の答えを第26章に明示的に先送りしている**: 第24章はシミュレーションが失敗する8つのよくある誤りの1つに「貧弱な乱数生成器」を、もう1つに「シードの不適切な選択」を挙げ、前者には「自作より広く分析済みの既知の生成器を使うほうが安全(第26章で詳述)」、後者には「シード選択の指針は§26.7」と、いずれも本章への forward reference を伴って記述する。第26章はこの2つの約束を、§26.6(実装済み生成器の実例集による「自作するな」の具体化)と§26.7(6項目のシード選択指針)としてそれぞれ回収しており、第24章が抽象的なチェックリスト項目として提示した内容の技術的な実体が第26章にある、という関係が確認できる(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] §24.1, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] §26.6-§26.7)。 - **第25章のモデル検証技法「シードの独立性」は、第26章のマルチストリーム指針と同じ問題を別の角度から照射する**: 第25章はモデル検証技法の1つとして「シードの独立性(seed independence): 乱数生成に使うシードの値は最終的な結論に影響してはならず、異なるシード値で似た結果が得られることを確認する必要がある」と述べるが、それをどう保証するかの具体策には立ち入らない。第26章§26.7の「重複しないストリームを使う」指針(各ストリームに重複しないシードを事前計算して割り当てる)は、まさにこの検証テストが合格するための設計上の前提条件を与えている。第25章が「結果として確認すべきこと(検証のチェック項目)」を述べるのに対し、第26章は「そもそもそれが成り立つように生成器とシードを設計する方法」を述べており、検証と設計が対になっている(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 25 Analysis of Simulation Results]] §25.1.11, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] §26.7)。 - **[[モンテカルロシミュレーション]]が前提とする「乱数入力の生成」という最初のステップは、本ページが扱う一様乱数列の生成そのものに立脚する**: [[モンテカルロシミュレーション]]の定義(PRE第4章)は「決定論的モデルを、入力を乱数の集合として反復的に評価する手法」であり、逆変換抽出法(inverse transform sampling)によって一様乱数から任意の分布の標本を得るとする。しかしPRE第4章もJain(1991)第24章も、その大元になる一様乱数の列がどう作られるかには立ち入らない。本章(第26章)はその空白を埋める層であり、モンテカルロシミュレーションが暗黙に前提とする「一様乱数列」がLCGなどの漸化式によって具体的にどう構成されるかを示す。したがって層の関係は、乱数生成器(一様乱数列の生成)→乱数変量生成(分布への変換、第28章)→モンテカルロシミュレーション(変換済みの乱数変量を使ったモデル評価)という積み上げになる(Source: [[モンテカルロシミュレーション]], [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] §26.1)。 - **[[サンプリング手法]]とは「選ぶ」対象の階層が異なる**: [[サンプリング手法]]は機械学習の訓練データという有限の母集団から代表的な部分集合を選ぶ方法(層化サンプリング・重み付きサンプリング等)を扱う。これに対し本ページの乱数生成器は、母集団からの選択ではなく0と1の間の一様分布に従う数値そのものを漸化式で作り出す層であり、サンプリング手法の確率サンプリング(特に重み付きサンプリングや重点サンプリング)が「どの確率で選ぶか」を決めた後、その確率的決定を実際に下すための乱数源として乱数生成器を必要としうる。両者は「乱数」という語を共有するが、前者は有限母集団からの選択方針、後者はその選択を実現する数値的な基盤という異なる層に属し、直接の依存関係はどちらのソースにも明示されていない(Source: [[サンプリング手法]], [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] §26.1)。 - **第27章は「線形合同法という設計そのものに内在する構造的弱点」を明らかにし、第26章の実例集の記述をより深い理由付けに接続する**: 第26章§26.6はRANDU($x_n=(2^{16}+3)x_{n-1}\bmod2^{31}$)の欠陥を「連続する3つの数が三次元空間でわずか15枚の平面に乗ってしまう」という個別事例として報告するが、なぜLCGが一般にこの種の欠陥を持ちうるのかには立ち入らない。第27章§27.7のスペクトル検定は、LCGの逐次k組が有限個の平行超平面上に並ぶことが漸化式の線形性そのものに由来する構造的性質であり、Marsaglia(1968)の上界(k組を含む超平面数は高々$k!\,m^{1/k}$枚)がどの乗数・法を選んでも次元が増えるほど超平面数が減ることを示す。したがってRANDUの欠陥は「悪い乱数生成器固有の欠陥」ではなく、「LCGという設計方式全般が持つ弱点が、悪い乗数選択によって極端な形で露呈した一事例」と読み直せる。この読み替えは第26章単体でも第27章単体でも得られず、両章を突き合わせて初めて見える(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] §26.6, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 27 Testing Random-Number Generators]] §27.7)。 - **第26章の誤解2「1つの検定で十分」は、第27章のExample 27.7で具体的な反例として再現される**: 第26章§26.8は「数列$0,1,\ldots,m-1$はカイ二乗検定には満点で合格するがラン検定には失敗する」と抽象的に警告するにとどまるが、第27章Example 27.7は$x_n=3x_{n-1}\bmod31$と$x_n=13x_{n-1}\bmod31$という2つのLCGがいずれも(1から30の順列を生成するため)カイ二乗検定には合格しながら、スペクトル検定では格子構造の質が明確に異なる(前者は間隔9.80の3本線、後者はより密な6本線)ことを数値で示す。第26章の警告が第27章で「どの検定の組み合わせがその警告を裏付けるか」という具体例として結実している(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] §26.8, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 27 Testing Random-Number Generators]] §27.7 Example 27.7)。 - **第28章は本ページが第26章冒頭で予告していた「乱数変量生成」の実体であり、良い一様乱数列が満たすべき3性質(独立性・一様性・大きな周期)のうち独立性の欠陥が具体的にどう伝播するかを明らかにする**: 第28章§28.1の逆変換法は一様乱数uを1個消費してx=F⁻¹(u)を計算するだけなので、逐次uどうしの独立性が崩れていても各xの周辺分布自体は保たれる。これに対し§28.2の棄却法は1回の試行につき独立な2つの一様乱数(xの生成用とy=U(0,cg(x))用)を必要とし、両者の間や連続する試行間に構造的な相関があると、採否判定y≤f(x)が本来の受理領域からずれ、生成される変量の分布が歪む可能性がある。第27章§27.7がスペクトル検定で検出する「LCGの逐次k組が有限個の超平面上に並ぶ」という欠陥は、まさにこの棄却法が要求する多変量的な独立性を壊す種類の欠陥であり、第26章・第27章が周辺分布の一様性検定(カイ二乗・K-S)だけでは見抜けないと警告する構造的弱点が、第28章の棄却法という具体的な消費者を通じて実害になりうることが分かる。この関係は各章単体では明示されず、3章を突き合わせて初めて見える(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 27 Testing Random-Number Generators]] §27.7, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 28 Random-Variate Generation]] §28.1-§28.2)。 ## 未解決の問い - 線形合同法・Tausworthe生成器・拡張フィボナッチ生成器・複合生成器という4方式のうち、第27章の検定手法にどの方式が最も強いかは部分的にしか判明していない。第27章はLCGの格子構造(スペクトル検定)とTausworthe生成器の2つの原始多項式間の2次元一様性の差(Example 27.4/27.5、視覚的確認)は具体的に示すが、4方式を同一の検定で横並びに比較する記述はない。拡張フィボナッチ生成器・複合生成器が第27章の各検定(特にスペクトル検定)にどの程度強いかは第26章§26.5の定性的な記述(複合生成器は超平面への集中という問題を持たないとL'Ecuyer(1988)が主張)以上には確認できていない。 - 第26章はTausworthe生成器を暗号応用の文脈で紹介するが、LCGが暗号応用に不適な理由(連続する数個の値から乗数・法を逆算できる予測可能性、§26.8誤解3)がTausworthe生成器やその他の代替方式にどこまで当てはまるかは明示的には論じられていない。 - モンテカルロシミュレーション(PRE第4章)の逆変換抽出法が要求する一様乱数の性質(独立性・一様性)と、本章が定義する良い生成器の3性質との対応関係は、本ページの横断的知見で初めて明示的に接続されたものであり、PRE第4章側からの言及はない。PRE第4章が実際にどの乱数生成器(LCG等)を前提にしているかは同章からは確認できていない。 - 第28章の棄却法が要求する「1試行内で消費する2つの一様乱数の独立性」を、第26章・第27章のどの検定が直接保証するかは、本ページの横断的知見で指摘した構造的懸念にとどまる。第27章のスペクトル検定はk組の逐次値がなす格子構造を検出するが、それを棄却法の受理率や生成される変量の分布のずれの大きさに定量的に結び付ける記述はどのソースにも見当たらない。 ## 関連 - source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 26 Random-Number Generation]] / [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 27 Testing Random-Number Generators]] / [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 28 Random-Variate Generation]] / [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 24 Introduction to Simulation]] / [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 25 Analysis of Simulation Results]] - 概念: [[離散事象シミュレーション]](乱数生成器を要素とするシミュレーションの共通構造) / [[モンテカルロシミュレーション]](乱数生成器の出力を分布変換して使う応用) / [[サンプリング手法]](階層の異なる別の「選ぶ」問題) / [[統計的有意性]](生成器の検定に使うカイ二乗検定・K-S検定という適合度検定の技法群) - 実体: [[Raj Jain]] / [[The Art of Computer Systems Performance Analysis]] ## 出典 - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 26, §26.1-§26.8; Chapter 27, §27.1-§27.7; Chapter 28, §28.1-§28.2.