「乱数列」の版間の差分

削除された内容追加された内容

インライン

2020年11月20日 (金) 08:03時点における版

乱数列（らんすうれつ）とはランダムな数列のこと。数学的に述べれば、今得られている数列 x₁, x₂, ..., x_n から次の数列の値 x_n+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内部に機能として組み込む例もでている。

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

乱数列の種類

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

離散一様分布（整数の一様分布乱数）

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

連続一様分布（一様乱数）

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

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

ベルヌーイ分布（2進乱数）

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

正規分布（正規乱数）

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

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

ボックス＝ミュラー法

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

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

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

${\sqrt {-2\cdot \ln \alpha }}\cdot \sin \left(2\pi \beta \right)$
${\sqrt {-2\cdot \ln \alpha }}\cdot \cos \left(2\pi \beta \right)$

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

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

中心極限定理を用いた手法

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

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

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

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

その他一般の確率分布

逆関数サンプリング法やマルコフ連鎖モンテカルロ法などの各種サンプリング法を使用する。

乱数の生成法

「ハードウェア乱数生成器」も参照

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

脚注

[脚注の使い方]

^ 量子力学的現象に比べると、サイコロなどはかなり確定的であるという主張もあるかもしれない。
^ Random (Java Platform SE 8 )
^ Random Class (System)
^ GNU Scientific Library – Reference Manual: The Gaussian Distribution
^ ^a ^b 奥村（1991）、P133-134。

参考文献

伏見正則：「乱数」、東京大学出版会、ISBN 978-4130640725 (1989年3月)。
奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年。ISBN 4-87408-414-1。
宮武修、脇本和昌：「乱数とモンテカルロ法 POD版」、森北出版、ISBN 978-4627004795 (2007年5月30日)。
四辻哲章：「計算機シミュレーションのための確率分布乱数生成法」、プレアデス出版、ISBN 978-4903814353（2010年6月1日）。
伏見正則 (監訳)、逆瀬川浩孝 (監訳)：「モンテカルロ法ハンドブック」、朝倉書店、ISBN 978-4254280050（2014年10月31日）。
小柴健史：「乱数生成と計算量理論」、岩波書店、ISBN 978-4000069755 (2014年11月28日)。
Donald E.Knuth：「The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition 日本語版」、KADOKAWA、ISBN 978-4048694162（2015年7月24日）。※第3章「乱数」。
藤井光昭：「暗号と乱数: 乱数の統計的検定」、共立出版、ISBN 978-4320112582 (2018年4月7日)。
﨑山一男、菅原健、李陽：「暗号ハードウェアのセキュリティ」、コロナ社、ISBN 978-4339028942（2019年5月23日）。
「でたらめ」作りを研究者たちが競う　奥深い乱数の世界朝日新聞記事2020年2月18日）。
現場へ！「乱数の世界へようこそ」（朝日新聞連載記事全5回）

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