5.5 制限事項
5.5.3 DRWS: メモリの使用量の管理
random samplerは一組の (xl, αl)を生成するために 160 bit= 20 byte のメモリ領域を 使用する．54たとえば前節のサンプルプログラムではlocmax = 37を最後に出力するが，
これはこのプログラムが37×20= 740 byteのメモリ領域を使ったことを意味する．最近 の計算機は十分なメモリを有しているから，普通は問題にならない．しかし，大規模な計 算，つまりWが非常に多くのZlたちを必要とする確率が無視できないとき，DRWSはメ モリ領域を使い果たすかも知れない．そのため，現在，DRWSがどのくらいのメモリを使 用中であるかをget locmaxを呼び出して常にチェックすることを心がけるのがよい．さ らに実際的な解決法は，set locmaxmaxで上限を設定しておくことである．そうすれば，
lがその上限を超えたとき，i.i.d.-サンプリングにスイッチする．
54unsigned long型が32 bit=4byteの場合．
おわりに
晩年のコルモゴロフはパーキンソン氏病という難病を患いながらも，「ランダムとは何 か」という問題に没頭したという([30] p.115)．§1.3で述べたとおり，乱数の問題はモン テカルロ法の本質的な困難である．しかしながら，モンテカルロ法を扱った論文や単行本 に，コルモゴロフの乱数が正面から扱われている例を筆者は知らない．クヌースの本[13]
のpp.165-166に紹介はあるが内容についてはまともな記述がない．数学辞典第三版には
「420乱数」という項目で内容について少し扱われてくらいである．しかし，最近出版さ れた数学辞典第四版[18]にはコルモゴロフの乱数の記述はなくなってしまった．もちろ ん，マルティン=レーフの論文[15]は見当たらない．残念な事態である．
暗号理論における疑似乱数の考え方はインターネットサーフィン中に知った．目から鱗 が落ちる思いだった．現代の計算機科学の重要な課題はすべて確率が絡んでるといって過 言でない．困難な問題に対して小さな確率的リスクを覚悟した上で実行可能な労力の範囲 で解決を図るのが，現代計算機科学の研究の主流だという．このような意識でモンテカル ロ法を眺めるとき，それはすぐれて計算機科学の問題であるように見えてくる．
計算機科学の分野で確率論が使われているといっても，代数的あるいは組み合わせ論的 な事実を確率論的に解釈して応用する，という方針が多用されている．たとえば，§1.5.2 定理1では有限体上の連立一次方程式の解の存在と一意性を確率論の独立性と解釈する という具合だ．しかし，数値解析の分野では代数的アイデアはあまりうまく働かない．実 際，定理1の証明で示した疑似乱数生成器が実用化された，という話は聞かない．計算機 科学においても理論上の道具にすぎないようだ．それはたとえばGF(2128)の四則計算の実 体はF2-係数の127次多項式の四則計算であり，とても大変だからである．素体Fpだと四 則計算は楽だから，2128< pなる素数をとってFp-値のペアごとに独立で一様分布する確 率変数列を構成するのがよいかもしれない([10])．しかし，それとてそのような素数 pを 探すのは容易ではない．55それならいっそ，解析学的に容易に得られる§4.2.3定理18を 離散化したRWSが実際の計算には数段便利である．もはや素数に縛られることはない．
この例でも分かるように，代数的に構成された工夫は数学的には単純で美しく最適解で あることが多いが，一方，パラメータを少し変化させるとたちまち成り立たなくなる．p が素数であってもp+1は素数でないから，同じ工夫はp+1では成り立たないのである．
現在流行の楕円曲線を用いた暗号理論でも，楕円曲線を定義するパラメータの特殊な選び 方が重要な問題になっている．単に大きな整数をとればよい，という類のものではない．
解析学では，数の個性(素数であることなど)に注目しないので最適解を得られないか も知れないが，パラメータの変動に伴い単調に変化する現象に注目する．たとえば§3.2.2 定理10はm → ∞に伴ってワイル変換による疑似乱数生成器がある次ビット予測が指数 関数的に困難になることを示している． 筆者は，計算機科学の諸問題に，解析学，とく に確率論の手法が生かされる場がたくさんあるのではないか，と期待している．
55Mathematicaでの計算によれば2128<pなる最小の素数pは2128+51である．
参考文献
[1] 秋根善孝，従属性消滅定理に関する収束速度の精密評価，九州大学大学院数理学研究院修士 論文，(2002)．
[2] P. Billingsley, Probability and measure, 3rd edition, John Wiley & Sons, (1995).
[3] L. Blum, M. Blum and M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput., 15-2 (1986), 364–383.
[4] M. Blum and S. Macali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. on Computing, vol. 13, (1984) 850–864. A preliminary version appears in Proceedings of the IEEE Foundations of Comput. Sci. (1982), 112–117.
[5] G.J. Chaitin, Algorithmic information theory, IBM J. Res. Develop., 21 (1977), 350–359.
[6] S. Heinrich, E. Novak, and H. Pfeiffer, How many random bits do we need for Monte Carlo inte-gration? Monte Carlo and quasi-Monte Carlo methods 2002, Springer, Berlin (2004), 27–49.
[7] S. Janson, Some pairwise independent sequences for which the central limit theorem fails, Stochas-tics 23-4 (1988), 439–448.
[8] JIS Z 9031乱数発生及びランダム化の手順，日本規格協会，2001年改正．
[9] A. Joffe, On a sequence of almost deterministic pairwise independent random variables, Proc. Amer.
Math. Soc. 29 (1971), 381–382.
[10] A. Joffe, On a set of almost deterministic k-independent random variables Ann. Probability 2-1 (1974), 161–162.
[11] 笠井琢美，計算量の理論，近代科学社，(1987).
[12] A.N. Kolmogorov, Logical basis for information theory and probability theory, IEEE Trans. on Inform. Theo., vol.IT-14-5, Sept. (1968), 662–664.
[13] D.E. Knuth, The Art of Computer Programming, 2nd ed., Addison-Wesley, (1981), (邦訳)準数値 算法/乱数(渋谷政昭訳)，サイエンス社，(1983)
[14] M. Luby, Pseudorandmness and cryptographic applications, Princeton Computer Science Notes, Princeton University Press, (1996).
[15] P. Martin-L¨of, The definition of random sequences, Inform. Control, 7 (1966), 602–619.
[16] J. von Neumann, Various techniques used in connection with random digits, U.S. Natl. Bur. Stand.
Appl. Math. Ser., 12 (1951), 36–38.
[17] D.R. Stinson, Cryptography (Theory and practice), CRC Press, (1995).
[18] 数学辞典(第4版)，484 (XX-9) “乱数とモンテカルロ法”，岩波書店，(2007), 1589–1591． [19] H. Sugita, Pseudo-random number generator by means of irrational rotation, Monte Carlo Methods
and Applications, VSP, 1-1 (1995), 35–57.
[20] H. Sugita, Robust numerical integration and pairwise independent random variables, Jour. Comput.
Appl. Math., 139 (2002), 1–8.
[21] H. Sugita, Dynamic random Weyl sampling for drastic reduction of randomness in Monte Carlo integration, Math. Comput. Simulation, 62 (2003), 529–537.
[22] 杉田洋，複雑な関数の数値積分とランダムサンプリング，「数学」岩波書店56-1, (2004) 1–17.
[23] H. Sugita, An analytic approach to secure pseudo-random generation, Proceedings of 2003 Rit-sumeikan Symposium on Stochastic Processes and its Applications to Mathematical Finance, World Scientific, (2004) 355–368.
[24] H. Sugita, Security of Pseudo-random Generator and Monte-Carlo Method, Monte Carlo Methods and Appl., 10-3, VSP(2004), 609–615.
[25] H. Sugita, The Random Sampler,疑似乱数生成と動的ランダム-ワイル-サンプリングのための C/C++言語ライブラリ，下記にて公開:
http://homepage.mac.com/hiroshi sugita/mathematics.html.
[26] H. Sugita and S. Takanobu, Random Weyl sampling for robust numerical integration of complicated functions, Monte Carlo Methods and Appl., 6-1 (1999), 27–48.
[27] 高橋正子，計算論(計算可能性とラムダ計算)，近代科学社，(1991).
[28] S.Takanobu, On the strong-mixing property of skew product of binary transformation on 2-dimensional torus by irrational rotation, Tokyo J. Math. 25-1 (2002), 1–15.
[29] 高信敏，private communication, (1998).
[30] 高橋陽一郎+志賀浩二，確率論をめぐって，日本評論社，(1992)．
[31] A. Yao, Theory and applications of trapdoor functions, Proceedings of the IEEE Foundations of Comput. Sci., (1982), 80–91.
[32] 安富健児，Weyl変換に関する従属性消滅定理のエルゴード論的証明，修士論文(神戸大学大 学院自然科学研究科), (2001).
[33] K. Yasutomi, A limit theorem for sequences generated by Weyl transformation: Disappearance of dependence, Probab. Theory Relat. Fields 124 (2002), no. 2, 178–188.
[34] K. Yasutomi, A direct proof of dependence vanishing theorem for sequences generated by Weyl transformation, J. Math. Kyoto Univ. 43 (2003), no. 3, 599–607.
[35] K. Yasutomi, A dependence vanishing theorem for sequences generated by Weyl transformation, J.
Math. Kyoto Univ. 44 (2004), no. 2, 365–380.
*文献は網羅的なものではない．とくに計算機科学関係の文献はもっと充実させる必要がある．
索 引
記号
#, 16
，, 1
hti, 30
≈, 6
∈U, 21 btc, 27 btcm, 27 {0,1}∗, 21 1B(x), 1 A(α(m),s), 36 α(m)Lj , 30 α(m)Uj , 30 α(m),s, 30 B(α(m),s), 30 B, 27 Bm, 27 Bτ, 71 β, 50 β(m)j , 30 D, 30 di, 27 Dm, 27 δf,A(n), 22 eδf,Ae(n), 25
Dm, 27
E(m)(k0, . . . ,kl−1;α), 35 E, 1
F(m)(k0, . . . ,kl−1;α), 28 K(y), 16
KA(y|x), 15 L(p), 15 m(x), 18 mU(x), 17 mod, 26
µy(p(x1, . . . ,xn,y)), 14 N, 1
NP, 23 P, 23 PL, 1 Pr, 1 PrY, 21 ri(x), 34 R, 1 Sf,A(n), 22 eSf,Ae(n), 25 s1,s2, 30 σ(m, j), 30 S(m), 27 Tf(n), 21
Tf(x,y, α, 1, 2), 50 T1, 27
Tk, 27 Var, 1 X(m)n (x;α), 34 Yn(m)(x;α), 27 Z, 1
用語
DRWS, 77 i.i.d.
—サンプリング, 8, 61–63 L2-ロバスト, 63
P, NP予想, 23, 24 RWS, 63
アルゴリズム, 15 一般的な値, 1, 3 賭け, 1, 3
棄却法, 73 危険率, 17, 20 疑似乱数, 6
—の種, 2, 6, 22, 26 疑似乱数生成器, 2, 6, 21
—の初期化, 6 BBS生成器, 26
暗号理論的に安全な—, 7, 23 計算量的に安全な—, 7, 22, 24, 25 次ビット予測不可能な—, 25 集合Aに対して安全な—, 2, 6 ワイル変換による—, 28 帰納的
—可算集合, 17
—関数, 14 原始—関数, 14 最大—零集合, 19
—部分関数, 13 計算量, 23
空間—, 7 時間—, 7, 21 ゲーデル数, 14 検定, 12, 17
万能—, 17 万能列—, 20 列—, 20 サンプリング, 1
—に関する基本的な不等式, 61 i.i.d.—, 8, 61–63
動的ランダム-ワイル- —, 77 無作為な—, 11
ランダム-ワイル- —, 63 チェビシェフの不等式, 4, 8, 10 チューリング機械, 21, 70, 72
万能—, 14
停止時刻, 71, 72, 74
—に関して可測な関数, 71, 76 トーラス, 27
万能
—アルゴリズム, 15
—検定, 17
—列検定, 20 標準的順序, 15 分布関数, 23
ペアごとに独立, 66 平均2乗誤差, 77 枚挙定理, 14, 18, 20
模倣(確率変数の), 70 モンテカルロ積分, 2, 8 モンテカルロ法, 3
ラデマッハ関数列, 34, 50 乱数, 2, 5, 16
コルモゴロフの複雑さ, 16 無限—, 19
臨界サンプル数, 33 ワイル
動的ランダム—サンプリング, 77
—変換, 28, 67
—変換による疑似乱数生成器, 28 ランダム- — -サンプリング, 63