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)変化する 言い換えると 枝公開マルチンゲール 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 n 4 5

確率変数 ti (i=1,2,…,n) 条件 ( 1 ) , ( 2 ) どちらかを満たす e.g. n個のコインを投げる ( 1 ) ti = {1,0} かつ E[ti] = pi ( 2 ) 確率 1 で ti = pi e.g. n個のコインを投げる コインiが表 ⇒ ti = 1 otherwise ti = 0 表が出る確率がpi

部分集合 S ⊆ V(H) 確率変数 重み w は負でない実数 コイン 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}

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の期待値より真に小さい

平均に集まっていない例 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 Y 0000 1 0001 2 0010 0011 3 0100 0101 0110 0111 5 t4t3t2t1 Y 1000 1 1001 3 1010 1011 5 1100 1101 1110 1111 9

平均に集まっている例 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 Y 0000 1 0001 2 0010 0011 3 0100 0101 0110 0111 4 t4t3t2t1 Y 1000 2 1001 3 1010 1011 4 1100 1101 1110 1111 5

定理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 i.e. k=3 E,E’を計算する

E0,E1,E2,E3を計算する. 2 1 6 3 n 4 5 |A|=1の例

定理7.8.1の応用 定理7.8.1 k=3,λ=ω(log n)

An Example in Textbook G=(n,p), 三角形の個数に関する問題 Gの頂点xをひとつ固定 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