chap6-1.2

6章 Correlation Inequalities
B4 高井唯史
Correlation Inequalities



グラフG  V , E  を、V  1,2,..., n の全ての2節点間
の枝を確立 p でランダムに張ったものとする。
PrH  ： G がハミルトン閉路を持つ確立
 Pr P  : G が平面グラフな確立


このとき、直感的に以下が言えそうである。
Pr( P  H )  Pr( H )  Pr( P)
6章ではこれを証明し、他の例を挙げる。
Chapter 6.1

N  {1,2,..., n}
(n  1)
A, B  N
P (N )： N の全ての部分集合の族
 ,  ： N の部分集合の族 ,   P( N ) 



: A R

(非負の実数),  ( ) 
定理6.1.1
関数 ,  ,  , 

A
 ( A)
:  があり、どんな A, B  N でも
 ( A)   ( B)   ( A  B)   ( A  B)が成り立つなら、
どんな,   P ( N ) でも
 ( )   ()   (   )   (   )が成り立つ。
証明：定理6.1.1
関数  ,  ,  ,  を ( A)  0( A  ) 、 ( B)  0( B  )
 (C )  0(C    ) 、 ( D)  0( D    ) と修正する。
修正後も、定理6.1.1の前提を満たし、そうすることで
    P (N ) として、考えることができる。

帰納法で示す

 ( )  ( )   ( ) ( ),  ( )  (1)   (1) ( )
,1}となり、 (1) ( )   (1) ( ),  (1) (1)   (1) (1)
n=1のとき P( N )  {
が前提よりいえ、それを用いて
( ( )   (1))(  ( )   (1))  ( ( )   (1))( ( )   (1))
が示せる。(詳細略)
証明：定理6.1.1
n-1のとき、いかなる関数においても定理6.1.1が成り
立っているとする。 N '  N \ {n} とおき、A'  N ' において、
 ' ( A' )   ( A' )   ( A'{n})を定義する。
すると   { ,  ,  ,  }において  ' ( P( N ' ))   ( P( N )) が成り立つ。


今、定理6.1.1はn-1まで成り立つため、 'が定理6.1.1
の前提を満たせば、n-1まで成り立ち、それが同時に 
がnまで成り立つことを示す事になる。
証明：定理6.1.1

 '{ ' ,  ' ,  ' ,  '}が定理6.1.1の前提を満たすことを
証明する。つまり、任意の A' , B'  N ' において、
 ' ( A' )  ' ( B' )   ' ( A' B' ) ' ( A' B' ) が成り立てばよい。

ここで新たに1要素集合Tと関数  を定義する。
 ( )   ( A' ),  ( )   ( B' ),  ( )   ( A' B' ),  ( )   ( A' B' )
 (T )   ( A'n),  (T )   ( B'n),  (T )   ( A' B'n),  (T )   ( A' B'n)
 関数  { ,  ,  ,  }は定理6.1.1の前提を満たすの
で、任意の S , R  T において
 ( S )  ( R)   ( S  R) ( S  R) が成り立つ。
 とTにおいても定理6.1.1の前提が成り立つ。
証明：定理6.1.1


 ' ( A' )  ' ( B' )  ( ( A' )   ( A'n))(  ( B' )   ( B'n))
 ( ( )   (T ))(  ( )   (T ))
  ( P(T ))  ( P(T ))
  ( P(T )) ( P(T ))
  ' ( A' B' ) ' ( A' B' )
よって、 '{ ' ,  ' ,  ' ,  '} は定理6.1.1の前提を
満たす。
□
lattices(束)
束とは、いかなる2要素も上界、下界を共に持つ
半順序集合である。
 このとき、上界を x  y、下界を x  yで表す。
束Lがあり、 X , Y  Lにおいて、

X  Y  {x  y : x  X , y  Y }
X  Y  {x  y : x  X , y  Y } と定義する。

任意のx, y, z  Lにおいて x  ( y  z)  ( x  y)  ( x  z)
が成り立つとき、束Lは分配可能であるという。
系：6.1.2
有限で分配可能な束Lと関数  ,  ,  ,  : L  R 
があり、任意の x, y  L において、
 ( x)   ( y )   ( x  y )   ( x  y ) が成り立つなら、
任意の X , Y  Lにおいて、
 ( X )   (Y )   ( X  Y )   ( X  Y ) が成り立つ。

系：6.1.3

有限で分配可能な束Lがある。
このとき任意のX , Y  L において、
X  Y  X  Y  X  Y が成り立つ。

証明
系6.1.2において、関数  ,  ,  ,  : L  R  を
全て要素数を返す関数とする事で導ける。 □
系:6.1.4

Xを有限集合Nの族とし、以下を定義する。
X \ X  {F \ F ': F , F ' X }
このとき、X \ X  X が成り立つ。
 X \ X の例
N  {1,2,3,4} 、X  {{1,2},{1,3,4}} のとき、
X \ X  {{},{2},{3,4}} となる。
証明:系6.1.4

Y  {N \ F : F  X } と定義すると、
2
X  X Y
(X,Yの要素数は同じ)
 X Y  X Y
(系6.1.3より)
2
 X \ X (  の誤植か?
しかし、証明できず。)
6.2 FKG inequality

有限で分配可能な束Lがあり、

関数  : L  R が任意の x, y  Lにおいて
を満たす時、
 ( x)   ( y )   ( x  y )   ( x  y )
 はlog-supermodularであるという。
定理:6.2.1



:
L

R
有限で分配可能な束Lと関数
があり、
 がlog-supermodularであるとすると、任意の
増加関数 f , g : L  R において以下が成り立つ。

 
 
 

   ( x)  f ( x)      ( x)  g ( x)      ( x)  f ( x)  g ( x)      ( x) 
 xL
  xL
  xL
  xL

証明:定理6.2.1



関数  ,  ,  ,  : L  R  を以下で定義する。
 ( x)   ( x)  f ( x) ,  ( x)   ( x)  g ( x)
 ( x)   ( x)  f ( x)  g ( x) ,  ( x)   ( x)
 ( x)   ( y )   ( x)  f ( x)   ( y )  g ( y )
  ( x  y )  f ( x)  g ( y )   ( x  y )
  ( x  y )  f ( x  y )  g ( x  y )   ( x  y )
  ( x  y )   ( x  y )
よって、系6.1.2より(X=Y=Lとし)
 ( L)   ( L)   ( L)   ( L)
□
定理:6.2.1’

同条件で、関数f,gが共に減少関数である場合も、

 
 
 

   ( x)  f ( x)      ( x)  g ( x)      ( x)  f ( x)  g ( x)      ( x) 
 xL
  xL
  xL
  xL


が成り立つ。
同条件で、関数f,gが一方が増加関数、もう一方
が減少関数である場合、

 
 
 

   ( x)  f ( x)      ( x)  g ( x)      ( x)  f ( x)  g ( x)      ( x) 
 xL
  xL
  xL
  xL

が成り立つ。

Download Report