乱数
計算機が作る「乱数」は、決定的なアルゴリズムの出力。 正しくは擬似乱数。
種 (seed) → 決定的な漸化式 → 一見ランダムな数列同じ種からは同じ列が出る。 これは欠点ではなく、再現性のために必須の性質。
生成器#
| 生成器 | 周期 | 評価 |
|---|---|---|
| 線形合同法 (LCG) | 短い | 下位ビットの質が悪い。使わない |
| Mersenne Twister | 長く使われた。統計的検定に一部落ちる | |
| PCG | 長い | 質が良く速い。NumPy の既定 |
| Philox、Threefry | — | 並列に分割しやすい |
| 暗号論的 (CSPRNG) | — | 予測不能。鍵・トークンにはこれ |
暗号用途に一般の擬似乱数を使ってはいけない。 出力から内部状態を復元でき、次の値が予測できる。
分布の変換#
一様乱数から他の分布を作る。
| 手法 | 内容 |
|---|---|
| 逆関数法 | 累積分布関数の逆関数を使う |
| Box-Muller | 一様 2 つ → 正規分布 2 つ |
| 棄却法 | 提案分布から採り、条件で受理する |
| Ziggurat | 高速。正規分布などで使われる |
並列での注意#
複数のスレッドやプロセスで乱数を使うとき、 同じ種を使うと同じ列になる。
python
# NumPy の推奨
rng = np.random.default_rng(seed)
children = rng.spawn(n_workers) # 統計的に独立な子生成器「プロセス ID を種にする」といった素朴な方法は、 系列が重なる危険がある。
実験での扱い#
| 指針 | 理由 |
|---|---|
| 種を記録する | 再現できるように |
| 複数の種で実行する | 1 つの種の結果は偶然かもしれない |
| 平均と分散を報告する | ばらつきを隠さない |
確率的アルゴリズムの比較では、 単一の実行結果を比べても意味がない。
参考文献#
- Pierre L’Ecuyer. Random Number Generation. In Handbook of Computational Statistics, Springer, 2012. https://doi.org/10.1007/978-3-642-21551-3_3
- Melissa E. O'Neill. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. HMC-CS-2014-0905, 2014. https://www.pcg-random.org/paper.html
- Makoto Matsumoto, Takuji Nishimura. Mersenne twister. ACM TOMACS 8(1), 1998. https://doi.org/10.1145/272991.272995
- NumPy documentation. Random Generator. https://numpy.org/doc/stable/reference/random/generator.html