定理 7.4.1

7.4 Two General Settings
D3 杉原堅也
7.4 節の内容



定理 7.4.1
定理 7.4.2
定理 7.4.3
この節でやることを大雑把に言うと，
ランダムグラフ G(n, p) を一般化したもの（正確にはもっと一
般的なものを扱う）を対象として、マルチンゲールを定義し、2
つの不等式を紹介する．
定義 1

A, B をある集合とし，
  AB を関数 g : B → A の集合とする．

g(b) の確率を
Pr[ g (b)  a]  pab とし，互いに独立とする．
例： A = {0, 1}, B をグラフG (節点数n) の節点ペアの集合，
とすれば， g ∈ AB は n節点のグラフとみなせる．
g(vw)=1
g(wx)=1
w
x g(xv)=0
全ての節点ペア b ∈ B で p1b = p, p0b = 1－ p とすれば，
g はランダムグラフ G(n, p).
A = {0, 1}
B = {vw, wx, xv}
v
B1
B2
定義 2


B3
B4
gradation   B0  B1    Bm  B を固定，
L : AB   を汎関数（e.g., クリーク数）とする．
マルチンゲール X 0 , X 1 ,, X m を次のように定義．
X i (h)  E[ L( g ) | b  Bi , g (b)  h(b)].
A
b ∈ Bi で g(b)=h(b)
B
X 0 = E[L(g)] : 定数．
b ∈ Bi+1 で g(b)=h(b)
X m(h) = L(h) ．
Xi(g) の値は g(b) が「公開される」につれて L(g) に近づく．
B1
B2
定義 2


B3
B4
gradation   B0  B1    Bm  B を固定，
L : AB   を汎関数（e.g., クリーク数）とする．
マルチンゲール X 0 , X 1 ,, X m を次のように定義．
X i (h)  E[ L( g ) | b  Bi , g (b)  h(b)].
A
B
b ∈ Bi で g(b)=h(b)
b ∈ Bi+1 で g(b)=h(b)
Xi の値は b ∈ Bi だけが寄与する．
Xi+1 の値は b ∈ Bi+1－ Bi の寄与が新たに加わる．
リプシッツ条件

汎関数 L の，gradation   B0  B1    Bm  B
に関するリプシッツ条件．
全ての 0  i  m に対し，
h, h’ が Bi 1  Bi 上でのみ異なる  | L(h' )  L(h) | 1
定理 7.4.1

定理 7.4.1
L が   B0  B1    Bm  B に関するリプシッツ条
件を満足するとき，対応するマルチンゲールは
全ての 0  i  m, h  AB で，
| X i 1 (h)  X i (h) | 1.
系 7.2.2 （前回のスライド）
X0,…,Xm をマルチンゲール、X0 = c とし、
|Xi+1–Xi| ≦ 1
が 0 ≦ i < m について成り立つとする。
このとき、次が成り立つ。


Pr X m  c   m  2e
2 2
定理 7.4.1（証明）

X i (h)  E[ L( g ) | b  Bi , g (b)  h(b)].
H: b ∈ Bi+1 で h’(b) = h(b) となる
h’ ∈ AB の集合.
h
H
AB
wh’ を条件付き確率とすると
(条件は，b ∈ Bi+1 で h(b) = g(b))，
（つまり，
wh  Pr[ g  h | b  Bi 1 , g (b)  h）(b)]
X i 1 (h) 
 L(h)w
hH
h
定理 7.4.1（証明）

X i (h)  E[ L( g ) | b  Bi , g (b)  h(b)].
H: b ∈ Bi+1 で h’(b) = h(b) となる
h’ ∈ AB の集合.
h
H
AB
h
H[h’]: b ∈ Bi で h’(b) = h*(b) となる
h*の集合．
H[h’]
qh* を以下の条件付き確率とすると，
qh*  Pr[ b  Bi 1 , g (b)  h * (b) | b  Bi , g (b)  h(b)]
X ( h)     L ( h ) q  w

i
hH hH [ h ]
wh  Pr[ g  h | b  Bi 1 , g (b)  h(b)]
h
h
qh* wh  Pr[ g  h* | b  Bi , g (b)  h(b)]
qh* wh
 Pr[ g  h | b  Bi 1 , g (b)  h(b)] Pr[ b  Bi 1 , g (b)  h * (b) | b  Bi , g (b)  h(b)]
 Pr[ g  h* | b  Bi 1 , g (b)  h * (b)] Pr[ b  Bi 1 , g (b)  h * (b) | b  Bi , g (b)  h(b)]
Pr[ b  Bi 1 , g (b)  h * (b)  b  Bi , g (b)  h(b)]
 Pr[ g  h* | b  Bi 1 , g (b)  h * (b)]
Pr[ b  Bi , g (b)  h(b)]

Pr[ g  h *  b  Bi 1 , g (b)  h * (b)] Pr[ g  h *  b  Bi , g (b)  h * (b)]



Pr[ b  Bi , g (b)  h(b)]
Pr[ b  Bi , g (b)  h(b)]
 Pr[ g  h* | b  Bi , g (b)  h * (b)]
Pr[ A | B] Pr[ B | C ]
A B C
Pr[ A | B] Pr[ B | C ]  Pr[ A | C ]
qh*  Pr[ b  Bi 1 , g (b)  h * (b) | b  Bi , g (b)  h(b)]
wh  Pr[ h | b  Bi 1 , g (b)  h(b)]
定理 7.4.1（証明）



| X i 1 (h)  X i (h) |  wh  L(h)   L(h )qh 
hH


hH [ h ]

 wh
hH

hH [ h ]


qh L(h)  L(h ) .
h’ と h* は Bi+1－Bi 上でのみ異なるので，
仮定からリプシッツ条件 | L(h)  L(h*) | 1 が成立．
| X i 1 (h)  X i (h) |
X i 1 (h) 
w q
hH
 L(h)wh
hH
h
h
hH [ h ]

w
hH
X i ( h) 
h
1
   L( h ) q  w


hH h H [ h ]
h
h
定理 7.4.2

定理 7.4.2
  E[ L( g )] とおく．
L がリプシッツ条件を満足するとき，
全ての   0 で，


PrL( g )     m   e
Pr L( g )     m  e
 2 / 2
 2 / 2
,
.
X m  L( g )
X 0    EL( g )
定理 7.2.1（前回のスライド）
X0,…,Xm をマルチンゲール、X0 = 0 とし、
|Xi+1–Xi| ≦ 1
が 0 ≦ i < m について成り立つとする。
 > 0 を任意に選ぶとき、次が成り立つ。


Pr X m   m  e
(Azumaの不等式)
2 2
系 7.2.2 （前回のスライド）
X0,…,Xm をマルチンゲール、X0 = c とし、
|Xi+1–Xi| ≦ 1
が 0 ≦ i < m について成り立つとする。
このとき、次が成り立つ。


Pr X m  c   m  2e
2 2
※初期値が 0 でない場合に拡張しただけ。
準備
Alonら(1997)による本発表2つ目の設定．
 確率空間を有限で独立な Yes/No choice とする．
indexを i ∈ I．
 choice i は確率 pi で Yes．
 この確率空間上の確率変数 Y が与えられる．
・ I: 質問の有限集合.
・質問 i ∈ I をオラクルに投げると確率 pi で Yes. (choice)
・各質問の答えがYes/Noとなる確率は互いに独立．
・質問の答えによって決まる値が Y.
準備




i 以外の質問の答えを固定した時，質問 i の答えが
反転しても Y は高々 ci だけ増減するとする．
ci を i の effect と呼ぶ．
C を全ての ci の上界とする．
2
pi (1  pi )ci を choice i の分散とよぶ．
Solitaire Game


ソリティアゲーム
－ 1人で遊ぶゲーム (e.g., パズル，クロンダイク)
Paul はある値 Y を見つけるため，（いつも正しく答えを返す）
オラクルに質問 i ∈ I を投げる．
－ Paul は前の質問に依存した質問を選んでよい．
－ Paul の戦略は決定木で表せる．
root
3
Yes
1つのパスに対してY の値が1つ決まる
パス（line of questioning）が含むchoice i の分散の合計を
そのline of questioning の分散とよぶ．
No
2
Yes
3
Yes
1
No
Yes
4
No
定理 7.4.3

定理 7.4.3
全てのε> 0 に対し，以下が成り立つようなδ> 0 が存在する．
Paul の戦略において，任意のline of questioningの分散が高々
σ2 のとき，全ての α> 0 に対し，
Pr | Y  E[Y ] |     2e
ただし，α (> 0) は
2

 2 (1 )
C   (1   ) を満たす．
.
定理 7.4.3 の応用
Pr | Y  E[Y ] |     2e

2
 2 (1 )
,
C   (1   )
ε= δ = 1とする．
C = O(1) のとき，α→∞ かつ α= o(σ) とすれば，
右辺は exp[ ( 2 )].
定理 7.4.3 の応用
Pr | Y  E[Y ] |     2e

2
 2 (1 )
,
C   (1   )
たいてい Paul は全ての i ∈ I を質問するので，  2  iI pi (1  pi )ci2
ランダムグラフ G(n, p) 上で枝リプシッツ条件を満たす Y を考
える．ただし，p = p(n) → 0 とする．
n
I を m    個の節点ペアに枝があるかない(Yes/No)とし，
 2
全ての pi = p （ランダムグラフ）, C = 1 （リプシッツ条件）なので，
  ( n 2 p ).
このとき，α→ ∞，   o( n p ) ならば，右辺は
2
exp[ ( )].
2
グラフ特徴量のリプシッツ条件
（前回のスライド）
グラフ上の特徴量 f について、枝 1 本だけ
異なる 2 つのグラフ H,H’ において
| f(H)–f(H’)| ≦ 1
が成り立つとき、f は枝リプシッツ条件を満
たすという。同様に、頂点 1 個だけ異なる 2
つのグラフ H,H’ において上式が成り立つと
き、頂点リプシッツ条件を満たすという。
定理 7.4.3 (再褐)

定理 7.4.3
全てのε> 0 に対し，以下が成り立つようなδ> 0 が存在する．
Paul の戦略において，任意のline of questioningの分散が高々
σ2 のとき，全ての α> 0 に対し，
Pr | Y  E[Y ] |     2e
ただし，α (> 0) は
2

 2 (1 )
C   (1   ) を満たす．
.
定理 7.4.3 （証明）





簡単のため E[Y] = 0 とする．
また，upper tailを示す．つまり， Pr
   /[ (1   )] とおくと，
C   (1   ) は C   ．
  e
以降， E e
なぜなら，
Y
(1 ) 2 2 / 2
Pr Y     Pr[e  e
Y

 Y     e
(7.2)
]e
2
 2 (1 )
を示す．
を示せばよい．
 
Y
E[e ]  e
Markov Bound
EX 
X  0, PrX  t  
t
 2 / 2 (1 )
.
定理 7.4.3 （証明）

まず次のことを示す．
全てのε> 0 に対し，δ> 0 が存在して，
0 ≦ p ≦ 1 と |a|≦ δ に対し，
pe
(1 p ) a
 (1  p)e
 pa
e
(1 ) p (1 p ) a 2 / 2
.
左辺を a に関してテイラー展開．（左辺） = 1 + 0 + a2p(1－p)/2 + ・・・
aj ( j ≧3 ) の係数は，高々
1
j!
p(1  p)[ p j 1  (1  p) j 1 ] 
a j  a2
 を満たすように取ると，

2
j 3 j!

δを， |a| ≦δが
pe
(1 p ) a
 (1  p)e
 pa
 1  p(1  p)
1 + x ≦ ex を使って右辺を得る．
a2
2
(1   )
1
j!
p(1  p).
定理 7.4.3 （証明）



決定木の深さに関する数学的帰納法で(7.2)を示す．
M = 0 のとき，Y は定数なので成立．
Paul の最初の質問に対して，
p: 確率，c: effect，v = p(1－p)c2 を分散とする．
また，μy, μn を最初のオラクルがYes/Noを返すときの Y の条
件付き期待値とする．
・ E[Y] = 0 なので，0 = pμy + (1－p)μn.
root
・ effect の定義から，|μy －μn|≦ c.
Yes
No
・パラメータ b (|b| ≦ c) を用いて，
μy
μn
Yes
No
μy = (1－p)b, μn = －pb とかく．
 
E eY  e(1 ) 
2
2
/2
(7.2)
Yes
Yes
No
No
定理 7.4.3 （証明）


μy = (1－p)b, μn = －pb．
2
先に示した pe(1 p ) a  (1  p)e  pa  e(1 ) p (1 p ) a / 2
pe
 y
 (1  p)e
 n
 pe(1 p ) b  (1  p)e  pb
e
pe
 y
 (1  p)e
 n
e
(1 ) p (1 p ) b 2 2 / 2
(1 ) v2 / 2
e
(1 ) v2 / 2
.
.
root
μy
Yes
 
E eY  e(1 ) 
2
2
/2
から，
(7.2)
Yes
Yes
No
No
Yes
No
No
μn

Ay  E e
定理 7.4.3 （証明）





An  E e  (Y  n )


Ay をオラクルがYesを返したときの e λ(Y－μy) の条件付き期待
値とする．(E[ Y－μy | Yes ] =0.)
An をオラクルがNoを返したときの e λ(Y－μn) の条件付き期待
値とする．(E[ Y－μn | No ] =0.)
Yes/Noが帰ってきたとき，部分木に関して Y の分散は高々
σ2－ v，深さは M－1．
帰納法の仮定から，
Ay , An  A : e (1 )  (
2
2
root
v ) / 2
μy
Yes
  e
E e
 (Y   y )
Y
(1 ) 2 2 / 2
(7.2)
Yes
Yes
No
No
Yes
No
No
μn
定理 7.4.3 （証明）

Ay  E e
Y
E[e ]  pe

 y
 pe
e
 (1  p )e
(1 ) 2 ( v  ( 2  v )) / 2

Ay , An  A  e
pe
 y

An  E e  (Y  n )
Ay  (1  p)e  n An
 y
 (1  p)e
 n
A
e
  e
E e

(1 ) 2 2 / 2
.
(1 ) 2 ( 2 v ) / 2
 n
(1 ) 2 2 / 2


root
e
(1 ) v2 / 2
μy
.
Yes
Y
 (Y   y )
(7.2)
Yes
Yes
No
No
Yes
No
No
μn

Download Report