乱数列
[Wikipedia|▼Menu]

乱数列(らんすうれつ)とはランダム数列のこと。数学的に述べれば、今得られている数列 x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\dots ,x_{n}} から次の数列の値 x n + 1 {\displaystyle x_{n+1}} が予測できない数列。乱数列の各要素を乱数(らんすう)という。もう少し具体的には、漸化式関数で定義できない数列を構成する数を乱数ということもできる。
擬似乱数列と真の乱数列

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

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

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

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

乱数列はそのとる値や確率分布によって分類される。
離散一様分布(整数の一様分布乱数)

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

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

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

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

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

手法として、以下の方法などがある。GNU Scientific Library のドキュメントによるとほとんどの場合ジッグラト法が最速である[4]

逆関数サンプリング法

ボックス=ミュラー法

ジッグラト法(英語版)

マルサグリア法(英語版)

ボックス=ミュラー法詳細は「ボックス=ミュラー法」を参照

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


次ページ
記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:23 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:undef