Probabilistic Method ７．７
７．７の内容 ７．６のTALAGRANDの不等式の応用 定理7.7.1 example1 ランダム[0,1]ベクトルのLISの平均長さ ランダムグラフG(n, ½)がサイズｋのクリークを含まない確率（7.3.2の結果の改善）
リプシッツ ｘ と ｙ の成分が一つしか違わないとき、 必ず｜h(x) – h(y) | ≦１が成り立つならば、 x = (x1 , ... , xn), y = (y1, ... , yn)∈Ω h : Ω→R
f-certifiable 定義３ ｈ（ｘ）≧ｓのとき、 I ⊆ {1, … , n} ( |I|≦ｆ（ｓ） )が存在して、 すべての i ∈ I で xi = ｙi となるような すべての ｙ∈Ωについて ｈ（ｙ）≧ｓ であることを h は f-certifiable であるという。
定理７.７.１ h が リプシッツかつ f-certifiable のとき、 任意の b, t について、 リプシッツ条件のかわりにK-リプシッツのときは、
定理7.7.1を証明するために、以下の主張を証明。 At = {xΩ: ρ(A,x) t } ｙ h(y)≧ｂ At A
主張１の証明 背理法 h は f-certifiable で h(y)≧ｂなので、定義３を満たすような I ⊆ {1, … , n} をとることができる。 At = {xΩ: ρ(A,x) t } ｙ :h(y)≧ｂ A
主張１の証明 距離の定義より、どんなアドバーサリの移動コストに対しても、ｔ 以下のコストで ｙ に移動できるような ｚ∈A が存在する。 移動コストを と取る。 ｙ と ｚ の第 i 成分が違う個数は、 で 個以下。 （それを超えるとコストｔ以下に矛盾） ｙ ① ｚ A
主張１の証明 ｙ‘ を以下のように作る。 hはf-certifiable なので、h(y’) ≧ b。 また、y’ は ｚ のi ∈Iの成分を yi で 置き換えたものなので、ｙ’ と z の間の 成分が違う個数は、前ページの より 高々 個。 ｙ ① ｚ A
主張１の証明 y’ と z は高々 個の違いなのでリプシッツ条件より h(y’) ≧ b、ｚ∈Aより なのでh(y’)>h(z) よって となるが と矛盾する。 よって、主張1が証明できた。 ｙ ｚ A
定理7.7.1の証明 Talagrand’s Theorem より、 主張１より、 としたとき、1-Pr[At] ≧ Pr[X≧b] なので、 証明終
定理7.7.1より 任意のb, t について、 よって、b = m (m は Xのメディアン)とおけば、 同様に、b － t f(b)1/2 = m とおけば、 Xの値はメディアンからそんなに離れない。
応用例１ ｘ＝（x1, … , xn) (xi は[0, 1]から一様、独立に選ぶ) X=ｈ（ｘ）を、ｘのLIS(最長増加部分列)の長さとする ・一つの成分の値を変えただけではLISの長さは高々１ しか変わらない。（リプシッツ条件） ・f(s) = sとすると、h は f-certifiable （ｘのLISの要素ｓ個だけ固定しておけばh(x’) ≧ s を保つ） ほとんどすべてXがメディアンに近いことを示す。
応用例１ 定理7.7.1より ここで、 であるから（ホワイトボード） ｓ＞＞ｎ1/4 とすると、Pr[X≦ｍ－ｓ]→0 ここで、 であるから（ホワイトボード） ｓ＞＞ｎ1/4 とすると、Pr[X≦ｍ－ｓ]→0 よって、Pr[X－ｍ＞－ｓ]→１ （ｍはXのメディアン）
応用例１ 定理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のメディアン）
応用例２ ランダムグラフ G=(n, ½)がkクリークを持たない確率 7.3.2の結果は、 ここが8乗だった
の証明 枝素なｋクリークの最大個数：Y＝h(G) ・E[Y] = Ω（n2k-4) (7.3.2の結果） ・Gの枝を一つ変えても、枝素なｋクリークの数は高々一つしか変化しない（リプシッツ条件） ・ とすると、h は f-certifiable ・定理7.7.1より、 （mはYのメディアン）
とすると、m=Ω（n2k-4)より
ｋ～log n を代入して、