Probabilistic Method 2007/11/02 岩間研究室M1 市場孝之
「おおよそ独立な」事象の生起回数をXとすると、 8.3 BRUN's SIEVE 本節の内容 Brun’s Sieve の証明 Brun’s Sieve, Janson Inequality両方を用いた証明 ポアソンパラダイムの１つのアプローチ 「おおよそ独立な」事象の生起回数をXとすると、 Xはポアソン分布で近似できる。 μ=E[X]とすれば
Brun’s SieveとJanson Inequality 「おおよそ独立」の定義が異なる Janson Inequality Δ: 独立でないBi, Bjのペアの内、 同時生起する数の期待値 ε: Biの生起確率の上界 Brun’s Sieve 同時生起するk-tupleの数が，独立な場合の数と近似的に等しい
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についての極限
Theorem 8.3.1 (Brun's Sieve)
Inclusion-Exclusion Principle とおくと (s : odd) Bonferroni Inequialies (s : even) B A∧B B∧C A∧B∧C A C A∧C
Simplify the probability を示す．
proof of theorem 8.3.1 任意にε>0を決め，次式を満たす s を選ぶ． また，ε，s，0≦r≦2sに対し次式を満たすn0を選ぶ．
proof of theorem 8.3.1 したがってn≧n0において、 同様に 2s+1までの和を考えれば、 (証了)
Application Janson InequalityとBrun’s Sieve両方を使った証明 に対し であれば, に対し Brun’s Sieve であれば,
Random graph G~G(n,p) : 頂点数 n 任意の2頂点間に枝がある確率 p であるグラフ
Theorem 8.3.2 c >0 について p, μを次式を満たすよう定める このとき
Outline of proof 1-1. を証明. 1-2. を証明. 2. を証明. Bxyz : xyzが三角形であるという事象 Cx : xを含む三角形がないという事象 1-1. を証明. 1-2. を証明. 2. を証明. 1-2, 2よりBrun's Sieveの前提が満たされるので、 Yx : xを含む三角形の個数 X : 三角形に含まれない点の個数 (Janson 不等式より) (Janson 不等式より)
1-1. の証明 x∈V(G)を固定 Janson不等式を利用 Pr[Bxyz]=p3, よってε=o(1) であるとき, に対し より,
1-1. の証明 z=v y Bxyz～Bxuv であれば、x以外の1点でも重複 (Yx : xを含む三角形の個数) したがって u x
1-2. の証明 1-1.より
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不等式を利用
2. の証明 Janson不等式 Y : の生起数(1≦i≦r, ∀y,z) 1-1.と同様に , したがって であるとき, に対し
2. の証明 Bxiyz～Bxjy’z’ であれば、2つの点が重複 i=jの場合 i≠jの場合 ペアの数を数える(点の取り方×重ね方) 2. の証明 Bxiyz～Bxjy’z’ であれば、2つの点が重複 ペアの数を数える(点の取り方×重ね方) i=jの場合 i≠jの場合 したがって z=v y u xi=xj
2. の証明 Bxiyzの数は したがって xixjz : 重複して数えている (証了)