Probabilistic Method ７．７

Presentation on theme: "Probabilistic Method ７．７"— Presentation transcript:

1 Probabilistic Method ７．７

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

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

4 f-certifiable 定義３ ｈ（ｘ）≧ｓのとき、 I ⊆ {1, … , n} ( |I|≦ｆ（ｓ） )が存在して、
すべての i ∈ I で xi = ｙi となるような すべての ｙ∈Ωについて ｈ（ｙ）≧ｓ であることを h は f-certifiable であるという。

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

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

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

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

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

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

11 定理7.7.1の証明 Talagrand’s Theorem より、 主張１より、
　としたとき、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 応用例１ ｘ＝（x1, … , xn) (xi は[0, 1]から一様、独立に選ぶ)
X=ｈ（ｘ）を、ｘのLIS(最長増加部分列)の長さとする ・一つの成分の値を変えただけではLISの長さは高々１　　しか変わらない。（リプシッツ条件） ・f(s) = sとすると、h は f-certifiable （ｘのLISの要素ｓ個だけ固定しておけばh(x’) ≧ s を保つ） ほとんどすべてXがメディアンに近いことを示す。

14 応用例１ 定理7.7.1より ここで、 であるから（ホワイトボード） ｓ＞＞ｎ1/4 とすると、Pr[X≦ｍ－ｓ]→0
ここで、　　　　　　　　　であるから（ホワイトボード）　 　ｓ＞＞ｎ1/4　とすると、Pr[X≦ｍ－ｓ]→0 　よって、Pr[X－ｍ＞－ｓ]→１ （ｍはXのメディアン）

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

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

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

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

19 ｋ～log n を代入して、