X n

Probabilistic Method
第2回
2: Linearity of Expectation
2.1 Basics
確率変数 X1,…,Xn の線形結合
X = c1X1+…+cnXn
の期待値は、
E[X] = c1E[X1]+…+cnE[Xn]
で表される。
★ X1,…,Xn が独立でなくても成り立つ
例. 置換の対角成分
{1,…,n} 上のランダムな置換 s において、
X(s) で恒等変換 (1 … n) と一致している個
数を表す（e.g. X(1 4 3 2 5) = 3）。
X の期待値を求めたい。 X を分解すると
X = X1+…+Xn
ここで s(i) = i ならば Xi = 1、それ以外 0 と
する。
例. 置換の対角成分
明らかに
E[Xi] = Pr[s(i) = i ] = 1/n
よって
E[X] = 1/n+…+1/n = 1
実際の応用では、確率空間に X ≦ E[X] と
なる X と X ≧ E[X] となる X の両方が必ず
存在することを利用する。
定理2.1.1
n!2-(n-1) 個のハミルトン路を持つ n 人のトー
ナメントが存在する。
ハミルトン路の例
n
1
2
3
4
5
6
n!2-(n-1)
1.0
1.0
1.5
3.0
7.5
22.5
定理2.1.1
証明：
ランダムなトーナメント T に含まれるハミル
トン路の数を X とおく。{1,…,n} 上の置換 s
でトーナメント上の路を表す。
X = S Xs
ここで、路 s が T に含まれるとき Xs = 1、
それ以外 0 とする。
定理2.1.1
路 s が T に含まれる確率は、n-1 本の枝が
すべて前向きである確率なので
E[Xs ] = Pr[Xs ] = 2-(n-1)
{1,…,n} 上の置換は全部で n! 個あるから
E[X] = S E[Xs ] = n!2-(n-1)
■
2.2 Splitting Graphs
定理 2.2.1
定理 2.2.2
定理 2.2.3
補題 2.2.4
定理2.2.1
n 頂点、e 枝のグラフ G = (V,E) は、最低
e/2 枝からなる部分二部グラフを持つ。
証明：
T⊆V を Pr[x∈T] = 1/2 でランダムに選ぶ。B
= V-T とする。枝 {x,y} の x,y いずれか1個
だけが T に含まれるとき、この枝は交差し
ているという。
定理2.2.1
X で交差している枝の本数を表す。即ち
X
X

 
x , y E
xy
ここで、枝 {x,y} が交差していれば Xxy = 1、
それ以外 0 とする。明らかに
E[Xxy] = Pr[{x,y}:交差] = 1/2
定理2.2.1
よって、
EX  
EX 

 
x , y E
xy
e

2
どんなグラフに対しても、X ≧ e/2 となる T
の選び方が存在する。交差した枝から部分
二部グラフが構成できる。
■
定理2.2.2
グラフ G が e 枝、2n 頂点からなるとき、最
低 2nen 1 枝の部分二部グラフを持つ。G が
2n+1 頂点からなるとき、最低 e 2nn11 枝の
部分二部グラフを持つ。
定理2.2.2
証明：
G が 2n 頂点からなるとき、V の部分集合で
サイズ n のものからランダムにひとつ選ん
で T とする。このとき、
n n
n n
n
Prx, y: 交差 


2n 2n  1 2 n 2n  1 2 n  1
より、
en
2n  1
枝の部分二部グラフが存在。
定理2.2.2
G が 2n+1 頂点からなるときも同様に、V の
部分集合でサイズ n のものからランダムに
ひとつ選んで T とする。このとき、
n n 1 n 1 n
n 1
Prx, y: 交差 


2 n  1 2 n 2n  1 2n 2 n  1
より、 e 2nn11 枝の部分二部グラフが存在。
■
より複雑な例
定義
V = V1∪…∪Vk (Vi:互いに素,|Vi| = n)
k-set … 枝みたいなもの
h:[V]k → {-1,+1} … k-set の 2 彩色
k-set E がある Vi から高々 1 個の要素しか
含まないとき、E は交差しているという。
ある S⊆V に対し、 hS    hE 
ES
E:k set
定理2.2.3
k-set E が交差していれば h(E) = +1 である
とする。このときある S⊆V が存在して、
|h(S)| ≧ cknk
が成り立つ。ck は n と無関係な定数。
補題2.2.4
次数 k、各項の係数が絶対値 1 以下の同
次多項式 f (p1,…,pk) で、p1p2…pk 項の係数
が 1 であるものからなる集合 Pk を考える。
すべての f∈Pk について
|f (p1,…,pk)| ≧ ck
を満たす p1,…,pk∈[0,1] が存在する。ただし
ck は f と無関係な定数。
補題2.2.4
証明：
Mf 
max
p1 ,, pk 0,1
f  p1 ,, pk 
とおく。f∈Pk について、f は零多項式ではな
いから M(f) > 0 である。Pk はコンパクトであ
り M:Pk → R は連続なので、M の最小値は
ck である。
■
定理2.2.3
証明：
ランダムな S⊆V を次のようにして構成する。
Pr[x∈S] = pi, x Vi
X = h(S) とし、各 k-set E について
とする。
hE  if E  S ,
XE  
otherwise.
0
定理2.2.3
証明：
k-set E が 1 ≦ i ≦ k について |E∩Vi| = ai の
とき、E はタイプ (a1,…,ak) であるという。各
E について、
a1
ak
EX E   hE  PrE  S   hE  p1  pk
である。タイプごとにまとめると、
EX  

a1  ak  k
a1
p1  pk
ak
h E 



E:type a1 ,, ak
定理2.2.3
仮定より、a1 = … = ak = 1 ならば h(E) = 1
であり、|Vi| = n かつ Vi は互いに素だから、
k


h
E

n

E:type1,,1
他のどんなタイプの k-set の数もそれぞれ
nk より少ない。タイプをひとつ固定すると、
hE   n



E:type a1 ,, ak
k
定理2.2.3
よって、X の期待値は補題 2.2.4 で定義し
た f∈Pk を用いて以下のように表せる。
E[X] = nkf (p1,…,pk)
p1,…,pk∈[0,1] は |f (p1,…,pn)| ≧ ck とでき、
E[|X|] ≧ E[X] ≧ cknk
従って、ある S⊆V について、
|X| = |h(S)| ≧ cknk
■

Download Report