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*
© Copyright 2024 ExpyDoc