疑似乱数 - 186 @ hatenablog

ちょっとした思いつき。
疑似乱数列を生成する計算方法の妥当性を調べるのにチューリングテスト的方法は使えるか。
放射線などを用いた真の乱数列と、調査したい計算方法の生成する疑似乱数列とが、二つのチャネルA, Bから流れ出てくる。でもどちらの数列がどちらのチャネルから流れてくるかは分からないとする。乱数を検定するアルゴリズムを別途用意しておき、二つのチャネルのどちらが真の乱数列であるか判定できるか。 ――という話題。
それができるなら、ランダムネスと知能との類似性という逆説的で面白い話題につながるね。
チューリングテストでは、本物の人間と適切な判定者によって、コンピュータのプログラムの知能性(?)を判定する（言い換えるとそれを知能の定義とする）。上に書いたテストでは、真の乱数列（本物の人間の代わり）と検定をするアルゴリズム（適切な判定者の代わり）によって、疑似乱数列の計算方法の妥当性を判定する（言い換えるとそれを乱数の定義とする）。
※ すでに誰かが考えていそうな話だけれど、結城はこれ以上展開できないので、念のため公開（上で書いたことは、すごく当たり前かすごくナンセンスかのどちらかのような気もする）。

|・σ・)ノ(暗号学的な)疑似乱数の定義
まさに結城さんが考えているような定義そのもの.

暗号の方だとこんな感じ.
伸長関数 $l:\mathbb{N}\to\mathbb{N}$ を考えて, ある決定性アルゴリズムGが疑似乱数生成器*1であるとは, $G:\{0,1\}^n \to \{0,1\}^{l(n)}$ で, 任意の多項式時間確率的アルゴリズムAについて, $\| \Pr[A(U_{l(n)})=1] - \Pr[A(G(U_n))=1] \|$ がnについて無視できること (ただし, $U_n,U_{l(n)}$ はそれぞれ長さn, l(n)の一様分布に従う確率変数. 確率は $U_n,U_{l(n)}$ とAのコインによる).

追記: 数式の読み方
Gの出力と真の乱数列を見分ける多項式時間アルゴリズムが存在しなければ, Gは疑似乱数生成器.
Aが見分けるとは, Aに真の乱数を突っ込んだときの出力の分布と, AにGの出力を突っ込んだときの出力の分布との統計的な差がnegligibleでないこと.
セッティングはこんな感じ. 伸長関数なんで, 1^nは突っ込まなくても良かったはず.

(画像はPowerpoint 2007 Betaで作成. willustratorを使おうかと思ったが, 矢印が無いので困る.)