乱数列

乱数列（らんすうれつ）とはランダムな数列のこと。 数学的に述べれば、今得られている数列 ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ から次の数列の値 ${\displaystyle 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（24番目のメルセンヌ素数、約4.315×10⁶⁰⁰¹）という非常に長い周期をもつが、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]。

• 逆関数サンプリング法
• ボックス＝ミュラー法
• ジッグラト法（英語版）
• マルサグリア法（英語版）

ボックス＝ミュラー法[編集]

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

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

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

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

この正規乱数に ${\displaystyle \sigma }$ をかけて、さらに ${\displaystyle \mu }$ を加えることで正規分布 ${\displaystyle N(\mu ,\sigma ^{2})}$ の正規乱数が得られる。

中心極限定理を用いた手法[編集]

またこれとは別に、簡単で擬似的な方法として、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つずつ振ったものが通常使われる）や袋に入れた乱数カードを引き出すハイハット方式で生成していた。

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

脚注[編集]

参考文献[編集]

• 伏見正則：「乱数」、東京大学出版会、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-4903342245（2014年7月11日）。
• 伏見正則 (監訳)、逆瀬川浩孝 (監訳)：「モンテカルロ法ハンドブック」、朝倉書店、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回）
  • 第1回：奥深き「でたらめ」の世界　秘密通信研究から転じた職人（2020年6月2日）。
  • 第2回：数学界の「異世界転生」　スーパー乱数に魅せられた職人（2020年6月3日）。
  • 第3回：「地上の太陽」作るシミュレーション　でたらめが支える（2020年6月4日）。
  • 第4回：スパイ対策の跡　あのプロ野球投手も使った暗号と乱数表（2020年6月5日）。
  • 第5回：メイド・イン・ジャパン　世界に先駆けたランダムの極意（2020年6月6日）。

関連記事[編集]

• ランダム
• カイ二乗検定
• コルモゴロフ複雑性
• 擬似乱数
• モンテカルロ法
• 逐次モンテカルロ法
• 乱択アルゴリズム - ラスベガス法
• 次元の呪い
• マルコフ連鎖
• MCMC