乱数列

乱数列とはランダムな数列のこと。数学的に述べれば、今得られている数列 から次の数列の値 が予測できない数列。乱数列の各要素を乱数という。もう少し具体的には、漸化式や関数で定義できない数列を構成する数を乱数ということもできる。

1. 擬似乱数列と真の乱数列
--------------

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

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

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

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

2. 乱数列の種類
---------

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

2.1. 離散一様分布
-----------

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

2.2. 連続一様分布
-----------

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

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

2.3. ベルヌーイ分布
------------

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

2.4. 正規分布
---------

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

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

逆関数サンプリング法
ボックス＝ミュラー法

2.4.1. ボックス＝ミュラー法
-----------------

平均 、分散 の正規分布 のような正規乱数を作る場合、まず の一様乱数をボックス＝ミュラー法で変換して の正規乱数を得ることから始める。

一様乱数 の要素 と を次の変換を用いて変換する。

このようにして2つの相関のない の正規乱数が得られる。ただし は自然対数。

この正規乱数に をかけて、さらに を加えることで正規分布 の正規乱数が得られる。

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

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

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

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

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

2.5. その他一般の確率分布
---------------

各種サンプリング法を使用する。手法ごとに計算量や棄却率など様々な特徴がある。

逆関数サンプリング法
棄却サンプリング
マルコフ連鎖モンテカルロ法
メトロポリス・ヘイスティングス法
ハミルトニアン・モンテカルロ法
ランジュバン・モンテカルロ法

3. 生成法
------

擬似乱数列でない乱数列をコンピュータで利用するには、外部のエントロピーを入力するための専用ハードウェアなどを利用することになる。そのようなハードウェア乱数生成器を内蔵したCPUやチップセット、OSによってキーボードの打鍵タイミングなどから乱数が生成される擬似デバイスなどが存在する。このような乱数の生成法はコンピュータの歴史より古く、コンピュータが一般的に利用可能となるまでは「乱数賽」や袋に入れた乱数カードを引き出すハイハット方式で生成していた。

擬似乱数列の生成は、理論的にはコンピュータ以前から手計算でも可能ではあったが、実際的にはコンピュータ以後に発展した。代表的な生成法に二乗中抜き法や線形合同法、線形帰還シフトレジスタやXorshift、メルセンヌ・ツイスタがある。これらはいずれも暗号論的に安全ではない。暗号論的に安全な擬似乱数については暗号論的擬似乱数生成器を参照。

4. 脚注
-----

5. 参考文献
-------

伏見正則：「乱数」、東京大学出版会、ISBN 978-4130640725 。
宮武修、脇本和昌：「乱数とモンテカルロ法 POD版」、森北出版、ISBN 978-4627004795 。
四辻哲章：「計算機シミュレーションのための確率分布乱数生成法」、プレアデス出版、ISBN 978-4903814353。
杉田洋：「確率と乱数」、数学書房、ISBN 978-4903342245。
伏見正則 、逆瀬川浩孝 ：「モンテカルロ法ハンドブック」、朝倉書店、ISBN 978-4254280050。
小柴健史：「乱数生成と計算量理論」、岩波書店、ISBN 978-4000069755 。
Donald E.Knuth：「The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition 日本語版」、KADOKAWA、ISBN 978-4048694162。※第3章「乱数」。
藤井光昭：「暗号と乱数: 乱数の統計的検定」、共立出版、ISBN 978-4320112582 。
﨑山一男、菅原健、李陽：「暗号ハードウェアのセキュリティ」、 コロナ社、ISBN 978-4339028942。
[https://www.asahi.com/articles/ASN2G4SH8N25ULBJ008.html 「でたらめ」作りを研究者たちが競う　奥深い乱数の世界 朝日新聞記事2020年2月18日）