Document

M1 吉田
W  i 1 Wi (Wi:確率空間,P:直積測度)
A  W, x = (x1,…,xn)W
 xからAへの距離r(A,x)を定めたい。
 xからyAへ一次元ずつ座標を合わせてい
くことを考える。
 アドバーサリが各次元の座標変化のコス
トを決める時に、xからあるyAに移動す
るのに必要な最小コストをr(A,x)とする。
n
r(A,x)は任意のaRn(|a|=1)に対して、ある
y=(y1,…,yn)Aが存在して
ai  r ( A, x)
xi  yi
となる最小値。
At={xW: r(A,x)t}と定義する。
A0=Aである。
W: {0,1}n上の一様分布, t : ハミング距離
 a=(n-1/2,…,n-1/2)と取れば
r(A,x)  minyAt(x,y)n-1/2
 もしxをAに移動するのにx1,…,xlを変化さ
せなければならないとき、
a=(l-1/2,…,l-1/2,0,…,0)と取ればr(A,x)  l1/2
Pr[A]: xWがA中の要素である確率
PrA1  PrAt   e
t 2 / 4
 Pr[A]がある定数以上で、tが十分大きけれ
ば、Wの殆どの部分がAから距離t以内に入
る。
 証明は後ほど。
U(A,x): s=(s1,…,sn){0,1}nで以下の条件を満
たすもの全体からなる集合。
あるyAが存在してxiyisi=1
例
W: {0,1}3 , x=(0,1,1),
A={(0,0,0),(1,0,0),(0,1,0),(1,1,0)}
の時、
U(A,x)={(*,1,1),(1,1,1),(*,*,1),(1,*,1)}
 U(A,x)はxからAに移動する道を表したもと
みなすことが出来る。
 r(A,x)を、任意のa(|a|=1)に対して、
あるsU(A,x)が存在し、a sr(A,x) となる
最小値と言い換えることが出来る。
 V(A,x):
U(A,x)の凸包
r ( A, x)  min | v |
vV ( A, x )
 証明
v  arg min | s | とする。
sV ( A, x )
点vを通り原点とvを通る直線に垂直な
平面は原点とV(A,x)を切り離す。
よってsV(A,x)に対してsvvvとなる。
 a=v/|v|と置くと、任意のsU(A,x)V(A,x)
に対してas=sa=sv/|v|vv/|v|=|v|
r(A,x)|v|
 任意のa(|a|=1)に対して、av|v|である。
v=Slisi (siU(A,x),li0,Sli=1)と表せるので、
Sli(asi)=av |v|。
よって、あるsiでasi|v|
r(A,x)|v|
 以上より定理が成り立つ。
1
1 2

W exp  4 r ( A, x)dx  Pr[ A]
 この定理からTalagrand’s
Inequality
が示せる。
 確率変数X=r(A,x) を考える。
 
Pr At  Pr[ X  t ]  Pr[e
X 2 /4
  Pr1A
Ee
X 2 /4
e
t2 / 4
]  E[e
X 2 /4
]e
t 2 / 4
定理より
なので、
Talgrand’s Inequalityが成り立つ。
帰納法による。
 n=1の時:
よって
0 x  A
r ( A, x)  
1 x  A
1

1/ 4
exp
r
(
A
,
x
)

Pr[
A
]

(
1

Pr[
A
])
e
  4

u+(1-u)e1/4u-1 (0<u1)より
1
1

 exp  4 r ( A, x)  Pr[ A]
 nで定理が成り立つとする。
OLD=W1Wn, NEW=Wn+1とする。
W=OLDNEW
zWはz=(x,w) (xOLD,wNEW)と書ける。
B={xOLD: (x,w)A for some wNEW}
Aw={xOLD: (x,w)A}
と置く。
zをAに移動:
wを変化させる: xをBに移動
wを変化させない: xをAwに移動
sU(B,x)(s,1)U(A,(x,w))
tU(Aw,x)(t,0)U(A,(x,w))
U(A,(x,w))の凸包V(A,(x,w))を考える。
sV(B,x),tV(Aw,x)なら(s,1),(t,0) V(A,(x,w))
よって任意のl[0,1]に対して
((1-l)s+lt,1-l)V(A,(x,w))
定理7.6.1より
r2(A,(x,w))(1-l)2+|(1-l)s+lt|2
||2の凸性から
r2(A,(x,w)) (1-l)2+(1-l)|s|2+l|t|2
s,tを最小に取ると
r2(A,(x,w))(1-l)2+lr2(Aw,x)+(1-l)2r2(B,x)
1 2
 (1l )
exp
r
(
A
,
(
x
,
w
))
x  4
  e
l
2
/4
1 l
1 2
 1 2

r
(
A
,
x
)
r
(
B
,
x
)
 

w
x 4
 4

 Holder’s
Inequality
p,q1, 1/p+1/q=1のとき
 f ( x) g ( x)dx  
1 2
 (1l )
xexp  4 r ( A, ( x, w ))  e
f ( x)
l
2
/4
2
/4
q 1/ q
1 l
1 2
 1 2

x 4 r ( Aw , x)   4 r ( B, x) 
で1/p=l, 1/q=1-lととると
1 2
 (1l )
xexp  4 r ( A, ( x, w ))  e
  g( x) 
p 1/ p
l
1 l
 1 2
  1 2

 x r ( Aw , x)   x r ( B, x) 
 4
  4

帰納法の仮定から大きくても
l
1 l
1   1 
(1 l ) / 4 

 

e
 Pr[ Aw ]   Pr[ B] 
r  Pr[ Aw ] / Pr[ B]  1
2
1
(1 l ) 2 / 4  l

e
r
Pr[ B]
ここで
1  2 ln r e 1/ 2  r  1
l
otherwise
 0
e
とlを選ぶと、
(1l ) 2 / 4  l
r
 2r
なので
Pr[ Aw ] 
1 
1 2

xexp  4 r ( A, ( x, w ))  Pr[ B]  2  Pr[ B] 
wで積分して
1 
Pr[ A] 
1
1 2

w xexp  4 r ( A, ( x, w ))  Pr[ B]  2  Pr[ B]   Pr[ A] x(2  x)
x  Pr[ A] / Pr[ B]  [0,1]
x(2-x)1からn+1についても定理が成り立つ。
以上より、帰納法から証明終了。
• あああ

Download Report