EC20.1-20.6_paku

Chapter 20 Linearity of Expectation






1. トーナメントグラフ
2. Sum-free sets
3. 支配集合
4. 独立数
5. 低次数の多項式
6. 最大充足可能性



7. Hashing functions
8. Submodular
complexity measures
9. Discrepancy
20. 期待値の線形性

確率変数
X  c1 X 1  c2 X 2    cn X n

期待値
EX   c1EX 1   c2 EX 2     cn EX n 
20. 期待値の線形性

Pigeonhole Property
確率変数 X のとりうる値で
X  E X 
か
となる場合が存在
X  E X 
20.1 トーナメントグラフのハミルトン路

1
n人で 1 vs 1 総当たり戦



コイントスとか
勝者
2
敗者
勝敗表→隣接行列
1
1
2
3
4
5
5
○
○
×
×
2 3 4
× × ○
○ ○
×
×
× ○
○ × ×
5
○
×
○
○
3
4
20.1 トーナメントグラフのハミルトン路

1
ハミルトン路が何個あるか？
2
5
3


少なくとも1つ (ex 20.5)
できるだけたくさんあるグラフ？
4
20.1 トーナメントグラフのハミルトン路

1
ハミルトン路が何個あるか？
2
5
3


少なくとも1つ (ex 20.5)
できるだけたくさんあるグラフ？
4
20.1 トーナメントグラフのハミルトン路

1
ハミルトン路が何個あるか？
2
5
3


少なくとも1つ (ex 20.5)
できるだけたくさんあるグラフ？
4
定理20.1
n! 個以上のハミルトン路を持つ
2 n 1
トーナメントグラフが存在する
1
•ランダムなトーナメントグラフ
•頂点をランダムに並べる
5
2
3
4
2
5
1
•これがハミルトン路の確率
1 1
1 1


   
  
2 2
2 2
•並べ方は全部で
n 1
3
n!通り
n!
•期待値は n 1 。で、pigeonhole property。
2
4
20.2 Sum-free sets

整数の集合（要素の和が含まれない）
x, y  B  x  y  B

例




Sum-free
Sum-free
×
×
{ 1, 3, 7 }
{ 5, 6, 7, 8, 9 }
{ 2, 3, 5 }
(∵ 2 + 3 = 5)
{ 1, 3, 6 }
(∵ 3 + 3 = 6)
20.2 Sum-free sets

問題
整数の集合 A からSum-freeな集合 B を作る

例



A { 1, 2, 5, 7, 8, 10}

B { 2, 5, 8 }
Sum-free
できるだけ多く数字を選びたい
定理20.2
1
N 個以上選んで、sum-freeな集合B
3 をつくることができる (N：Aの要素数)
•十分大きい素数 p = 3k + 2 を探す
•{1, 2, …, k, k+1, … , 2k+1, … , p-1 }
S
•Sはpの剰余類としても sum-free
定理20.2
1
N 個以上選んで、sum-freeな集合B
3 をつくることができる (N：Aの要素数)
• A { 1, 3, …… }
•{1, 2, …, k, k+1, … , 2k+1, … , p-1 }
S
•ランダムに t を選ぶ
•Aの要素aに対して
a  t (mod p )
定理20.2
1
N 個以上選んで、sum-freeな集合B
3 をつくることができる (N：Aの要素数)
• A { 1, 3, …… }
•{1, 2, …, k, k+1, … , 2k+1, … , p-1 }
S
1
• N 個くらいはSに入ると期待できる
3
•集合B{…} がつくれる（Sum-free）
 a, b  B  (a  b)t  at  bt  S  a  b  B
20.3 支配集合

支配集合とは


頂点集合とその隣接頂点だけで
すべての頂点を覆う
できるだけ少ない数で支配し
たい
2個で支配できる例
20.3 支配集合

支配集合とは


頂点集合とその隣接頂点だけで
すべての頂点を覆う
できるだけ少ない数で支配し
たい
2個で支配できる例
20.3 支配集合

支配集合とは


頂点集合とその隣接頂点だけで
すべての頂点を覆う
できるだけ少ない数で支配し
たい
2個で支配できる例
定理20.3 n
1  ln d  1
個以下で支配できる (d:最小次数)
d 1
•ランダムな頂点集合Sをつくる
ln d  1
•各頂点は確率 p :
でSに含まれ
d 1
るようにする
•SとSの隣接に含まれない頂点の集合をT
とする
•SとTをあわせれば支配集合
定理20.3 n
1  ln d  1
個以下で支配できる (d:最小次数)
d 1
•ランダムな頂点集合Sをつくる
ln d  1
•各頂点は確率 p :
でSに含まれ
d 1
るようにする
•SとSの隣接に含まれない頂点の集合をT
とする
•SとTをあわせれば支配集合
S
定理20.3 n
1  ln d  1
個以下で支配できる (d:最小次数)
d 1
•ランダムな頂点集合Sをつくる
ln d  1
•各頂点は確率 p :
でSに含まれ
d 1
るようにする
•SとSの隣接に含まれない頂点の集合をT
とする
•SとTをあわせれば支配集合
S
定理20.3 n
1  ln d  1
個以下で支配できる (d:最小次数)
d 1
•ランダムな頂点集合Sをつくる
ln d  1
•各頂点は確率 p :
でSに含まれ
d 1
るようにする
•SとSの隣接に含まれない頂点の集合をT
とする
•SとTをあわせれば支配集合
T
S
定理20.3 n
1  ln d  1
個以下で支配できる (d:最小次数)
d 1
•Sの頂点数の期待値は
T
n×(ある頂点がSに含まれる確率)
=
n p
S
•Tの頂点数の期待値は
n×(ある頂点がTに含まれる確率)
= n×(ある頂点とその隣接頂点がSに含まれない確率)
d 1
n

(
1

p
)

定理20.3 n
1  ln d  1
個以下で支配できる (d:最小次数)
d 1
•SとTをあわせたものの期待値
E ( S  T )  np  n(1  p ) d 1
 np  ne  p ( d 1)
1  ln( d  1)
n
d 1
∵ (2行目) (1  p) d 1  e  p ( d 1)
また、 p 
ln d  1
d 1
T
S
20.4 独立数

独立集合とは


互いに非隣接な頂点の集合
独立数

もっとも大きい独立集合（最大独立
集合）の要素の数
独立数４の例
20.4 独立数

独立集合とは


互いに非隣接な頂点の集合
独立数

もっとも大きい独立集合（最大独立
集合）の要素の数
独立数４の例
n
定理20.4
1
個以上の独立集合が存在する

i 1 d i  1
( d i : i 番目の頂点の次数)
•ランダムに頂点を並べる
i
•条件A
「自分のすべての隣接頂点より前に並ぶ」
•Aを満たす頂点の集合は独立集合
隣接な頂点どうしが同時にAをみたすこ
とはありえない
(どちらかが前でどちらかが後ろ)
i
n
定理20.4
1
個以上の独立集合が存在する

i 1 d i  1
( d i : i 番目の頂点の次数)
•ランダムに頂点を並べる
i
•頂点 i が条件Aを満たす確率
1
di  1
•Aを満たす頂点の数の期待値
n
1

i 1 d i  1
i
20.5 低次数の多項式

{0,1}上の次数がd 以下の多項式

例（次数３以下）
f1  1  x1 x2  x2 x3 x4  x1 x4
f 2  x1 x3  x4 x5  x6

注
11  0
0 1  1
m個の多項式の積は次数はdm 以下
f x1 , xn   f1  f 2  f m

f に近い多項式で次数の小さいものがつくれる
補題20.5 f x1 , xn   f1  f 2  f m において、任意の r で、
間違いが 2nr 以下で、次数 dr 以下の多項式 g がつくれる
•整数1～mを用いてランダムな整数集合を r 個つくる
S1 , S2 ,, Sr
•そこで多項式 g を以下で定義する
g  h1  h2  hr
h j  1   (1  f i )
iS j
•多項式 g は次数 dr 以下である
補題20.5 f x1 , xn   f1  f 2  f m において、任意の r で、
間違いが 2nr 以下で、次数 dr 以下の多項式 g がつくれる
h j  1   (1  f i )
g  h1  h2 hr
iS j
• 例 S1  1,3,5, h1  1  1  f1   1  f 3   1  f 5 
f1
…
f3
…
f5
…
h1
…
hj
…
f
g
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
1
0
1
0
1
0
1
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
0
1
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
補題20.5 f x1 , xn   f1  f 2  f m において、任意の r で、
間違いが 2nr 以下で、次数 dr 以下の多項式 g がつくれる
g  h1  h2 hr
h j  1   (1  f i )
iS j
• f  1 のとき
• f1 , , f m がすべて１で、 g  1
• f  0 のとき
• f1 , , f m の中に0のものがある
1
h

1
• j
となる確率は
以下
2 r
1
• g  1 となる確率は   以下
2
補題20.5 f x1 , xn   f1  f 2  f m において、任意の r で、
間違いが 2nr 以下で、次数 dr 以下の多項式 g がつくれる
g  h1  h2 hr
h j  1   (1  f i )
iS j
•つまり f  g の確率が
1
 
2
r
以下
• n 個の x の入力のパターン 2 n 通り
•間違い入力の期待値 2nr
20.6 最大充足可能性

充足可能性




CNF（和積標準形）を真にする入力の存在性
例
F  x1  x3 x1  x2  x3 x2 x1  x2 
x1 , x2 , x3   1,0,0
で充足
k-充足可能

任意のk個のor節を充足可能
定理20.6 Fが3-充足可能ならば、Fのor節のうち 2 は
3
同時に充足可能
•ランダムな入力列
•つくり方
Prxi  1
x1 ,, xn をつくる
2
3
1
3
Fが ( xi ) 節を含む場合
1
2
それ以外
Fが ( xi ) 節を含む場合
•Fは ( xi ) と ( xi ) を同時に含まない（Fは3-充足可能だから）
定理20.6 Fが3-充足可能ならば、Fのor節のうち 2 は
3
同時に充足可能
•ランダムな入力列
•逆に
Prxi  0
•各リテラル
x1 ,, xn をつくる
1
3
2
3
Fが ( xi ) 節を含む場合
1
2
それ以外
Fが ( xi ) 節を含む場合
x1 や x1 が0になる確率は
2 以下
3
定理20.6 Fが3-充足可能ならば、Fのor節のうち 2 は
3
同時に充足可能
2
•Fの各節が 3 以上の確率で充足されることを言えばよい
1. ( xi ) 節もしくは ( xi ) 節の形の場合
•入力のつくり方より明らか
2. リテラル３つ以上含む節の場合
•充足確率 = 1 - (すべてのリテラルが0の確率)
• 1  2 3  2 3
3
定理20.6 Fが3-充足可能ならば、Fのor節のうち 2 は
3
同時に充足可能
2
•Fの各節が 3 以上の確率で充足されることを言えばよい
3. リテラルが２つの節の場合
x1  x2 
•
たとえば
•
充足確率は
•
とすると
1  Prx1  0 Prx2  0  1 
x1  x2 x1 x2 
2 1
2
 
3 2
3
は3-充足可能に矛盾
•Fで充足する節の期待値は、その 2 以上
3

Download Report