《一様乱数》のソースを表示

'''【いちようらんすう (uniform random numbers) 】'''

　確率変数の実現値と見なしうる数の列のことを[[乱数]] (または乱数列)(random numbersまたはrandom number sequence)という. 確率変数の従う分布として一様分布を想定する場合には, 対応する乱数のことを[[一様乱数]] (uniform random numbers)という. 例えば, サイコロを振って出る目(数)の系列は, 典型的な一様乱数である. この系列には次の2つの性質がある. 1) 系列が長ければ各数の相対出現頻度がほぼ等しい. 2) 次に出る数を確実に予測することは不可能である. 

　大量の乱数を使用する実験では, サイコロを振って乱数を作るのは現実的でないので, 簡単なアルゴリズムで生成される乱数もどきの数(擬似乱数)で代用するのがふつうである. そして, これを単に乱数と呼ぶことが多い. この意味での乱数は, 上記の2) の性質は持たないが, 1) の性質は近似的に満たしているものと考えられている. このような乱数の生成法は数多く提案されているが, 現在比較的よく使われているものを以下にあげる. 

［[[線形合同法]]］

　1948年頃にレーマー(Lehmer)によって提案され, その後多数の人々によって研究された方法であり, 線形漸化式


<center>
<math>
X_n=aX_{n-1}+c \ \ \ \ \ (\mbox{mod}\ \  m) \, 
</math>
</center>


を使って非負整数列<math>\{X_n\} \,</math>を生成する. ここで, <math>a \,</math>および<math>m \,</math>は正整数であり, <math>c \,</math>は非負整数である. 特に<math>c=0 \,</math>の場合には, [[乗算合同法]]と呼ぶ. パラメタの選び方に関しては多くの研究結果があるが, 現在比較的良いとされているものをいくつか表1に示す. 

<center>
<table border="1"> 
<caption> 表１：線形合同法で使われるパラメタの例 </caption>
<tr>
<td><math>a \,</math> </td> 
<td><math>c \,</math> </td> 
<td><math>m \,</math> </td> 
<td><math>X_0 \,</math> </td> 
<td><math>\mu_2 \,</math> </td>
<td><math>\mu_3 \,</math> </td> 
<td><math>\mu_4 \,</math> </td>
<td><math>\mu_5 \,</math> </td> 
<td><math>\mu_6 \,</math> </td> 
<td> 周期 </td>
</tr>
<tr>
<td><math>1\,664\,525 \,</math></td>
<td><math>* \,</math></td>
<td><math>2^{32} \,</math></td>
<td>任意 </td>
<td>16.1 </td>
<td>10.6 </td>
<td>8.0 </td>
<td>6.0 </td>
<td>5.0 </td>
<td><math>2^{32} \,</math></td>
</tr>
<tr>
<td><math>1\,566\,083\,941 \,</math> </td> 
<td>0 </td> 
<td><math>2^{32} \,</math> </td> 
<td>奇数 </td> 
<td>14.8 </td> 
<td>9.7 </td> 
<td>7.5 </td> 
<td>5.6 </td> 
<td>4.2 </td>
<td><math>2^{30} \,</math> </td>
</tr>
<tr>
<td><math>48\,828\,125 \,</math> </td> 
<td>0 </td> 
<td><math>2^{32} \,</math> </td> 
<td>奇数 </td> 
<td>14.8 </td> 
<td>8.8 </td> 
<td>7.4 </td> 
<td>5.7 </td> 
<td>4.9 </td>
<td><math>2^{30} \,</math> </td>
</tr>
<tr>
<td><math>2\,100\,005\,341 \,</math> </td> 
<td>0 </td> 
<td><math>2^{31}-1 \,</math> </td> 
<td>正整数 </td> 
<td>15.4 </td> 
<td>10.2 </td> 
<td>7.7 </td> 
<td>6.0 </td> 
<td>5.0 </td>
<td><math>2^{31}-2 \,</math> </td>
</tr>
<tr>
<td><math>397\,204\,094 \,</math> </td> 
<td>0 </td> 
<td><math>2^{31}-1 \,</math> </td> 
<td>正整数 </td> 
<td>14.8 </td> 
<td>9.7 </td> 
<td>7.4 </td> 
<td>6.0 </td> 
<td>5.0 </td>
<td><math>2^{31}-2 \,</math> </td>
</tr>
<tr>
<td><math>314\,159\,369 \,</math> </td> 
<td>0 </td> 
<td><math>2^{31}-1 \,</math> </td> 
<td>正整数 </td> 
<td>15.2 </td> 
<td>9.9 </td> 
<td>7.6 </td> 
<td>5.9 </td> 
<td>5.1 </td>
<td><math>2^{31}-2 \,</math> </td>
</tr>
</table>
<math>c \,</math>の列の <math>* \,</math>印は, 任意の奇数を使用してよいことを表す.
</center>


　線形合同法によって生成される乱数の欠点として, 多次元疎結晶構造と言われているものがある. これは, <math>k \,</math>次元超立方体内にランダムに点を配置する目的で, 点の座標を<math>(x_n, x_{n+1},\cdots, x_{n+k-1}), n=1,2,\cdots, \,</math>で定めたとすると, これらの点はすべて比較的少数の等間隔に並んだ超平面の上に規則的にのってしまい, ランダムにならないという性質である. <math>m \,</math>と超平面の枚数の上界との関係を表2に示す. また, 表1の<math>\mu_k \,</math>は, <math>k \,</math>次元の点配置を作ったとき, <math>\mu_k \,</math>ビットの精度ではほぼ一様な配置になることを意味している. 


<center>
<table border="1">
<caption> 表２：超平面の枚数の上界 </caption>
<tr>
<td><math>m \,</math> </td> 
<td><math>k=3 \,</math> </td> 
<td> 4 </td> 
<td> 5 </td> 
<td> 6 </td>
<td> 7 </td> 
<td> 8 </td> 
<td> 9 </td> 
<td> 10 </td>
</tr>
<tr>
<td><math>2^{24} \,</math> </td> 
<td>465 </td> 
<td>141 </td> 
<td>72 </td> 
<td>47 </td> 
<td>36 </td> 
<td>30 </td> 
<td>26 </td> 
<td>23 </td>
</tr>
<tr>
<td><math>2^{32} \,</math> </td> 
<td><math>2\,953 \,</math> </td> 
<td>566 </td> 
<td>220 </td> 
<td>120 </td> 
<td>80 </td> 
<td>60 </td> 
<td>48 </td> 
<td>41 </td>
</tr>
<tr>
<td><math>2^{36} \,</math> </td> 
<td><math>7442 \,</math> </td> 
<td><math>1133 \,</math> </td> 
<td>383 </td> 
<td>191 </td> 
<td>119 </td> 
<td>85 </td> 
<td>66 </td> 
<td>54 </td>
</tr>
<tr>
<td><math>2^{48} \,</math> </td> 
<td><math>119086 \,</math> </td> 
<td><math>9065 \,</math> </td> 
<td><math>2021 \,</math> </td> 
<td>766 </td> 
<td>391 </td> 
<td>240 </td> 
<td>167 </td> 
<td>126 </td>
</tr>
</table>
</center>


［[[M系列法]]］

　ガロア体GF(2)上の任意の原始多項式


<center>
<math>
x^p+c_1x^{p-1}+c_2x^{p-2}+\cdots + c_p
</math>
</center>


を選び, その係数を係数とする漸化式


<center>
<math>
a_n = c_1a_{n-1}+c_2a_{n-2}+\cdots + c_pa_{n-p}
\ \ \ \ \ (\mbox{mod}\ \  2)
</math>
</center>


によって生成される系列<math>\{a_n\} \,</math>を考える. この系列はM系列(M-sequence)あるいはシフトレジスタ系列, 極大多項式系列などと呼ばれ, 硬貨を投げて表が出れ


ば1, 裏が出れば0として得られる系列と類似の性質を持つことが知られている. 表3に実用的な原始多項式の例を示す. 


<center>
<table> 
<caption> 表３：原始多項式の例 </caption>
<tr><td><hr></td></tr>
<tr><td align="left"><math>x^{521}+x^{32}+1 \,</math></td></tr>
<tr><td align="left"><math>x^{607}+x^{273}+1 \,</math></td></tr>
<tr><td align="left"><math>x^{1279}+x^{418}+1 \,</math></td></tr>
<tr><td align="left"><math>x^{521}+x^{455}+x^{437}+x^{350}+1 \,</math></td></tr>
<tr><td align="left"><math>x^{607}+x^{461}+x^{307}+x^{167}+1 \,</math></td></tr>
<tr><td><hr></td></tr>
</table>
</center>



　これは1ビットの系列なので, 多数ビットの系列<math>\{X_n\} \,</math>を作るためには, 漸化式


<center>
<math>
X_n = c_1X_{n-1} \oplus c_2X_{n-2} \oplus \cdots \oplus c_pX_{n-p}
</math>
</center>


を用いる. ここで, 記号<math>\oplus \,</math>は2進法でのけた上りなしの足し算(ビットごとの排他的論理和)を表す. これによって生成される系列は, トーズワース(Tausworthe)系列あるいはGFSR(Generalized Feedback Shift Register)系列と呼ばれている. 

　この漸化式を使う場合の初期値の設定法については, [1] を参照するとよい. これを使って例えば32ビットの整数系列<math>\{X_n\} \,</math>を生成すると, 合同法のような多次元疎結晶構造が生じることはなく, 32ビットの精度で<math>[p/32] \,</math>次元まで一様に分布する. また, この系列の周期は<math>2^p-1 \,</math>であり, 自己相関関数の値は位相差が<math>2^p/32 \,</math>以下ならばほぼ0に等しい. 

　M系列を使ったもう少し複雑な乱数生成法として, 最近提案されたメルセンヌ・ツイスター(Mersenne Twister) [3] がある. これは上記のものに比べて, 同じ記憶容量で, はるかに長い周期と高い次元の一様性を達成できるという特徴を有する. 詳細は

http://www.math.keio.ac.jp//~matumoto/mt.html

を参照するとよい. 




----
'''参考文献'''

[1] 伏見正則, 『乱数』(UP応用数学選書12), 東京大学出版会, 1989. 

[2] D. E. Knuth, ''The Art of Computer Programming, Vol.2: Seminumerical Algorithms, 2nd ed.,'' Addison-Wesley, 1981. 渋谷政昭訳, 『準数値算法/乱数』, サイエンス社, 1981.

[3] M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator," ''ACM Transactions on Modeling and Computer Simulation'', '''8''' (1998), 3-30.