定理 7.8.1 の応用

7.8 Kim-Vu Polynomial
Concentration
Iwama Lab. M2
Masakazu Kadoshita
発表の内容




導入
定理7.8.1のアイデア
定理7.8.1の証明
定理7.8.1の応用
発表の内容




導入
定理7.8.1のアイデア
定理7.8.1の証明 ← 省略
定理7.8.1の応用
Reference

J. H. Kim, and V. H. Vu. “Concentration
of Multivariate Polynomials and Its
Applications,” Combinatorica, Vol. 20,
pp. 417-434, (2000)
The goal

Y,t1,t2,…,tn : 確率変数
Y : 正係数多変数多項式

Yが平均付近に集中している

– 確率Pr( |Y-E[Y]| > λ)が小さい
The Number of Triangles


G(n,p): ランダムグラフ
: {0,1}の2値を取る確率変数
– ij間に枝があればtij=1, otherwise tij=0
– E[tij]=p

Y : G上の三角形の個数


枝公開マルチンゲール
Gの枝eを取ると最悪Yの値が(n-2)変化する
– Azumaの不等式が使えない

言い換えると
– Pr[ |Y-μ| > λ] < exp(-λ2/(∑ijdworst)2)

Azumaの不等式(chap7.2)の別バージョン
– Yの平均はO(p3n3)=O(n3（1-α))
– α>2/3では不等式がうまく動かない

λ=ω(n) , μ=O(n1-ε)
準備

ハイパーグラフH=(V(H), E(H))
– V(H)={1,2,…,n}
– E(H)={{1,3,4},{2,3,4,5},{6},…,{v1,…,vk}}
2
1
6
3
4
5
n

確率変数 ti (i=1,2,…,n)
– 条件 ( 1 ) , ( 2 ) どちらかを満たす
( 1 ) ti = {1,0} かつ E[ti] = pi
( 2 ) 確率 1 で ti = pi
– e.g. n個のコインを投げる
コインiが表 ⇒ ti = 1
 otherwise ti = 0
 表が出る確率がpi


部分集合 S ⊆ V(H)
– コイン i が表ならば S に頂点 i を加える

確率変数
– H[S]に枝eがある⇒
– Otherwise
–

重み w は負でない実数

確率変数 Y
– e.g. V(H)={1,2,3}, E(H)={{1,2},{3},φ}

H[S]に価値の高い枝が含まれる
⇒Yが大きくなる
Truncated
Subhypergraphs



‘truncated’ [形] 先端を切った;一部を切
り詰めた (GENIUS 英和辞典改訂版)
部分集合 A⊆V(H)
HA : HのA-truncated subhypergraph



Example of Truncated
Subhypergraphs


HA : HのA-truncated subhypergraph
e.g.
– V(H)={1,2,3}, E(H)={{1,2},{3},φ}
– A={1}
⇒V(HA)={2,3}, E(HA)={{2}}
特にA=φ
⇒ V(HA)={1,2,3}=V(H),
E(HA)={{1,2},{3},φ}=E(H)

HAに対して確率変数YHAを同様に定義

– e.g. V(H)={1,2,3}, E(H)={{1,2},{3},φ}, A={1}
– 遍導関数になっている(任意のAで)

EA=E[YHA] : YHA の期待値
– EAはSに頂点Aがすべて含まれるときの、Aを含むS
の枝の重みの総和の条件つき期待値
– e.g. V(H)={1,2,3}, E(H)={{1,2},{3},φ}, A={1},

|A|=iなるAでEAが極大になるAを選ぶ
定理7.8.1

[Kim-Vu Polynomial Concentration]
– 任意のλ>1に対して
– 言い換えると
定理の背景あるアイデア(1)

EA=E[YHA] : YHA の期待値
– EAはSにある枝で、Aを含む枝の重みの総和
の期待値
– あるAでEAがYの期待値にほぼ等しいならば
A以外の頂点はYに影響を与えにくい
 AがSに含まれる時、そうでないときのYの値の差
が大きくなる

定理の背景あるアイデア(2)
– 正値係数の多変数多項式で表現された確率
変数Y
– Yの任意の遍導関数YHAの期待値がYの期待
値より真に小さい
⇒Yは平均付近に集中している
平均に集まっていない例
– e.g. V(H)={1,2,3,4},
E(H)={φ,{1},{1,2},{1,3},{1,4},{1,2,3},{1,2,4},
{1,3,4},{1,2,3,4}}, A={1}
– tiは確率1/2で1,確率1/2で0の値をとる
– we=1
t4t3t2t1
0000
0001
0010
0011
0100
0101
0110
0111
Y
1
2
1
3
1
3
1
5
t4t3t2t1
1000
1001
1010
1011
1100
1101
1110
1111
Y
1
3
1
5
3
5
5
9
度数分布(1)
7
6
5
4
3
2
1
0
1
2
3
4
5
6
7
8
9 10
平均に集まっている例
– e.g. V(H)={1,2,3}, E(H)={φ,{1},{2},{3},{4}},
A={1}
– tiは確率1/2で1,確率1/2で0の値をとる
– we=1
t4t3t2t1
0000
0001
0010
0011
0100
0101
0110
0111
Y
1
2
2
3
2
3
3
4
t4t3t2t1
1000
1001
1010
1011
1100
1101
1110
1111
Y
2
3
3
4
3
4
4
5
度数分布(2)
7
6
5
4
3
2
1
0
1
2
3
4
5
6
定理7.8.1(再掲)

[Kim-Vu Polynomial Concentration]
– 任意のλ>1に対して
– 言い換えると
定理7.8.1の証明



kについての帰納法
定理7.4.3で示したマルチンゲールに関す
る不等式の証明と同様
補題とあわせて6 pages
定理7.8.1の応用

kを固定,λ>>log n
The Number of
Triangles(再掲)



G(n,p): ランダムグラフ
: {0,1}の2値を取る確率変数
Y : G上の三角形の個数
A Sample Example in the
Thesis

定理7.8.1で枝eを三角形に制限したと
思って適用
– i.e. k=3

E,E’を計算する

E0,E1,E2,E3を計算する.
2
1
6
3
4
5
|A|=1の例

n
定理7.8.1の応用

定理7.8.1

k=3,λ=ω(log n)
An Example in Textbook

G=(n,p), 三角形の個数に関する問題
– p=nε-1, 1/3<ε<1


Gの頂点xをひとつ固定
確率変数Yx: 頂点xを含む三角形の個数


あるδが存在して以下の確率が小さくなることを示す

E’=max[np2,1]=max[n2ε-1,1]
– E’ ~ cμn-ε
– μ~n3ε-1を使った

E=max [μ, E’]

定理7.8.1

k=3,λ=c’nε/6

Download Report