「デタラメさ」雑考 - nifty

「デタラメさ」雑考
牧琢弥
version 1
October 13, 2012
1
1
Introduction
自然界の法則性や規則性を数理的に調べる営みが自然科学だとしたら，その
反対と思われる「デタラメさ」とは何かという方向から第二土曜会の趣旨に
沿うように問題提起ができればと思う．ただし，問題提起者は，このアプロー
チに対してよい案内ができるかは疑問であるが，皆さんとこれらの問題を共
有し議論するだけの価値と深さをもった問題であると考える．
2
乱数について
まずは，数値におけるデタラメさとしての乱数をどう扱うか？について考え
よう．
歴史的には，無作為抽出（ランダムサインプリング）の必要性が挙げられる．
（偏りの無さが重要）
無作為抽出の方法として，
・サイコロをふる．
・無作為に数字のかかれた紙を抽出．
・乱数表 105 − 106 桁の乱数列の出版（1927, Tippett）．
つぎに，秘匿情報の暗号などの必要性が挙げられる．
（予測不可能性が重要）
さらに
・計算機の発達
ストリーム暗号→大量のデータを暗号化・復号化するのに大量のデタラメな
ビット列が必要
・科学的シミュレーションの必要性例：Monte-Carlo method
(この場合「一様性」「独立性」「高速性」「再現性」が重要)
マンハッタン計画 von Neumann によるコンピュータによる疑似乱数の最
初の利用 (平方採中法)
→現在，108 − 1011 個以上の乱数が必要とされている．
2
しかし，
・乱数表は，電子暗号に使えない．
（10 万通りはコンピュータですぐ計算可能）
膨大な乱数表は，保存するのに困難．
・乱数発生器高価，低速，故障のリスク
→では膨大な数の乱数列を発生させる方法があるか？
●確率論的なデタラメさ
サイコロをふる，表（＝１），裏（＝０）として何回かふって 2 進数列をつ
くる．
情報エントロピー（Shannon, 1948）
S=−
∑
pi log2 pi
(1)
i
例：コインを 1 回投げるときの entropy :S=1
Ｎ回投げてＮ行の 2 進数をつくるＳ＝Ｎ.
このとき 2N の乱数が得られる．
Shannon 「確率的要素によってのみエントロピー（デタラメさ）が増大する」
→「確率的要素がない操作ではデタラメさは増えない」
→現在のデジタル・コンピュータでは，デタラメさを生み出すことができな
い．
（量子コンピュータは？脳は？）
●疑似乱数発生法・平方採中法 von Neumann (1940) 漸化式を使ったコンピュータにおける
疑似乱数の発生→核反応のシミュレーション
その後，
・Lehmer 線形合成法 Linear Congruential Generator(1960-1990)
xn+1 = xn × 1103515245 + 12345
3
mod 232
(2)
シード x1 の選び方によらず周期 232
→低コストかつ高速（数分で生成可能）ANSI-C などの標準的な疑似乱数．
→再現性がある（シミュレーションにはいいか暗号には悪い）
・Mersenne Twister(1996-)
二元体 F2 の多項式
これらで無事解決？（真の乱数を発生する方法はあるか？）
3
デタラメなビット列をつくる
いままでは話デタラメ「に」，ビット列をつくる話．
例：コインを投げて，
（１） 1001 1010 0110 を発生させたり，
（２） 0000 0000 0000 とか 1010 1010 10 10 なども発生する．
この場合，どちらも同じ確率 1/212 で発生する．
ところで，上の例（１）と（２）を比べると（１）のほうがデタラメ「な」
列の感じがする．
しかし，見た目ではなんともわからない．
11.001001000011111101101010100010001000010110100011000010001101001100010011000110011
はどうだろう？
→じつは，これは π の 2 進表示．
これもデタラメなビット列として扱えるのか？
→そもそも，デタラメさ（ランダムネス）の定義が不明．
では，
（上記の応用上）デタラメさとしてどのような性質が必要か？
・典型性わずかな実数だけが持つ特殊な性質を持たない
・記述不可能性記述が困難または圧縮不可能性
・予測不可能性次の値を予測するのが困難または独立性
ここからの話デタラメ「な」ビット列をつくる話．
規則性があるビット列（上の例（２））は，その規則を使ってこの列を「圧
縮」が可能であるという直感がある．例えば，
（書き方はよくないが）
4
0000000000 = 010
1010101010 → 10 を 5 回ならべる
(3)
Kolmogorov-Chaitin Randomness
【定義 1-1】x を二進列とする．x の最小記述（minimal description）を d(x)
と書き，テープ上に x を書き出して停止する TM M とそれに対する入力 w の
対のうちで最短の記述 < M, w > とする．このような記述を複数存在するな
らば，その中で辞書式順序で最初のものを選ぶ．x の記述の複雑さ descriptive
complexity を K(x) と書き，
K(x) = |d(x)|
(4)
とする．
（descriptive complexity を Kolmogorov-Chaitin complexity とも呼ぶ．以
下 Kolmogorov 記述量と呼ぶ）
言い換えると，K(x) は x の最小記述の長さ, すなわち有限列を生成するのに
必要な最小のプログラムの長さ K(x) を表現している
例：ここで 5000 個の 0 の列の K(x) を評価してみる．
0 を 1000 個出力するプログラムは，Ｃ言語で，
P= int main(){int i;for(i=0;i¡5000;i++)printf(”0”);printf(”\n”);}
これは６３文字，６３×７＝４４１ bit なので，
K(05000 ) ≤ 441 < 5000
(5)
これは，0 を 1000 個並べた数は規則的だったことを反映している．では，ラ
ンダムである列の K(x) の特徴を見てみる．n ビット列 x を trivial に出力す
る方法は，Ｃ言語では，
P= int main{printf(’bin(x)’);}
ここで，bin(x)=x のビット長を二進符号化したもの「：」を符号化したものｘのように並べることにする（語頭符号化）．すると |P | ≈ n+7(log2 n+23) =
n + 7log2 n + 161 となる．そこで，
5
【定理 1-1】任意のビット列 x に対して，つぎの不等式が成り立つ．
K(x) ≤ |x| + c1 log2 |x| + c0
(6)
ここで，c1 , c2 は，x に依存しない定数である．
この右辺を Kolmogorov 記述量の上界と考えてよいだろう．
この記述法を用いると Kolmogorov 記述量に対するややこしい【定義 1-1】は，
K(x) = min{|P | : P () = x}
(7)
と書ける．さらに情報 y があたえられたときの x の相対的 Kolmogorov 記述量
K(x) = min{|P | : P (y) = x}
(8)
を考えることができる．
【定理 1-2】
∃c∀x[K(x) ≤ |x| + c]
(9)
K(x) ≤ |x| − c
(10)
【定義 1-2】
のとき，x はｃ圧縮可能 (c-compressible) という．
圧縮不可能なビット列は，Kolmogorov ランダムであるという．またある k ≥ 0
なる k に対し
K(x) ≥ |x| − k
(11)
のとき，x は，k-ランダムと呼ぶ．
【定理 1-1】の |x| = n の値が大きいとき，
対数項は無視できて，K(x) ≤ |x| = n となる．では，どれだけ k-ランダムな
数があるかという疑問に対し，
【定理 1-3】長さ n のビット列に対し，
k − ランダムな列の数 ≥ 2n (1 −
1
2k+c2
)
(12)
すなわち，高い密度で存在することが証明されている．
問題：コンピュータで効率よく乱数は発生させることができるか？
問題：与えられたビット列が Kolmogorov の意味でランダムであることを知
6
ることができるか？
問題：シード（鍵）が与えられた場合には多項式時間で生成できるが，シー
ドを知らない場合には，その数列に関する一切の予測ができず，多項式時間
では生成できない数列はつくれるか？(Blum-Blum-Shub 1986)
【定理 1-3】任意のビット列 x に対し， K(x) を計算するアルゴリズムは存在
しない．
（証明は，K(x) を計算できるプログラムＡを仮定し背理法で導く．
）
Martin-L¨
of Randomness1
ある無限列 ω のデタラメさ（不規則性）を定義できないか？(以下 [3]）
ω を統計的にテストすることを考えてみる．
ここでは，ω の n 個の先頭からの有限部分列 ω1:n に対して，n が大きくなる
とき，ランダムに生成された無限列ならば，確率 ≈ １で合格（ほとんど棄却
されない）漸近的なテストを考える．
例： ω1:n に対し，#1 (ω1:n ) を「１」が出現する回数としたとき，#1 (ω1:n −
√
n/2)/ n というテスト A はこれを満たす．
（０に収束しないとき棄却）
このようなテストを Martin-L¨
of は，次のように定式化した．
【定義 2-1】無限ビット列 ω から，自然数へのつぎの条件を満たす評価関数
δ をランダムネスの列テスト (sequential test) と呼ぶ．
（１）有限ビット列上の関数 γ を用いて，δ(ω) = lim supn→∞ γ(ω1:n ) と定義
できる．
（２）任意の m > 0 に対して，µ(δ(ω) ≥ m) ≤ 2−m が成り立つ．
ここで，µ(δ(ω) ≥ m) は，δ(ω) ≥ m となる確率．
列 ω が，この列テスト δ に「合格」するか「棄却」されるかを見る．
1
Per Martin-L¨of （ 1942 年-) スウェーデンの論理学者、哲学者、数学者。直観主義
型理論の創案者 7
先ほどの例：
γA (ω1:n ) = log2
#1 (ω1:n − n/2)
√
n
(13)
をテストＡとすると，１つのランダムネスの列テストとなっている：
（γA (ω) < ∞ で「合格」，γA (ω) = ∞ で「棄却」）
これを満たすテスト（Ａ，Ｂ，Ｃ・
・
・）にすべて合格する列をランダムな無
限列と定義してよいか？そもそも，このような列テストはどれだけあるだろ
うか？
→答え：列テストは無限に（連続体濃度）存在する．
上の定義に従うすべての列テストに合格する無限ビット列は存在しない．
（す
なわち，任意の ω を棄却する列テスト δ が作れることが証明できる．
）
では，ランダムネスを定義するにはどうすればよいだろうか？
【定義 2-2】すべての「計算可能な」列テストに合格した無限列 ω
⇔ω は Martin-L¨of ランダム (1 ランダム）である．(1966)
では，Martin-L¨
of ランダムな列はどれだけ存在するのだろうか？
【定理 2-1】Martin-L¨
of ランダムな列 ω に対して，
µ(ω) = 1
(14)
これはランダムネスの数学的直観とよく一致する（特定の定義によらない）
(Martin-L¨of-Chaitin のテーゼ）
● Martin-L¨
of ランダム性と Kolmogorov ランダム性の関係
【定理 2-2】無限ビット列 ω が Martin-r¨
of ランダム
⇔ そのすべての先頭部分列が Kolmogorov ランダム
→典型性と記述不可能性（圧縮不可能性）の等価性
予測不可能性との等価性は？
【定理 2-3】Shnorr(1971)
A(∈ 2ω カントール空間）が Martin-L¨of ランダム
⇔ すべての可枚挙マルチンゲールがＡで成功しない．
8
● von Lambalgen の定理 (1987)
● Kolmogorov ランダムネスを応用する．
・Kolmogorov 記述量＝データの規則性の尺度
→２つのデータ x, y 間の類似度=「距離」NID(x,y) (Cilibrasi and Vitanyi,
2005)
・機械学習，人工知能への応用（カントール空間→位相空間, CMS, CTS）
4
Discussion
人間の知的活動にとってデタラメさとはなにか．
References
[1] Micheal Sipser, Introduction to the theory of COMPUTATION (2000).
[2] 四辻哲章，
「計算機シミュレーションのための確率分布乱数生成法」
[3] O.Watanabe, Randomness from Computational View Points, Proceedings of Statistical Mathematics vol.54, No.2, pp511-523 (2006).
[4] 弓林司, 「計算可能とは何か」，第 4 回第２土曜会資料．
9

Download Report