chap6.3-6.4

Probabilistic Method
6-3,4
B4照山順一
前回の内容[FGK不等式(Th.6.2.1)]
Ｌ：有限分配束
 ( x)  ( y )   ( x y )  ( x y )
μ：Ｌ→Ｒ＋ log-supermodular関数
f,g：増加関数に対して、


 


  (x) f (x)   (x)g(x)     (x) f (x)g(x)   (x) 
 xL
 xL
  xL
 xL


 f 

f (x) (x) と表せば、  f   g   fg
(x)
xL
xL
前回の内容[FGK不等式(Th.6.2.1)]
また、
f,gがともに減少関数でも、
 f   g   fg
が成り立つ、一方が増加関数、
もう一方が減少関数であれば、
 f   g   fg
が成り立つ。
6.3 Monotone Properties
A : N  {1,2,..., n}の部分集合の族
Aが monotone decreasing
  A  '    ' A
Aが monotone increasing
  A    '  ' A
確率空間としてP(N){Nのすべての部分集合}を考え、
Aの確率を Pr( A)  | A | 2n と定義する。
Proposition6.3.1
N  {1,2,..., n}
A,B ：monotone increasing なNの部分集合の族
C,D ： monotone decreasing なNの部分集合の族
確率で表現
Pr( A  B )  Pr( A)  Pr( B )
Pr(C  D)  Pr(C )  Pr( D)
Pr( A  C )  Pr( A)  Pr(C )
要素数で表現
2n A  B  A  B
2n C  D  C  D
2n A  C  A  C
Proposition6.3.1の証明
以下のようにA,Bの特性関数 f , g : P( N )  R
を定める。
0 (   A)
f ( )  
1 (   A)
0 (  B)
g ()  
1 (  B)
f,gは仮定からともに増加関数である。
FGK不等式を適用して、   1とすれば
Pr( A  B)  fg    f    g  Pr( A)  Pr( B)
他の式も同様にして導く。

より一般の確率空間へ
実ベクトル p  ( p1 , p2 ,..., pn ) , 0  pi  1
に対して、以下のような確率空間を考える。
  N に対して、 Pr( )  pi (1  p j )
 
i
j
A  P(N ) に対して、この確率空間での確率を、
Prp ( A)と表す。
ここで、  : P( N )  R として、
と定める。

  Pr()
,   Nに対して () ()   (  ) (  )
であることからμはlog-supermodular関数で
あり、FGK不等式を用いて、Prop.6.3.1の
一般形Ｔｈ.6.3.2を得る。
Theorem 6.3.2
N  {1,2,..., n}
A,B ：monotone increasing なNの部分集合の族
C,D ： monotone decreasing なNの部分集合の族
このとき、 p  ( p1 , p2 ,..., pn ) , 0  pi  1に対して、
Prp ( A  B)  Prp ( A)  Prp ( B)
Prp (C  D)  Prp (C )  Prp ( D)
Prp ( A  C )  Prp ( A)  Prp (C )
グラフに適用すると
m
m頂点の完全グラフにある 2  本の枝を集合Nの要素として
見ると、関係式をランダムグラフに適用できる。
G=(V,E)：V上のランダムグラフ、頂点間に確率ｐで枝をはる。
グラフの特性(property)Q
Qが monotone decreasing
ＧがＱを持ち、ＨがＧに枝を足すことでえられるならば、
例ハミルトン閉路を持つ
ＨもＱを持つ。
Qが monotone increasing
ＧがＱを持ち、ＨがＧから枝をとるころでえられるならば、
例平面グラフである
ＨもＱを持つ。
Theorem 6.3.3
Q1 , Q2：monotone increasing な graph property
Q3 , Q4：monotone decreasing な graph property
G=(V,E)：V上のランダムグラフ
(確率pで独立にそれぞれの枝を取ることで得る)
Pr(Q1  Q2 )  Pr(Q1 )  Pr(Q2 )
Pr(Q3  Q4 )  Pr(Q3 )  Pr(Q4 )
Pr(Q1  Q3 )  Pr(Q1 )  Pr(Q3 )
6.4 Linear Extensions of
Partially Ordered Sets
( P, ) n要素順序集合
順番を保存する全単射写像  : P  {1,2,..., n}
を線形拡張(Linear Extension)という。
つまり、x, y  P かつ x  y ならば、
 ( x)   ( y ) である全単射写像。
Pのすべての線形拡張を確率空間と考えること
で、Pでの事象の確率空間を考えられる。
Theorem 6.3.4
P:
a1 , a2 ,..., an を要素とする順序集合
この時、
Pr( a1a2  a1a3 )  Pr( a1a2 )  Pr( a1a3 )
Theorem 6.3.4 の証明
ｍ：大きな整数(あとで無限大にもっていく)
L:順序ｎ組 x  ( x1 ,..., xn ) [ xi  M  1,2,..., m]
すべての集合。
L上の順序関係を以下のように定める。
x  ( x1 ,..., xn ), y  ( y1 ,..., yn )  L に対して、
x  y iff
x1  y1 かつ xi  x1  yi  y1
( 2  i  n)
証明の流れ
Lが分配束であることを示す。
Pの測度関数μを定義し、これがlog-supermodularで
あることを示す。
特性関数f,gを定義し、これらが増加関数であることを
示す。
以上が示されるとFGK不等式が適用できる。
Lは分配束か？
x  y のi番要素を
(x  y)i  min( xi  x1 , yi  y1 )  max( x1 , y1 )
とし、
xy
のi番要素を
(x  y)i  max( xi  x1 , yi  y1 )  min( x1 , y1 )
とすると、Lは束である。
Lは分配束か？
示したいこと x  (y  z )  (x  y )  (x  z )
左辺右辺それぞれのi要素を見ると、
(x  (y  z )) i
 min( xi x1 , (yz )i (yz )1 )  max( x1 , (yz )1 )
 min( xi x1 , max( yi  y1 , zi z1 ))  max( x1 , min( y1 , z1 ))
(( x  y )  (x  z )) i
 max(( x  y )i  (x  y )1 , (x  z ) i  (x  z )1 )
 min(( x  y )1 , (x  z )1 )
 max(min( xi x1 , yi  y1 ), min( xi x1 , zi z1 ))
 min(max( x1 , y1 ), max( x1 , z1 ))
Lは分配束か？
３つの整数abcに対して、
min( a, max( b, c))  max(min( a, b), min( a, c))
max( a, min( b, c))  min(max( a, b), max( a, c))
が成り立つことを使うと、
x  (y  z )  (x  y )  (x  z )
が示され、Lは分配束である。
log-supermodular関数μ
以下のようにPの特性関数μを定める。
x  ( x1 ,..., xn )  Lに対して、
 (x)  1 (Pでai a j ならばいつでも
xi x jの時)
 (x)  0 (otherwise )
μがlog-supermodularであることを示すには、
 (x)   (y )  1の時、  (x  y )   (x  y )  1 であることを
見ればよい。
log-supermodular関数μ
 (x)   (y )  1かつai  a j ならばxi  x j , yi  y j であるから
(x  y )i  max( xi  x1 , yi  y1 )  max( x1 , y1 )
 max( x j  x1 , y j  y1 )  max( x1 , y1 )  (x  y ) j
つまり、  (x  y )  1 であり、
 (x  y )  1 についても同様に見れる。
以上からμはlog-supermodularである。
増加関数f,g
事象 x1  x2 , x1  x3 に関する特性関数f,gを
以下のように定める。
( x1  x2 )
( x1  x3 )
1
1
f ( x)  
g ( x)  
0 (otherwise)
0 (otherwise)
この２つの関数は増加関数である。
実際以下の関係が成り立つ。
x  yかつf (x)  1ならば
g
についても同様。
0  x2  x1  y2  y1つまりf (y )  1
FGK不等式を適用
このままではLでのｎ組はdistinctな整数の組で
はないためにPの線形拡張に対応しないが、
ｍを無限大へ近づけると x  ( x1 ,..., xn )  L
i  j に対して xi  x j となる確率が0へ近づく。
以上からＦＧＫ不等式を適用でき、定理を得る。

Download Report