Presentation is loading. Please wait.

Presentation is loading. Please wait.

Probabilistic Method 7.7

Similar presentations


Presentation on theme: "Probabilistic Method 7.7"— Presentation transcript:

1 Probabilistic Method 7.7

2 7.7の内容 7.6のTALAGRANDの不等式の応用 定理7.7.1 example1 ランダム[0,1]ベクトルのLISの平均長さ
 ランダムグラフG(n, ½)がサイズkのクリークを含まない確率(7.3.2の結果の改善)

3 リプシッツ x と y の成分が一つしか違わないとき、 必ず|h(x) – h(y) | ≦1が成り立つならば、
x = (x1 , ... , xn), y = (y1, ... , yn)∈Ω h : Ω→R

4 f-certifiable 定義3 h(x)≧sのとき、 I ⊆ {1, … , n} ( |I|≦f(s) )が存在して、
すべての i ∈ I で xi = yi となるような すべての y∈Ωについて h(y)≧s であることを h は f-certifiable であるという。

5 定理7.7.1 h が リプシッツかつ f-certifiable のとき、 任意の b, t について、
リプシッツ条件のかわりにK-リプシッツのときは、

6 定理7.7.1を証明するために、以下の主張を証明。
At = {xΩ: ρ(A,x)  t } h(y)≧b At A

7 主張1の証明 背理法  h は f-certifiable で h(y)≧bなので、定義3を満たすような I ⊆ {1, … , n} をとることができる。 At = {xΩ: ρ(A,x)  t } y :h(y)≧b A

8 主張1の証明 距離の定義より、どんなアドバーサリの移動コストに対しても、t 以下のコストで y に移動できるような z∈A が存在する。
移動コストを                    と取る。 y と z の第 i 成分が違う個数は、     で            個以下。 (それを超えるとコストt以下に矛盾) A

9 主張1の証明 y‘ を以下のように作る。 hはf-certifiable なので、h(y’) ≧ b。
また、y’ は z のi ∈Iの成分を yi で 置き換えたものなので、y’ と z の間の 成分が違う個数は、前ページの  より  高々        個。 A

10 主張1の証明 y’ と z は高々 個の違いなのでリプシッツ条件より h(y’) ≧ b、z∈Aより なのでh(y’)>h(z)
よって              となるが              と矛盾する。              よって、主張1が証明できた。 A

11 定理7.7.1の証明 Talagrand’s Theorem より、 主張1より、
 としたとき、1-Pr[At] ≧ Pr[X≧b] なので、 証明終

12 定理7.7.1より 任意のb, t について、 よって、b = m (m は Xのメディアン)とおけば、
同様に、b - t f(b)1/2 = m とおけば、 Xの値はメディアンからそんなに離れない。

13 応用例1 x=(x1, … , xn) (xi は[0, 1]から一様、独立に選ぶ)
X=h(x)を、xのLIS(最長増加部分列)の長さとする ・一つの成分の値を変えただけではLISの長さは高々1  しか変わらない。(リプシッツ条件) ・f(s) = sとすると、h は f-certifiable (xのLISの要素s個だけ固定しておけばh(x’) ≧ s を保つ) ほとんどすべてXがメディアンに近いことを示す。

14 応用例1 定理7.7.1より ここで、 であるから(ホワイトボード) s>>n1/4 とすると、Pr[X≦m-s]→0
ここで、         であるから(ホワイトボード)   s>>n1/4 とすると、Pr[X≦m-s]→0  よって、Pr[X-m>-s]→1 (mはXのメディアン)

15 応用例1 定理7.7.1でb - t b1/2 = mとなるようにbをとると、 t をゆっくり増加させると、Pr[X≧b]→0 つまり
b=m+(1+o(1) ) t m1/2 となって、  Pr[X≦m+tm1/2]→1 つまり、s>>n1/4 とすると、   Pr[X-m≦s]→1 Pr[X-m>-s]→1の結果とあわせて、Pr[|X-m|<s] → 1. (mはXのメディアン)

16 応用例2 ランダムグラフ G=(n, ½)がkクリークを持たない確率  7.3.2の結果は、   ここが8乗だった

17 の証明 枝素なkクリークの最大個数:Y=h(G) ・E[Y] = Ω(n2k-4) (7.3.2の結果) ・Gの枝を一つ変えても、枝素なkクリークの数は高々一つしか変化しない(リプシッツ条件) ・   とすると、h は f-certifiable ・定理7.7.1より、 (mはYのメディアン)

18 とすると、m=Ω(n2k-4)より

19 k~log n を代入して、


Download ppt "Probabilistic Method 7.7"

Similar presentations


Ads by Google