Probabilistic Method 2007/11/02 岩間研究室M1 市場孝之.

Presentation on theme: "Probabilistic Method 2007/11/02 岩間研究室M1 市場孝之."— Presentation transcript:

1 Probabilistic Method 2007/11/02 岩間研究室M1 市場孝之

2 「おおよそ独立な」事象の生起回数をXとすると、
8.3 BRUN's SIEVE 本節の内容 Brun’s Sieve の証明 Brun’s Sieve, Janson Inequality両方を用いた証明 ポアソンパラダイムの１つのアプローチ 「おおよそ独立な」事象の生起回数をXとすると、 Xはポアソン分布で近似できる。 μ=E[X]とすれば

3 Brun’s SieveとJanson Inequality
「おおよそ独立」の定義が異なる Janson Inequality Δ: 独立でないBi, Bjのペアの内、 　　　同時生起する数の期待値 ε: Biの生起確率の上界 Brun’s Sieve 　 同時生起するk-tupleの数が，独立な場合の数と近似的に等しい

4 Definition B1, …, Bm 事象 X1, …, Xm 指示関数 X=∑Xi Biの生起数 n hidden parameter
m, Xi, Xがnによって定まるとする ( m=m(n), Xi=Xi(n), X=Xi(n) ) 以下で考えるのはmではなくnについての極限

5 Theorem (Brun's Sieve)

6 Inclusion-Exclusion Principle
とおくと (s : odd) Bonferroni Inequialies (s : even) B A∧B B∧C A∧B∧C A C A∧C

7 Simplify the probability
を示す．

8 proof of theorem 8.3.1 任意にε>0を決め，次式を満たす s を選ぶ．
また，ε，s，0≦r≦2sに対し次式を満たすn0を選ぶ．

9 proof of theorem 8.3.1 したがってn≧n0において、 同様に 2s+1までの和を考えれば、 (証了)

10 Application Janson InequalityとBrun’s Sieve両方を使った証明 に対し
であれば, に対し Brun’s Sieve であれば,

11 Random graph G~G(n,p) : 頂点数 n 任意の2頂点間に枝がある確率 p であるグラフ

12 Theorem 8.3.2 c >0 について p, μを次式を満たすよう定める このとき

13 Outline of proof 1-1. を証明. 1-2. を証明. 2. を証明. Bxyz : xyzが三角形であるという事象
Cx : xを含む三角形がないという事象 を証明. を証明. を証明. 1-2, 2よりBrun's Sieveの前提が満たされるので、 Yx : xを含む三角形の個数 X : 三角形に含まれない点の個数 (Janson 不等式より) (Janson 不等式より)

14 の証明 x∈V(G)を固定 Janson不等式を利用 Pr[Bxyz]=p3, よってε=o(1) であるとき, に対し より,

15 の証明 z=v y Bxyz～Bxuv であれば、x以外の1点でも重複 (Yx : xを含む三角形の個数) したがって u x

16 の証明 1-1.より

17 2. の証明 r を固定 (2行目の{x1, ..., xr}⊂V(G)は適当な頂点) (右辺は1≦i≦r, ∀y,zについての積)
2. の証明 r を固定 (2行目の{x1, ..., xr}⊂V(G)は適当な頂点) (右辺は1≦i≦r, ∀y,zについての積) ここで についてJanson不等式を利用

18 2. の証明 Janson不等式 Y : の生起数(1≦i≦r, ∀y,z) 1-1.と同様に , したがって であるとき, に対し

19 2. の証明 Bxiyz～Bxjy’z’ であれば、2つの点が重複 i=jの場合 i≠jの場合 ペアの数を数える(点の取り方×重ね方)
2. の証明 Bxiyz～Bxjy’z’ であれば、2つの点が重複 ペアの数を数える(点の取り方×重ね方) i=jの場合 i≠jの場合 したがって z=v y u xi=xj

20 2. の証明 Bxiyzの数は したがって xixjz : 重複して数えている (証了)