乱数列

提供: miniwiki
2018/8/19/ (日) 17:44時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

乱数列(らんすうれつ)とはランダムな数列のこと。 数学的に述べれば、今得られている数列 x1, x2, ..., xn から次の数列の値 xn+1 が予測できない数列。乱数列の各要素を乱数という。

擬似乱数列と真の乱数列

決定的オートマトンen:deterministic automaton)であるコンピュータでは、基本的には確定的な計算によってしか数列を作ることができない。しかし、確定的な計算によって作られた数列でありながら、統計的にはサイコロなどで作られた乱数列と近似の性質を持つ数列の生成法があり、そのようにして生成された数列を擬似乱数列という。特にコンピュータへの実装に関しては、ビット列を生成することから Deterministic Random Bit Generator(DRBG)という語もある。「乱数列と近似の性質」の評価(検定)に関しては各種の提案があるが、標準としては米国のNIST、FIPSが検査方法を、ANS X9-82の中で公表しているものがあり、幾つかの方法について公認としている。

以上のような、確定的な計算などによる擬似乱数列に対し、(十分に[1])確率的な自然現象・物理現象から作られた乱数列を「真の乱数」「自然乱数」などという。非決定的という点を強調した Non-deterministic Random Bit Generator(NRBG)という語もある。この発生に用いられる代表的な自然現象は、原子の崩壊による放射線の輻射レベルや時間間隔、抵抗器の熱雑音などといったホワイトノイズやピンクノイズなどのノイズ、熱雑音などを原因とする半導体素子の遅れ時間のバラつき、光の屈折からの光子の分散などが多く使われている。先に出たFIPSでは、自然乱数の検定方法はいまだ検討中となっているが、いくつかの必要条件を示している。この必要条件としては、乱数発生源の健康状態が確認できること、発生源のエントロピーを確認できること、発生回路を自己検定できることなどがあるが、いまだドラフトの段階となっている。特記すべき点として、自然乱数はその発生源のエントロピーの低下に備え、疑似乱数との混合が望ましいとしていることがある。(これは望ましくない場合もある。コンピュータの応答などで遅滞が許されない場合は疑似乱数にフォールバックすべきだろうが、暗号等に使う場合などには絶対に真の乱数でなければならない場合がある)

近年、IoT他、セキュリティの高まりから、より良い乱数が暗号のために必要となり、従来はその実装が高価で一般に特殊用途でしか実用されていなかった自然乱数の需要が高まり、インテルといったCPUメーカーがそのCPUに組み込む例が多くなっている。

世界での自然乱数の発生器については英語版の記事が詳しい。

乱数列の種類

乱数列はそのとる値や分布によって分類される。

2進乱数

2進乱数とは01 (あるいは-1と1)がランダムに現れるような乱数である。ストリーム暗号スペクトラム拡散通信に用いられる。

一様乱数

一様乱数とはある有限の区間を区切って、その区間内で全ての実数が同じ確率(濃度)で現れるような乱数のことである。つまり連続一様分布に従う。

ある範囲の整数値を取る乱数列を発生させて、それを範囲の幅で割ることで [0,1](0以上1以下)や [0,1)(0以上1未満)の一様乱数に近いものが得られる。このようにして生成した一様乱数は原理的に有理数のみを含むため、任意の実数でありうる真の一様乱数ではない。コンピュータでは一般に浮動小数点数を扱い、真の実数を一般に扱うことは難しいため、真の一様乱数を扱うのは難しい。

整数の一様分布乱数

多くのプログラム言語では基本的な乱数として、0からある最大値までの整数に一様分布する乱数を発生させる関数が標準で用意されている。これを加工することで色々な分布の乱数を作り出すことができる。ただし、実装に使われているアルゴリズムによって周期やランダム性(すなわち乱数の"質")に違いがあり、たとえばC++11標準ライブラリに実装されているメルセンヌ・ツイスタエンジン(std::mt19937)は219937-1という非常に長い周期をもつが、C言語標準ライブラリのrand()関数やJavajava.util.Random [2]、および.NET Framework基本クラスライブラリのSystem.Random [3]など、実装が簡便だが下位桁の規則性や2次元以上での相関のある線形合同法が使われていることが多い。

正規乱数

正規乱数とは正規分布を持つような乱数である。正規乱数は工学においてはホワイトガウスノイズとして利用される。

平均μ、分散σ2 の正規分布N(μ, σ2)のような正規乱数を作る場合、まず(0,1]の一様乱数をボックス=ミュラー法(Box-Muller transform)で変換してN(0, 1)の正規乱数を得ることから始める。

一様乱数(0,1]の要素[math]\alpha[/math][math]\beta[/math]を次の変換を用いて変換する。

  • [math]\sqrt{-2\cdot\ln \alpha}\cdot\sin \left(2\pi \beta \right)[/math]
  • [math]\sqrt{-2\cdot\ln \alpha}\cdot\cos \left(2\pi \beta \right)[/math]

このようにして二つの相関のないN(0, 1)の正規乱数が得られる[4]。ただし[math]\ln[/math]自然対数

この正規乱数にσをかけて、さらにμを加えることで正規分布N(μ, σ2)の正規乱数が得られる。

またこれとは別に、簡単で擬似的な方法として、12個の一様乱数[0,1]の和から6を減ずる方法もよく用いられる[4]中心極限定理によって、独立した複数の一様乱数の和の分布は正規分布に近づく。さらに、12個の一様乱数[0,1]の和の分散は1となるため、6を減ずるだけで正規分布に近い確率分布が得られ、計算に都合がよい。

1990年代以降のパーソナルコンピュータ浮動小数点演算処理装置の内蔵によって三角関数や対数関数の演算が速くなっているため、1つの正規乱数あたり12回もの一様乱数生成を要するこの方法より、1つの正規乱数あたり1回の一様乱数生成で済むボックス=ミュラー法を用いた方が、一般的によく知られた多くの擬似乱数生成器との組み合わせにおいては高速である。

但し、非常に高速な擬似乱数生成器を用いるならば、中心極限定理を用いた手法はボックス=ミュラー法を用いるよりも十分に高速な正規乱数の生成が可能である。

ボードゲームテーブルトークRPGなどの遊戯において、複数個のサイコロの目の合計を使用している例がよく見られるが、これは中心極限定理によって正規乱数(の、ごくごく粗い近似)を生成し利用しているといえる。

乱数の生成法

擬似乱数でない乱数をコンピュータで利用するには、外部のエントロピーを入力するための専用ハードウェアなどを利用することになる。そのようなハードウェア乱数生成器を内蔵したCPUチップセットOSによってキーボードの打鍵タイミングなどから乱数が生成される擬似デバイスなどが存在する。このような乱数の生成法はコンピュータの歴史より古く、コンピュータが一般的に利用可能となるまでは「乱数賽」(1〜10の全ての数字が1/10の確率で現れるよう作られたサイコロ。3軸に対して対称の10面体は作れないので、正20面体の各面に2回ずつ番号を振ったものが通常使われる)や袋に入れた乱数カードを引き出すハイハット方式で生成していた。

脚注

  1. 量子力学的現象に比べれば、サイコロなどはかなり確定的だという主張もあるかもしれない。
  2. Random (Java Platform SE 8 )
  3. Random Class (System)
  4. 4.0 4.1 奥村(1991)、P133-134。

参考文献

関連記事