乱数列
出典: Wikipedio
|
乱数列(らんすうれつ)とはランダムな数列のこと。 数学的に述べれば、今得られている数列 x1, x2, ..., xn から次の数列の値 xn+1 が予測できない数列。乱数列の各要素を乱数という。
目次 |
概要
乱数は、実験計画やシミュレーションで利用されるほか、秘密鍵の生成など暗号でも利用される。
乱数の種類
乱数はそのとる値や分布によって分類される。
2進乱数
2進乱数とは0と1 (あるいは-1と1)がランダムに現れるような乱数である。ストリーム暗号やスペクトラム拡散通信に用いられる。コンピュータでは、複数ビットの乱数を生成するような関数から1ビット単位で切り出して生成する。
自然乱数
自然乱数とは自然数がランダムに現れるような乱数である。0を含むことが多い。0以上無限大までの全ての自然数を用いた自然乱数が考えられるが、実際上は最大の自然数を決めて、それ以下の範囲で考えることが多い。
コンピュータでは最大値を持つ自然乱数を発生させる関数(rand()やメルセンヌ・ツイスタなど)が用意されている。これを加工することで色々な乱数を作り出すことができる。
一様乱数
一様乱数とはある有限の区間を区切って、その区間内で全ての実数が同じ確率(濃度)で現れるような乱数のことである。
コンピュータでは最大値を持つ自然乱数列を発生させて、それを最大値で割ることで[0,1](0以上1以下)の一様乱数が得られる。また、(最大値+1)で割ることで[0,1)(0以上1未満)の一様乱数が得られる。このようにして生成した一様乱数は原理的に有理数のみで無理数は含まれないため、これは真の一様乱数ではない。デジタルコンピュータの性質上、無理数を扱うことはできない。
[a,b](a以上b以下)の区間の一様乱数が必要な場合は、[0,1]の乱数列を用意して、これに(b-a)をかけて、さらにaを加えることで得られる。
[a,b)(a以上b未満)が必要な場合は同様にして[0,1)を利用する。
正規乱数
正規乱数とは正規分布を持つような乱数である。正規乱数は工学においてはホワイトガウスノイズとして利用される。
平均μ、分散σ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 (2\pi \beta)</math>
- <math>\sqrt{-2\cdot\ln \alpha}\cdot\cos (2\pi \beta)</math>
このようにして二つの相関のないN(0, 1)の正規乱数が得られる。ただし<math>\ln</math>は自然対数。
この正規乱数にσをかけて、さらにμを加えることで正規分布N(μ, σ2)の正規乱数が得られる。
またこれとは別に、簡単で擬似的な方法として、12個の一様乱数[0,1]の和から6を減ずる方法もよく用いられる。中心極限定理によって、独立した複数の一様乱数の和の分布は正規分布に近づく。さらに、12個の一様乱数[0,1]の和の分散は1となるため、6を減ずるだけで正規分布に近い確率分布が得られ、計算に都合がよい。
近年のパーソナルコンピュータはプロセッサの進歩によって三角関数や対数関数の演算が速くなっているため、1つの正規乱数あたり12回もの一様乱数生成を要するこの方法より、1つの正規乱数あたり1回の一様乱数生成で済むボックス=ミューラー法を用いた方が、一般的によく知られた多くの擬似乱数生成器との組み合わせにおいては高速である。
但し、xorshiftの様に非常に高速な擬似乱数生成器を用いるならば、中心極限定理を用いた手法はボックス=ミュラー法を用いるよりも十分に高速な正規乱数の生成が可能である。
ボードゲームやテーブルトークRPGなどの遊戯において、複数のサイコロの目の和を条件として分岐するイベントがよくあるが、これは中心極限定理による疑似的な正規乱数を生成し、その分布を利用しているといえる。
乱数の生成法
コンピュータは有限オートマトンとみなせるので、外部からの入力がない限り計算によって求める確定的な擬似乱数しか生成できない。外部のエントロピを入力するための専用ハードウェアで生成した非確定的な乱数を利用することになる。そのようなハードウェア乱数生成器を内蔵したCPUやチップセットも存在する。コンピュータがなかった当時は「乱数賽」(1~10の全ての数字が1/10の確率で表われるよう作られたサイコロ)や袋に入れた乱数カードを引き出すハイハット方式で生成していた。
関連記事
- ランダム
- カイ二乗検定
- コルモゴロフ複雑性
- 擬似乱数(線形合同法、メルセンヌ・ツイスタ)
- モンテカルロ法
- 逐次モンテカルロ法
- 乱択アルゴリズム - ラスベガス法
- 次元の呪い
- マルコフ連鎖
- MCMCca:Nombre_aleatori
de:Zufallszahl en:Random_number es:Número_aleatorio fi:Satunnaisluku he:מספרים_אקראיים pt:Número_aleatório zh:随机数