chap7.5

Probabilistic Method
7.5 章
岩間研究室 D2
川原純
7.5 の概要
• 7.1～7.4 で証明した定理の具体例を扱う
1
2
3
g
1
2
3
1つ目の具体例
L(g) = 2
g
• {1,2,...,n} から {1,2,...,n} への関数 g を考える。
n = 3 なら
g(1) = 3, g(2) = 1, g(3) = 3
1
2
3
1
2
3
L(g) = 0
1, 1)
• g の種類は nn 通りある。 ( g(1), g(2), g(3) ) = (1,
(1, 1, 2)
• nn 通りの関数から等確率で1つ選ぶ。
• g の「ヒットしない」数を考える。
1
– これを L(g) とする。
2
3
(1, 1, 3)
(1, 2, 1)
...
(3, 3, 3)
g
1
2
3
33 = 27 通り
ヒットしない
L(g) = 1
L(g) = (g のヒットしない数)
すなわち、g(x) = y となる x が存在しない y の数
L(g) の期待値
• g(x) = 1 となる x が存在しないとき、L1(g) = 1、存
在するとき、L1(g) = 0 とする。
Li(g) : g(x) = i となる…
g
1
2
3
4
1
2
3
4
L1(g) = 0
L2(g) = 1
L3(g) = 0
L4(g) = 1
L(g) = 0+1+0+1 = 2
• 明らかに L(g) = L1(g) + L2(g) + … + Ln(g)
• したがって、E[L(g)] = E[L1(g)] + … + E[Ln(g)]
=n (1-1/n)n ～ n / e
E[Li(g)] = ( g(x) = i となる x が存在しない確率 )
= ( g(1) = i とならない ∩ g(2) = i とならない∩ … ∩ g(n) = i とならない) 確率
L(g) = (g のヒットしない数)
すなわち、g(x) = y となる x が存在しない y の数
定理 7.5.1
• Bi = {1, 2, ..., i } とする。
• g(i) の行き先を変えたとき、L(g) の変化は高々1。
リプシッツ条件を満たす。
• 定理 7.5.1
• 証明
定理 7.4.2 を直接適用すればよい。
2つ目の具体例
一般にノルム空間
• vi を大きさ 1 以下の n 次元空間上のベクトルとする。
• 定理 7.5.2
定理 7.5.2
定理 7.5.2 の証明
• {-1,1} から等確率に
をとる。
• マルチンゲール X0,...,Xn = X をを順に開けるこ
とで定義する。
•
が変わることで、X は高々 2 だけ変化する。
• 定理 7.4.1 の適用すると、
•
を、i 番目だけが異なるn-組とする。
i
ε= (-1, 1, 1, ..., 1,..., -1)
ε’= (-1, 1, 1, ...,-1,..., -1)
• Azuma の不等式を使えばよい。
3つ目の具体例
• {0, 1}n 上のHamming metric を考える。
n = 3 のとき
110
x と y の異なる「ビット」の個数（ハミング距離）
111
に対し、
101
100
010
000
011
=
∃
001
110
111
100
101
010
A
011
B(A, 1)
A から 1 歩で行ける部分
B(A, 2)
000
001
B(A, 0) は A に等しい
ハミング距離
A から s 歩で行ける部分
定理 7.5.3
• 定理 7.5.3
を
を満たす定数とする。
• 証明
{0, 1} n から等確率で1 つ要素をとる。
y ∈ {0, 1} n に対し、
y = 101011000
マルチンゲール X0, X1, ..., Xn = X を、座標を順に 1 つずつ開けることで定義する。
これはリプシッツ条件を満たす。
y, y’ を座標が1つだけ異なる2数とする。
が成り立つ。したがって、定理 7.4.2 より
ハミング距離
A から s 歩で
行ける部分
定理 7.5.3
定理 7.5.3 の証明
直前のスライドで証明した式
仮定
Pr(X)
y と x の距離が 0 になる = y が A の要素である
ε
と仮定する。
Pr(X)
0
<ε
<ε
ε
λ √n
μ
λ√
n
これは矛盾。したがって
0
<ε
λ √n
μ
λ√
n
X
2λ n
√
X
4つ目の具体例
• すべての頂点の次数が D 次のグラフ G （頂点数 N）
• D, N は後で∞に飛ばす
• p = 1/D
枝を確率 p で H に含める
G
H
D: 頂点の次数、N: 頂点の個数、p = 1/D
4つ目の具体例
枝を確率 p で H に含める
G = (V, E)
H
孤立した枝の集合を M とする
M に接続していない頂点の集合を V* とする
deg*(v) : {v, w} ∈ E となる w ∈ V* の数
deg*(v) を評価するのが目標
D: 頂点の次数、N: 頂点の個数、p = 1/D
V* : M に接続していない頂点の集合
M : 孤立した枝集合
deg*(v) : {v, w} ∈ E となる w ∈ V* の数
ゲーム
プレイヤー : ポール
出題者
知らされる情報 : グラフ G、頂点 v
尋ねられた問いについて正しく答える
（PCP ？みたいな難しいことはしない）
知らされない情報 : グラフ H
目的 deg*(v) を求める
行える動作
枝 e が H に含まれるか出題者に尋ねる
1 つの枝につき 1 クエリ
G
v
注：実際は頂点の次数はすべて D （この図は嘘）
H
V*
v
deg*(v) = 3
M (孤立枝集合)
D: 頂点の次数、N: 頂点の個数、p = 1/D
V* : M に接続していない頂点の集合
M : 孤立した枝集合
deg*(v) : {v, w} ∈ E となる w ∈ V* の数
ポールのストラテジー
ゲーム
1. v に隣接する頂点 w を1つ選択
プレイヤー : ポール
知らされる情報 : グラフ G、頂点 v
知らされない情報 : グラフ H
目的 deg*(v) を求める
行える動作
枝 e が H に含まれるか出題者に尋ねる
1 つの枝につき 1 クエリ
G
v
注：実際は頂点の次数はすべて D （この図は嘘）
2. w に接続する辺のうち、H に含まれる
出題者
辺の数を数える（クエリ D 回）
0 個 → w ∈ V*
尋ねられた問いについて正しく答える
2 個以上 → w ∈ V*
（PCP
？みたいな難しいことはしない）
1個
→ 3 に進む
3. {w, u} ∈ H とする。u に接続する辺の
うち、H に含まれる辺の数を数える
（クエリ D – 1 回）
0 個 → w ∈ V*
1 個以上 → w ∈ V*
V* D(2D – 1) 回
クエリ回数は全体で
H
H
V*
v
deg*(v) = 3
M (孤立枝集合)
ポールのストラテジー
1. v に隣接する頂点 w を1つ選択
2. w に接続する辺のうち、H に含まれる
辺の数を数える（クエリ D 回）
0 個 → w ∈ V*
2 個以上 → w ∈ V*
1 個 → 3 に進む
3. {w, u} ∈ H とする。u に接続する辺の
うち、H に含まれる辺の数を数える
（クエリ D – 1 回）
0 個 → w ∈ V*
1 個以上 → w ∈ V*
M : 孤立した枝集合
deg*(v) の評価
V* : M に接続していない頂点の集合
deg*(v) : {v, w} ∈ E となる w ∈ V* の数
• 「e ∈ H」かどうかを尋ねるクエリを考える。
v
H
w
クエリの回数
全部で
deg*(v) を求めたい
for each w such that {v, w} ∈ E
のとき
for each u such that {w, u} ∈ E
{w, u} ∈ H かどうかをきき、その個数を数える。
個数が 0 個 or 2 個なら、w ∈ V* である。
個数が 1 個なら、
for each z such that {u, z} ∈ E
{u, w} ∈ H かどうかをきき、その個数を数える。
1 個なら w ∈ V*
2 個以上なら w ∈ V*

Download Report