chap8.3

Probabilistic Method
2007/11/02
岩間研究室M1
市場孝之
8.3 BRUN's SIEVE
本節の内容
 Brun’s Sieve の証明
 Brun’s Sieve, Janson Inequality両方を用いた証明
ポアソンパラダイムの１つのアプローチ
「おおよそ独立な」事象の生起回数をXとすると、
Xはポアソン分布で近似できる。
μ=E[X]とすれば
Pr [X = t ] ø
öt à ö
t! e
Brun’s SieveとJanson Inequality
「おおよそ独立」の定義が異なる
 Janson Inequality
ð
Δ: 独立でないBi, Bjのペアの内、 É =
同時生起する数の期待値
P
iøj
ñ
Pr [B i ^ B j ]
ε: 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)
n  において，
E[ X ]   , かつ全ての rについて，
S
(r )
  / r!
r
であれば，
Pr[ X  0]  e

t

 
 
 Pr[ X  t ]  e , t 
t!


が成り立つ．
Inclusion-Exclusion Principle
(r )
S =
P
Pr [B i 1 ^ ááá^ B i r ] とおくと
(i 1;:::;i r ) ò N
Pr [B 1 _ ááá_ B n] = S(1) à S(2) + ááá+ (à 1) n à 1S(n)
Pr [B 1 _ ááá_ B n ] ô
Pr [B 1 _ ááá_ B n ] õ
Ps
(à 1) r à 1S(r )
r= 1
Ps
(à 1) r à 1S(r )
r= 1
jA _ B _ Cj ô jAj + jBj + jCj
ð
(s : odd)
Bonferroni Inequialies
(s : even)
ñ
jA _ B _ Cj õ jAj + jBj + jCj à jA ^ Bj + jB ^ Cj + jC ^ Aj
ð
ñ
jA _ B _ Cj = jAj + jBj + jCj à jA ^ Bj + jB ^ Cj + jC ^ Aj
+ jA ^ B ^ Cj
B
A∧B
B∧C
A∧B∧C
A
A∧C
C
Simplify the probability
Pr [X = 0] = Pr [B 1 ^ ááá^ B m]
= 1 à Pr [B 1 _ ááá_ B m]
= 1 à S(1) + S(2) à ááá+ (à 1) mS(m)
Pm
Pr [X = 0] = (à 1) r S(r )
r= 0
Pr [X = 0] ô
Pr [X = 0] õ
P2k
(à
r= 0
2k+
P1
1) r (r )
S
ô eà ö + ï
(à 1) r S(r ) õ eà ö à ï
r= 0
を示す．
proof of theorem 8.3.1
任意にε>0を決め，次式を満たす s を選ぶ．
ì P2s
ì
ðP
ñ
1
r
ì
ì
r
ì (à 1) r áör ! à eà ö ì ô 2ï
(à 1) r áöt! = eà ö
r= 0
P2s
r= 0
(à
r= 0
ör
r
1) ár !
ô eà ö +
ï
2
また，ε，s，0≦r≦2sに対し次式を満たすn0を選ぶ．
ì
ì
ð
ñ
r
ì (r ) ö ì
ï
(r ) !
r !
lim
ì S à r ! ì ô 2(2s+
S
ö
=r
1)
n! 1
(r )
S
ô
ör
r!
+
ï
2(2s+ 1)
(r )
à S
ô à
ör
r!
+
ï
2(2s+ 1)
proof of theorem 8.3.1
P2s
(à
r= 0
ör
r
1) ár !
àö
ô e +
ï
2
(r )
S
ô
ör
r!
+
ï
2(2s+ 1)
(r )
à S
ô à
ör
r!
+
ï
2(2s+ 1)
したがってn≧n0において、
Pr [X = 0] ô
P2s
(à 1) r S(r ) = S(0) à S(1) + S(2) à ááá
r= 0
ô (1 à
=
P2s
ö
ö2
1! + 2! à
ááá) +
ör
ár !
+ 2ï ô
(à
r= 0
1) r
ï
2(2s+ 1) á(2s +
1)
eà ö + ï
同様に 2s+1までの和を考えれば、 Pr [X = 0] õ eà ö à ï
(証了)
Application
Janson InequalityとBrun’s Sieve両方を使った証明
Janson Inequality
8
[
]
ô
=
(1)
(
Pr B i
ï
o
i 2 I );
P
É =
Pr [B i ^ B j ] = o(1) であれば,
iøj
ö = E [X ] に対し
Pr [X = 0] !
Brun’s Sieve
E [X ] !
ö; S(r ) !
ö r =r !
Pr [X = 0] !
であれば,
àö
e
àö
e
Random graph
G~G(n,p) : 頂点数 n
任意の2頂点間に枝がある確率 p
であるグラフ
Gj= EPI T : Gの全ての頂点が三角形の頂点
になっているという事象
Theorem 8.3.2
c >0 について p, μを次式を満たすよう定める
à
á
à
n
1
c
àö
3
e = n;
p = ö
2
このとき
àc
lim Pr [G( n; p)j= EPI T] = e
n! 1
ð
ö = O(log n ) ; p3 = O( logn
n2 )
ñ
Outline of proof
Bxyz : xyzが三角形であるという事象
Cx
: xを含む三角形がないという事象
Yx
: xを含む三角形の個数
X
: 三角形に含まれない点の個数
(r )
S
=
P
( Cx = ^ y;z B xyz)
(X =
P
x 2 V Pr [C x ])
Pr [Cx 1 ^ ááá^ Cx r ]
1-1. Pr [Yx = 0] ! eà ö を証明.
1-2.
E [X ] ! c を証明.
2.
を証明.
cr
(r )
S !
(Janson 不等式より)
(Janson 不等式より)
r!
1-2, 2よりBrun's Sieveの前提が満たされるので、
Pr [G( n; p)j= EPI T] = Pr [X = 0] = eà c
1-1.
àö
Pr [Yx = 0] ! e
の証明
x∈V(G)を固定
Janson不等式を利用
8
[
]
ô
=
(1)
(
Pr B xyz
ï
o
y; z 2 V( G)) ;
P
É =
Pr [B xyz ^ B xuv] = o(1) であるとき,
xyzø xuv
ö 0 = E [Yx ] に対しPr [Yx
eà ö
à
á
à
n
1
3=
= nc;
p
ö
2
より,
ö = O(log n) ; p3 = O(log n=n 2)
Pr[Bxyz]=p3, よってε=o(1)
= 0] !
à ö0
e
1-1.
àö
Pr [YX = 0] ! e
の証明
Bxyz～Bxuv であれば、x以外の1点でも重複
P
nà 1
0
É =
Pr [B xyz ^ B xyz ] = ( 3 ) p5
y;z;z0
5
3
y
x
1
3
= O(log n=n ) = o(1)
(Yx : xを含む三角形の個数)
P
nà 1
E [Yx ] =
Pr [B xyz] = ( 2 ) p3 = ö
y;z
したがって Pr [Yx = 0] !
z =v
àö
e
u
1-2. E [X ] ! c の証明
1-1.より Pr [Yx = 0] !
E [X ] =
P
x 2 V(G)
àö
e
=
Pr [Yx = 0] !
c
n
c
2.
(r )
S
!
r
c
r!
の証明
r を固定
P
S =
Pr [Cx 1 ^ ::: ^ Cx r ]
àn á
= r Pr [Cx 1 ^ ::: ^ Cx r ] ø
(r )
nr
r ! Pr [C x 1 ^
::: ^ Cx r ]
(2行目の{x1, ..., xr}⊂V(G)は適当な頂点)
Cx 1 ^ ::: ^ Cx r = ^ B x i yz
(右辺は1≦i≦r, ∀y,zについての積)
ここで Pr [^ B x i yz] についてJanson不等式を利用
2.
(r )
S
!
r
c
r!
の証明
Janson不等式
Y:
B x i yz の生起数(1≦i≦r, ∀y,z)
Pr [B x i yz] ô ï = o(1) (1 ô i ô r ; 8 y; z 2 V( G)) ;
P
É =
Pr [B x i yz ^ B x j y0z0] = o(1) であるとき,
x i yzø x j y 0z0
ö 1 = E [Y] に対し
Pr [Y = 0] !
à ö1
e
1-1.と同様に Pr [B x i yz] = o(1), したがって ï = o(1)
(r )
2.
S
!
r
c
r!
の証明
Bxiyz～Bxjy’z’ であれば、2つの点が重複
ペアの数を数える(点の取り方×重ね方)


i=jの場合
nà 1
3
r á( 3 ) á3 = O( n )
i≠jの場合
r
nà 2
( 2 ) á( 2 ) á( 42 ) = O( n 2)
z=v
y
xi=xj
u
したがって
É =
P
Pr [B x i yz ^ B x j y 0z0] = p5 áO( n 3) = o(1)
x i yzø x j y 0z0
(r )
2.
E [Y] =
S
P
Bxiyzの数は
r
c
r!
!
の証明
Pr [B x i yz]
xixjz : 重複して数えている
à
r ( n 2 1 ) à O( n)
O( r 2n + r 3) = O( n)
ð
ñ
à
E [Y] = p3 á r ( n 2 1 ) à O( n ) = r ö + O( n à 1+ o(1) )
したがって
Pr [Y = 0] = Pr [Cx 1 ^ ::: ^ Cx r ] ø eà r ö
(r )
S
=
nr
r ! Pr [C x 1 ^
ø
nr
r!
à rö
áe
=
::: ^ Cx r ]
(neà ö) r
r!
=
cr
r!
(証了)

Download Report