乱数列のソースを表示

'''乱数列'''（らんすうれつ）とは[[ランダム]]な[[数列]]のこと。
[[数学]]的に述べれば、今得られている数列 <math>x_1, x_2, \dots , x_n</math> から次の数列の値 <math>x_{n + 1}</math> が予測できない数列。乱数列の各要素を'''乱数'''（らんすう）という。もう少し具体的には、[[漸化式]]や[[関数 (数学)|関数]]で定義できない[[数列]]を構成する数を乱数ということもできる。

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

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

近年、[[モノのインターネット|IoT]]他、セキュリティの程度を高める要求から、暗号のためにより良い乱数が必要とされ、従来はその実装が高価で一般に<!--軍（自衛隊を含む）--><!--軍を例に出してるのは暗号を考えてるのかもしれませんが、暗号だけじゃなくて統計などで科学的に必要な（高いカネを出してくれる）所は普通にあったはず-->特殊な用途でしか実用化されていなかった自然乱数に対する需要が高まり、たとえば[[CPU]]メーカーであるインテルがCPU内部に機能として組み込む例もでている。

世界での自然乱数の発生器については[[:en:Hardware random number generator|英語版の記事]]が詳しい。

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

=== 離散一様分布（整数の一様分布乱数） ===
多くの[[プログラム言語]]では、0からある最大値までの整数に一様分布する乱数を発生させる関数が標準で用意されている。これを基にして加工することにより様々な分布を持つ乱数を作ることができる。ただし、実装に使われているアルゴリズムによって周期やランダム性（すなわち乱数の"質"）には違いがあり、たとえば[[C++11]]標準ライブラリに実装されている[[メルセンヌ・ツイスタ]]エンジン（<code>std::mt19937</code>）は2<sup>19937</sup>-1（24番目の[[メルセンヌ素数]]、約4.315×10<sup>6001</sup>）という非常に長い周期をもつが、[[C言語]]標準ライブラリの<code>[[rand]]()</code>関数や[[Java]]の<code>java.util.Random</code> <ref>[https://docs.oracle.com/javase/jp/8/api/java/util/Random.html Random (Java Platform SE 8 )]</ref>、および[[.NET Framework]]基本クラスライブラリの<code>System.Random</code> <ref>[https://msdn.microsoft.com/en-us/library/system.random.aspx Random Class (System)]</ref>などのように、実装は簡便であるが下位の桁が規則性を持っていたり、2次元以上では分布に相関が生じる[[線形合同法]]が使われていることが多い。

=== 連続一様分布（一様乱数） ===
{{Anchors|一様乱数}}一様乱数<!-- リンク元: [[ハードウェア乱数生成器]] 2020年5月29日設置 -->とはある有限の区間を区切って、その区間内で全ての実数が同じ確率（[[濃度 (数学)|濃度]]）で現れるような[[連続一様分布]]に従う乱数のことである。

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

=== ベルヌーイ分布（2進乱数） ===
2進乱数とは[[0]]と[[1]]（あるいは[[-1]]と1）がランダムに現れるような[[ベルヌーイ分布]]に従う乱数である。[[ストリーム暗号]]や[[スペクトラム拡散]][[通信]]に用いられる。<!--コンピュータでは、複数ビットの乱数を生成するような関数から1ビット単位で切り出して生成する。--><!-- ← M系列とかは本質的にビット列ですのでこの説明は変 MetaNest -->
<!--
=== 自然乱数 ===
自然乱数とは[[自然数]]がランダムに現れるような乱数である。0を含むことが多い。0以上無限大までの全ての自然数を用いた自然乱数が考えられるが、実際上は最大の自然数を決めて、それ以下の範囲で考えることが多い。


--><!-- ← この節はあれこれ変。検索する限り、この記事の引用以外は、自然乱数=真の乱数ないし物理乱数の別名じゃないかという感じだが MetaNest -->

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

手法として、以下の方法などがある。[[GNU Scientific Library]] のドキュメントによるとほとんどの場合ジッグラト法が最速である<ref>[https://www.gnu.org/software/gsl/manual/html_node/The-Gaussian-Distribution.html GNU Scientific Library – Reference Manual: The Gaussian Distribution]</ref>。
* [[逆関数法|逆関数サンプリング法]]
* [[ボックス＝ミュラー法]]
*{{仮リンク|ジッグラト法|en|ziggurat algorithm}}
*{{仮リンク|マルサグリア法|en|Marsaglia polar method}}

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

一様乱数 <math>(0, 1]</math> の要素 <math>\alpha</math> と <math>\beta</math> を次の変換を用いて変換する。
*<math>\sqrt{-2\cdot\ln \alpha}\cdot\sin \left(2\pi \beta \right)</math>
*<math>\sqrt{-2\cdot\ln \alpha}\cdot\cos \left(2\pi \beta \right)</math>
このようにして2つの相関のない <math>N(0, 1)</math> の正規乱数が得られる<ref name="正規分布">[[#algo|奥村（1991）]]、P133-134。</ref>。ただし <math>\ln</math> は[[自然対数]]。

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

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

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

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

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

=== その他一般の確率分布 ===
各種サンプリング法を使用する。手法ごとに計算量や棄却率など様々な特徴がある。

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

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

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

== 脚注 ==
{{脚注ヘルプ}}
{{reflist}}

== 参考文献 ==
* 脇本和昌：「乱数の知識」、森北出版(初等情報処理講座5）、{{ISBN2|978-4-62703350-4}} (1970年8月)。
* D. E. Knuth：「準数値算法：乱数」、サイエンス社、ISBN 978-4-7819-0304-0 (1981年10月1日)。
* 伏見正則：「乱数」、東京大学出版会、ISBN 978-4130640725 (1989年3月)。
*{{cite book | 1=和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 |isbn=4-87408-414-1|ref=algo}}
* 宮武修、脇本和昌：「乱数とモンテカルロ法 POD版」、森北出版、ISBN 978-4-62700479-5 (2007年5月30日)。
* 四辻哲章：「計算機シミュレーションのための確率分布乱数生成法」、プレアデス出版、ISBN 978-4-903814-35-3（2010年6月1日）。※ 様々な確率分布を持った乱数列の生成方法を紹介している。
* 杉田洋：「確率と乱数」、数学書房、ISBN 978-4-90334224-5（2014年7月11日）。
* 伏見正則 (監訳)、逆瀬川浩孝 (監訳)：「モンテカルロ法ハンドブック」、朝倉書店、ISBN 978-4-254-28005-0（2014年10月31日）。
* 小柴健史：「乱数生成と計算量理論」、岩波書店、ISBN 978-4-00-006975-5 (2014年11月28日)。
* Donald E. Knuth：「The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition 日本語版」、KADOKAWA、ISBN 978-4-04869416-2（2015年7月24日）。※第3章「乱数」。
* 藤井光昭：「暗号と乱数：乱数の統計的検定」、共立出版、ISBN 978-4-320-11258-2 (2018年4月7日)。
* 﨑山一男、菅原健、李陽：「暗号ハードウェアのセキュリティ」、コロナ社、ISBN 978-4-33902894-2（2019年5月23日）。
* 手塚集：「確率的シミュレーションの基礎」、近代科学社、ISBN 978-4-7649-0557-3 (2018年1月31日)。※ シミュレーションに用いる乱数列、特に高次元での一様分布に詳しい。
* [https://www.asahi.com/articles/ASN2G4SH8N25ULBJ008.html 「でたらめ」作りを研究者たちが競う　奥深い乱数の世界 朝日新聞記事2020年2月18日）]。
* 現場へ！「乱数の世界へようこそ」（朝日新聞連載記事全5回）
**[https://www.asahi.com/articles/ASN614CMJN5NULBJ001.html 第1回：奥深き「でたらめ」の世界　秘密通信研究から転じた職人（2020年6月2日）]。
**[https://www.asahi.com/articles/ASN614CPTN5NULBJ009.html 第2回：数学界の「異世界転生」　スーパー乱数に魅せられた職人（2020年6月3日）]。
**[https://www.asahi.com/articles/ASN614CR3N5TULBJ003.html 第3回：「地上の太陽」作るシミュレーション　でたらめが支える（2020年6月4日）]。
**[https://www.asahi.com/articles/ASN614CXCN5TULBJ002.html 第4回：スパイ対策の跡　あのプロ野球投手も使った暗号と乱数表（2020年6月5日）]。
**[https://www.asahi.com/articles/ASN614CY9N5TULBJ001.html 第5回：メイド・イン・ジャパン　世界に先駆けたランダムの極意（2020年6月6日）]。
* [https://doi.org/10.11540/jsiamt.30.4_320 鈴木航介、合田隆：「サーベイ 準モンテカルロ法の最前線」、日本応用数理学会論文誌、2020年、30巻、4号、p.320-374]
* 伏見正則：「乱数」、筑摩書房（ちくま学芸文庫）、{{ISBN2|978-4-48051214-7}} (2023年10月10日). 東京大学出版会1981年版に若干の修正を加えた文庫版。
* 鈴木航介、合田隆：「重点解説 モンテカルロ法と準モンテカルロ法」、サイエンス社（SGCライブラリ197）、ISBN 978-4-7819-1623-1 (2025年1月25日)。

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

{{Normdaten}}
{{DEFAULTSORT:らんすうれつ}}
[[Category:乱数|*]]
[[Category:数学に関する記事]]