Document

7. Martingales and
Tight Concentration
7.1: Definitions
7.2: Large Deviations
7.1 Definitions
マルチンゲールとは、ランダムな変数列
X1,…,Xm であって、
E[Xi+1 | Xi,Xi–1,…,X0] = Xi
を満たすものを言う。
★ X0,…,Xi までがわかったとき、Xi+1の条件
付期待値が Xi と等しくなるようなもの。
公平なギャンブル



公平なギャンブルとは、1 ゲームの収支
の期待値が 0 になるようなものを言う。
次のゲームをした後の所持金の期待値
は、過去の履歴 (X0,…,Xi–1) によらず、現
在の所持金 (Xi) に等しい。
↓
所持金の推移はマルチンゲールになる。
例：コイン投げ




裏表を当てると所持金 +1、外すと –1
1 ゲームごとの収支期待値は当然 0
ゲーム後の所持金の期待値はゲーム前
の所持金の期待値に等しい
→マルチンゲール
所持金は二項分布に従う
枝公開マルチンゲール





グラフ G の枝を隠す(頂点は見える)。
すべての頂点の組について、順番に枝が
あるかどうかの情報を公開していく。
それまでに公開された i 個の枝情報を含
むグラフを H で表す。
グラフに関する任意の特徴量 Xi(H) は、
公開された情報の数 i についてマルチン
ゲールになる。
Xi は未公開枝についての期待値をとる。
例：特徴量 f(H) = 彩色数
?
②
③
?
?
①
?
有
X1(H)
= 2.25
?
?
?
X0(H)
= 2 平均
無
X1(H)
= 1.75
有
?
有
X2(H)
= 2.5
無
有
X2(H)
=2
無
有
有
X3(H)
=2
?
無
無
有
X3(H)
=2
例：特徴量 f(H) = 彩色数
2.5
3
2.25
2
2
2
2
2
2
2
2
1.75
X0
X1
2
1.5
X2
1
X3
頂点公開マルチンゲール





グラフ G の枝を隠す(頂点は見える)。
各頂点について、それまでに公開された
頂点との間に枝があるか公開していく。
それまでに公開された i 個の頂点情報を
含むグラフを H で表す。
グラフに関する任意の特徴量 Xi(H) は、
公開された情報の数 i についてマルチン
ゲールになる。
Xi は未公開頂点についての期待値をとる。
例：特徴量 f(H) = 彩色数
3
2.25
2
2
2
2
2
2
2
1.75
2
1
X0
X1
X2
X3
7.2 Large Deviations




定理 7.2.1
系 7.2.2
定理 7.2.3
定理 7.2.4
A.1.1
X0,…,Xn を独立とし、
Pr[Xi = +1] = 1/2, Pr[Xi = –1] = 1/2,
Sn = X0+…+Xn
 a 2 2n
とするとき、 PrS n  a  e
(証明略)
A.1.16
X0,…,Xn を独立とし、
E[Xi] = 0, |Xi| ≦ 1,
Sn = X0+…+Xn
とするとき、   a n とおくと
PrS n  a  cosh    e
(証明略)
 2 2
定理 7.2.1
X0,…,Xm をマルチンゲール、X0 = 0 とし、
|Xi+1–Xi| ≦ 1
が 0 ≦ i < m について成り立つとする。
l > 0 を任意に選ぶとき、次が成り立つ。


Pr X m  l m  e
(Azumaの不等式)
l2 2
定理 7.2.1
証明：   l m とおく。 Yi = Xi – Xi–1 とする
と、仮定より |Yi| ≦ 1 であり、
E[Yi | Xi–1,Xi–2,…,X0] = 0 が成り立つ。




e e
max E e | X i 1 , X i 2 ,, X 0 
 cosh  
Yiの分布
2
(確率 0.5 で Yi = ±1 の分布で最大) なので、
Yi

Yi
Ee

| X i 1 , X i 2 ,, X 0  cosh    e
2 2
定理 7.2.1
   Ee
 Ym Ym1 Y1 
X m
より、 E e
  E
 e Ee | X , X
 E  e e    e
E
m 1 Y
i
Ym
i 1
m 1 Y
i
従って、

m 1
2 2
 e
Ee
i 1
m2
Yi
e

, , X 0

 2m 2
i 1
 
Pr X m  l m  Pr eX m  el
X m
m
l m
 2 m 2 l m
e
m
e
 l

l2 2 l2
m
e
 l2 2
■
Markov Bound
X > 0 のとき
EX 
PrX  t  
t
系 7.2.2
X0,…,Xm をマルチンゲール、X0 = c とし、
|Xi+1–Xi| ≦ 1
が 0 ≦ i < m について成り立つとする。
このとき、次が成り立つ。


Pr X m  c  l m  2e
l2 2
※初期値が 0 でない場合に拡張しただけ。
グラフ特徴量のリプシッツ条件
グラフ上の特徴量 f について、枝 1 本だけ
異なる 2 つのグラフ H,H’ において
| f(H)–f(H’)| ≦ 1
が成り立つとき、f は枝リプシッツ条件を満
たすという。同様に、頂点 1 個だけ異なる 2
つのグラフ H,H’ において上式が成り立つと
き、頂点リプシッツ条件を満たすという。
定理 7.2.3
f が枝リプシッツ条件を満たすとき、これに
対応する枝公開マルチンゲールは
|Xi+1–Xi| ≦ 1 を満たす。
f が頂点リプシッツ条件を満たすとき、これ
に対応する頂点公開マルチンゲールは
|Xi+1–Xi| ≦ 1 を満たす。
証明：のちのセクションで。
定理 7.2.3
直感的には、1 本の枝あるいは 1 個の頂点
の存在が、グラフの特徴量 f に ±1 以上影
響しないとすると、枝・頂点をひとつ「公開」
したとしても、前後の f の期待値は ±1 以
上変化しない、ということが言えそうである。
次は定理 7.2.1, 7.2.3 の応用例↓
定理 7.2.4
n,p を任意にとり、c = E[c(G)] とする。
ただし、G ~ G(n,p) は頂点数 n、各頂点間
に確率 p で枝を張ったランダムグラフであり、
c(G) は G の彩色数を表す。
このとき、
l2 2
Pr c G   c  l n  1  2e
が成り立つ。


定理 7.2.4
証明：頂点公開マルチンゲール X1,…,Xn を
考え、f(G) = c(G) とする。c(G) は、頂点を 1
個追加するたびに高々 1 色増やせば彩色
可能なので、頂点リプシッツ条件を満たす。
Azumaの不等式を系 7.2.2 の形で適用すれ
ば、直ちに証明が完了する。■
定理 7.2.4
l と任意にゆっくりと発散させるとき、こ
の結果は c(G) が期待値付近に固まってい
る (tightly concerned) ことを示す。しかし、上
記の証明は期待値がどこにあるかというこ
とについて一切ふれていない。

Download Report