AC03_3_jkawahara

Extractor
D3 川原純
Extractor
• Extractor : 一様でない確率分布から一様分布
に近い分布を作り出す技法。
例：自然界にある乱数（熱揺らぎ等）
確率分布
サンプリング
X
正体不明（のことも多い）
x1, x2, ...,xn
f
(extractor)
f(x1), f(x2),..., f(xn)
一様分布に「近い」
Extractor
• Extractor : 一様でない確率分布から一様分布
に近い分布を作り出す技法。
例：自然界にある乱数（熱揺らぎ等）
確率分布
X
f
(extractor)
正体不明（のことも多い）
f(X)
一様分布に「近い」分布
弱い乱数発生源
weak random sources
• どんな確率分布からでも一様分布が作り出せる訳ではない
例：を考える
• 弱い乱数発生源（weak random sources）
Pr[X=1] = 1
Pr[X=0] = 0
の分布からはどのようにしても
– マルコフ鎖発生源（Markov-chain source）
作れない
(k は定数) に従う
確率遷移行列
以下の例はすべて {0,1}n 上の確率分布
– 予測不可能発生源（unpredictable source）
{0, 1}n上の確率分布 X
– ビット固定発生源（bit fixing source）
{0, 1}n上の確率分布 X で n-k ビットを固定したもの
直観的には n ビット中、k ビットがランダム
分布が「近い」とは
• 定義
は、
T 上の分布 P と Q が ε-close であると
が成り立つこととする。これを分布の統計距離と
呼ぶ。
任意の事象 A ⊆ T に対して
が成り立つことと同値。
分布がランダムさをもつとは
• 定義 {0, 1}n 上の確率分布 X の min-エント
ロピーを以下のように定義する
Ｘ
H∞(X) ≧ k なら
任意の x∈{0,1}n に対して
1
≧k
log
Pr[X=x]
Pr[X=x] ≦
2-k
直観的には k ビットのランダムさをもつ
Extractor の（理想的な）目標
•
を満たす任意の {0,1}n 上の確
率分布 X から1ビットを “extract” する extractor
の設計
f: {0,1}n → {0,1}
を満たす任意の X に対して、
Pr[x ← X, f(x) = 1] = 1/2 となる f を設計する
理想的なExtractor は構築不可能
定理
を満たす任意の {0,1}n 上の確率分布 X に
対して Pr[x ← X, f(x) = 1] = 1/2 となるような f は存在しない
証明のアイデア
n=3
000
1/8
001 1/16
H∞(X) = min
f : {0,1}3 → {0,1}
X
=
f
f(X)
…
111
1/4
0
1/2
1/16
1
1/2
1/8
log pi
1
log 1/4
=2
1/16
1/16
1/4
1
任意の H∞(Y) ≧ n – 1 を満たす Y について、
f(Y) は一様分布か？
理想的なExtractor は構築不可能
定理
を満たす任意の {0,1}n 上の確率分布 X に
対して Pr[x ← X, f(x) = 1] = 1/2 となるような f は存在しない
証明のアイデア
n=3
000
1/8
001 1/16
f : {0,1}3 → {0,1}
X
…
111
f
1/6
f(X)
1/6
1/4
0
1/16
1
1/8
log 1/6
≧2
Y
1/16
1/16
1/4
H∞(Y) =
1
1/6
0
1/6
1/6
0
1/6
f
f(X)
理想的なExtractor は不可能
を満たす任意の {0,1}n 上の確率分布 X に
対して、Pr[x ← X, f(x) = 1] = 1/2 となる f は存在しない
証明
ある X に対して、S = {x | f(x) = b} とする。
|S| ≧ 2n-1 となる b が存在する
確率分布 Y を、
f(y) = b となる y には 1/|S| を、
f(y) = b となる y には 0 を割り当てる。
H∞(Y) ≧ n – 1 を満たし、明らかに
Pr[y ←Y, f(y) = 1] = 0 or 1 なので、矛盾
b は 0 or 1
Extractor の定義
• 定義
で、
(k, ε)-extractor とは関数
を満たす任意の {0,1}n 上の確率分布 X に
ついて Ext(X, Ud) が一様分布 Um と ε-close になるもの
である。
d はシードと考える
d を下げる、mを上げるのが目標
BPP アルゴリズムのシミュレート
• Extractor があれば BPP アルゴリズムをシミュ
レートできる。
f(w) を計算するBPPアルゴリズムを考える。
となる多項式チューリング機械 A(w, z) が存在する（z ∈ {0,1}m）。
得体のしれない確率分布 X と extractor Ext が存在するなら
すべての y ∈ {0,1}d について、Ext(x, y) = z を計算して、
A(w, z) を走らせて、得られた答えの多数決をとる。
Disperser の定義
• 定義
で、
(k, ε)-disperser とは関数
を満たす任意の {0,1}n 上の確率分布 X に
ついて Dis(X, Ud) の台のサイズが少なくとも (1 - ε)2m である
Disperser は RP アルゴリズムをシミュレートできる
X ∈ Lk の場合（Lk は次元が k 以上の
上の
アフィン部分空間の集合）
sum-product theorem を使う前
k ≧ 2 log n のとき、extractor の存在を証明（probabilistic method）
k ≧ n / 2 のとき、extractor を構築
sum-product theorem を使った後
k ≧ δn, m = 1 のとき、disperser を構築 [Barakら 05]
k ≧ δn のとき、optimal extractor を構築 [Bouら 07]
小さな次元で大きな有限体のとき、extractor を構築 [GR05]
X∈
の場合
sum-product theorem を使う前
k ≧ 2 log n のとき、optimal extractor を構築（ラムゼーグラフ）
k ≧ n / 2 のとき、optimal extractor を構築 [CG88] [Vaz 87]
sum-product theorem を使った後
k ≧ 0.4999n のとき、optimal extractor を構築 [Bou 07]
k ≧ δn, m = 1 のとき、disperser を構築 [BW05]
A statistical version of the SumProduct Theorem
で、
を満たす任意の {0,1}n 上の確率分布 X に
ついて Dis(X, Ud) の台のサイズが少なくとも (1 - ε)2m である
Sum-Product Theorem は集合のサイズに関する命題なので、
disperser の構築に有用
しかし、extractor は f(X) が一様であることも要求するので、
単に集合の個数を議論するだけでは不十分
H0(A) = |support(A)|
Hshannon(A) = ∑-pi log pi
H2(A) =
• Theorem 3.2.15 (Sum-Product Theorem)
F =Fp とする。H0(A) ≦ 0.9 log p を満たすすべ
ての A ⊂ F に対して、H0(A + A) ≧ H0(A)1+ε と
H0(A × A) ≧ H0(A)1+ε の少なくとも一方を満た
す ε ≧ 0 が存在する。
H0(A) = |support(A)|
H2(A) =
H0 を H2 や H∞に置き換えた定理が成り立ってほしいが、
実際は成り立たない
• Theorem 3.2.16
F =Fp とする。H0(A) ≦ 0.9 log p を満たすすべ
ての A ⊂ F に対して、
H0(A × A + A) > (1+ε)H0(A)
を満たす ε ≧ 0 が存在する。
H0(A) = |support(A)|
H2(A) =
H0 を H2 に置き換えた定理が成り立つ
H2(A × A + A) > (1+ε)H2(A)
H2(A) =
• A, B, C を FP 上の独立な分布とする。
r(X) = H2(X) / log p ,
r = min(r(A), r(B), r(C)) とする。
[BW04] は以下の定理を示した。
• r ≦ 0.9 なら r(A,B,C) ≧ (1+ε)r
• r >0.9 なら r(A,B,C) = 1
となる定数 ε >0 が存在する。
• 以下のように関数列 f i を構築する
H2(A × A + A) > (1+ε)H2(A)
この定理を使うことで、H2(A) のエントロピーをもった
3 t 個の発生源から、少なくとも (1+ε)t H2(A) の
エントロピーをもった1つの発生源に変換することができる。
この手法で
上の（optimal）extractor を構築した [BW04]
k ≧δn, c = poly(1/δ)

Download Report