Probabilistic Method 6-3,4

Presentation on theme: "Probabilistic Method 6-3,4"— Presentation transcript:

1 Probabilistic Method 6-3,4

2 前回の内容[FGK不等式(Th.6.2.1)] Ｌ：有限分配束 μ：Ｌ→Ｒ＋ log-supermodular関数
　　　　　　　　　　　　　と表せば、

3 前回の内容[FGK不等式(Th.6.2.1)] また、 f,gがともに減少関数でも、 が成り立つ、一方が増加関数、
もう一方が減少関数であれば、 が成り立つ。

4 6.3 Monotone Properties の部分集合の族 Aが monotone decreasing
　　　　　　　　　　　　　の部分集合の族 Aが monotone decreasing Aが monotone increasing 確率空間としてP(N){Nのすべての部分集合}を考え、 Aの確率を　　　　　　　　　　　　と定義する。

5 Proposition6.3.1 A,B ：monotone increasing なNの部分集合の族
C,D ： monotone decreasing なNの部分集合の族 確率で表現 要素数で表現

6 Proposition6.3.1の証明 以下のようにA,Bの特性関数 を定める。 f,gは仮定からともに増加関数である。
FGK不等式を適用して、　　　とすれば 他の式も同様にして導く。

7 より一般の確率空間へ 実ベクトル に対して、以下のような確率空間を考える。 に対して、 に対して、この確率空間での確率を、 と表す。
　　　　　に対して、 　　　　　　　に対して、この確率空間での確率を、 　　　　　と表す。 ここで、　　　　　　　　　　　として、 と定める。

8 であることからμはlog-supermodular関数で
あり、FGK不等式を用いて、Prop.6.3.1の 一般形Ｔｈ.6.3.2を得る。

9 Theorem 6.3.2 A,B ：monotone increasing なNの部分集合の族
C,D ： monotone decreasing なNの部分集合の族 このとき、　　　　　　　　　　　　　　　　　　　に対して、

10 グラフに適用すると m頂点の完全グラフにある 本の枝を集合Nの要素として 見ると、関係式をランダムグラフに適用できる。
G=(V,E)：V上のランダムグラフ、頂点間に確率ｐで枝をはる。 グラフの特性(property)Q Qが monotone decreasing 　　　ＧがＱを持ち、ＨがＧに枝を足すことでえられるならば、 　　　ＨもＱを持つ。 Qが monotone increasing 　　　ＧがＱを持ち、ＨがＧから枝をとるころでえられるならば、 例　ハミルトン閉路を持つ 例　平面グラフである

11 Theorem 6.3.3 ：monotone increasing な graph property
　　　　　：monotone decreasing な graph property G=(V,E)：V上のランダムグラフ (確率pで独立にそれぞれの枝を取ることで得る)

12 6.4 Linear Extensions of Partially Ordered Sets
順番を保存する全単射写像 を線形拡張(Linear Extension)という。 つまり、　　　　　かつ　　　　　ならば、 　　　　　　　　　である全単射写像。 Pのすべての線形拡張を確率空間と考えること で、Pでの事象の確率空間を考えられる。

13 Theorem 6.3.4 P:　　　　　　　　　　を要素とする順序集合 この時、

14 Theorem 6.3.4 の証明 ｍ：大きな整数(あとで無限大にもっていく) L:順序ｎ組 すべての集合。
　すべての集合。 L上の順序関係を以下のように定める。 　　　　　　　　　　　　　　　　　　　　　に対して、

15 証明の流れ Lが分配束であることを示す。 Pの測度関数μを定義し、これがlog-supermodularで あることを示す。
特性関数f,gを定義し、これらが増加関数であることを 示す。 以上が示されるとFGK不等式が適用できる。

16 Lは分配束か？ 　　　　　のi番要素を とし、　　　　　　のi番要素を とすると、Lは束である。

17 Lは分配束か？ 示したいこと 左辺右辺それぞれのi要素を見ると、

18 Lは分配束か？ ３つの整数abcに対して、 が成り立つことを使うと、 が示され、Lは分配束である。

19 log-supermodular関数μ 以下のようにPの特性関数μを定める。 に対して、
　　　　　　　　　　　に対して、 μがlog-supermodularであることを示すには、 　　　　　　　　の時、　　　　　　　　　　　　　であることを 見ればよい。

20 log-supermodular関数μ つまり、　　　　　　であり、 　　　　　　　についても同様に見れる。 以上からμはlog-supermodularである。

21 増加関数f,g 事象　　　　　　　　　に関する特性関数f,gを 以下のように定める。 この２つの関数は増加関数である。 実際以下の関係が成り立つ。

22 FGK不等式を適用 このままではLでのｎ組はdistinctな整数の組で はないためにPの線形拡張に対応しないが、 ｍを無限大へ近づけると
　　　に対して　　　　　　となる確率が0へ近づく。 以上からＦＧＫ不等式を適用でき、定理を得る。