probabilistic2.5

The Probabilistic Method
2.5-2.6
2.5ＵＮＢＡＬＡＮＣＩＮＧＬＩＧＨＴＳ
定理2.5.1
aij 1(1i , j n )
とする。その時、
 2
 3/ 2




o
(
1
)
y

a
n
ij xi


j
i 1 j 1
 

n
を満たす
n
x,y
i
が存在。
j
 1(1  i, j  n)
・証明（定理2.5.1）
,, y にランダム
y
については考えず、
1
n
x
に  1を割り当て、
n
R
i
とする。
  aij
j 1
n
y ,R   R
j
i 1
i
証明(定理2.1.5)の続き
iを固定する。aijに関わらず、aijyjは確率1/2
で＋１か－１。
Riは以下のような分布Sｎを持つ。
Sn：{－１，１}のランダム値ｎ個の和の分布
証明(定理2.1.5)の続き
E Sn  の近似値をとって、
 2

E  Ri   E  S n   
 o(1)  n
。
 

この近似値は組み合わせで得られる
n 1 
1 n 

E S n   n2 
 (n  1) 2 
とスターリンの公式 n! n n e  n 2n から求まる。
証明(定理2.1.5)の続き
Rの期待値の線形性を用いて、
n
 2
 3/ 2
E R    E  Ri   
 o(1) n
i 1
 

よって、少なくともRがこの値はあるような
y1,…,yn＝±１が存在する。
証明(定理2.1.5)の続き
最後にRiと同符号になるようにxiをとれば、
n
n
 x a
i 1
i
j 1
ij
n
y j   xi Ri
i 1
n

i 1
となる。
 2
 3/ 2
Ri  R  
 o(1) n
 

2.6ＷＩＴＨＯＵＴＣＯＩＮＦＬＩＰＳ
確率を使わなかったら？
定理2.2.1
アルゴリズム：
それまでの頂点との枝が少なくとも半分は交差
するように頂点をTかBに入れていく。
B
T
B
定理2.4.1
• 任意の v1 , v2 ,  , vn  R , all vi  1 に対して、
以下を満たす  ,  ,  ,   1 が存在する。
n
1
2
n
1v1   2v2       n vn  n
同様に以下を満たす 1 ,  2 ,  ,  n  1も存在する。
1v1   2v2       n vn  n
定理2.4.1
viの符号εiが選ばれるとき、
部分和 w=ε1v1＋・・・＋εi-1vi-1
求まっているとする。
ノルムを小さくするのであればεiviがｗとなす
角が鈍角(または直角)となるように、大きく
するのであれば鋭角(または直角となるよ
うに)となるようにεiをとる。
定理2.4.1の続き
もしすべての段階でwとvのなす角が直角で
あれば、ピタゴラスの定理と帰納法からノ
ルムは nであることがわかる。
そうでないならば、 n より小さいか、大きい
かになる。
定理2.4.2
• 任意の
v1 , v2 ,  , vn  R n , all vi  1
p1 , p2 ... pn  [0,1]
に対して、
,1
以下を満たす 1 ,  2 ,  ,  n  0が存在する。
※ただし
 
n
wv 
2
w  p1v1  ...  pn vn
v  1v1  ...   n vn
定理2.4.2
v1 ,..., vn  R n , p1 ,..., pn  0,1 が与えられ、
1 ,...,  s 1 {0,1} がすでに選ばれていると仮定する。
s 1
部分和を ws 1    pi   i vi とする。
i 1
アルゴリズム：
s
ws  ws 1  ( ps   s )vs   ( pi   i )vi
i 1
のノルムが最小となるように  sを選ぶ。
定理2.4.2の続き
Pr s 1  ps で  s  {0,1}を選ぶと、
 

E ws  ws 1  2ws 1  vs E ps   s   vs E ( ps   s ) 2
2
2
2
 ws 1  ps (1  ps ) vs
であるから、  s  {0,1} のどちらかの選択で、
2
ws  ws 1  ps (1  ps ) vs
2
2
2
2

定理2.4.2の続き
すべての s (1  s
w0  0 とすれば、
 n) について考えると、
n
wn   pi (1  pi ) vi
2
i 1
2

Download Report