chap7.7

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

Download Report