Document

Probabilistic
Method
3.6 CONTINUOUS TIME
離散的な確率
↓
連続時間で考える．
（積分などの強力な手法が使える）
3.5 RERECOLORING
１－２ｎ
≦2
p
Pr[Bef]
の別証明を与える。
ＲＥＣＯＬＯＲＩＮＧのアルゴリズム
・ステップ１：最初の色づけ
各頂点を、確率１/２で赤か青に塗り分ける。
・ステップ２：最後の色づけ
各頂点をランダムな順序で処理する。
頂点が単色の枝に含まれているとき、確率ｐで色
を変え、確率１-ｐで色を変えない。
頂点の順序付けを以下のように行う。
・各頂点に対し、出生時間を[0，1]から一様，独立にランダムに割り当
てる。
・頂点を出生時間が小さいほうから並べる。
Bef
●
●
●
●
条件１枝e,fは頂点ｖのみを共有。
条件２ fは最初の色づけで真っ青に。
eは最後の色づけで真っ赤に。
条件３ｖは、eのなかで最後に
青から赤に塗り替えられる。
条件４ｖが青から赤に塗り替えられるとき、
fはまだ真っ青。
f
Ｖ
e
・最初の色づけで、 e-｛ｖ｝のちょうどＬ個が
青に塗られたとする。
・条件2の前半：最初の色づけでｆが真っ青かつ
2 n 1
e-｛ｖ｝のちょうどＬ個が青になる確率は、 n  1  1 

 
 L  2 
f
Ｖ
e ‐｛ｖ｝
Bef
●
●
●
●
条件１枝e,fは頂点ｖのみを共有。
条件２ fは最初の色づけで真っ青に。
eは最後の色づけで真っ赤に。
条件３ｖは、eのなかで最後に
青から赤に塗り替えられる。
条件４ｖが青から赤に塗り替えられるとき、
fはまだ真っ青。
f
Ｖ
e
• 条件２後半：Ｐｒ[eが最後の色付けで真っ赤になる|…] ≦
(eの中の青色の頂点は、Ｌ＋1個)
Ｖ
Ｖ
e
e
p
L 1
Bef
●
●
●
●
条件１枝e,fは頂点ｖのみを共有。
条件２ fは最初の色づけで真っ青に。
eは最後の色づけで真っ赤に。
条件３ｖは、eのなかで最後に
青から赤に塗り替えられる。
条件４ｖが青から赤に塗り替えられるとき、
fはまだ真っ青。
f
Ｖ
e
Ｖが時間Ｘ（[0，1]に一様分布する乱数)に生成されるとする。
• 条件３：Ｐｒ[Ｖがeの中で最後に赤に塗り替えられる|…]＝
(eの中の青色のＬ個の頂点が、ｖよりはやく生まれればよい)
Ｖ
Ｖ
e
e
x
L
Bef
●
●
●
●
条件１枝e,fは頂点ｖのみを共有。
条件２ fは最初の色づけで真っ青に。
eは最後の色づけで真っ赤に。
条件３ｖは、eのなかで最後に
青から赤に塗り替えられる。
条件４ｖが青から赤に塗り替えられるとき、
fはまだ真っ青。
f
Ｖ
e
Ｖが時間Ｘ（[0，1]に一様分布する乱数)に生成されるとする。
• 条件４：Ｐｒ[Ｖが青→赤になるとき、ｆは真っ青|…]＝(1  xp)
(ｆ‐{ｖ}の頂点は、ｖより遅く生まれるか、色を赤にされなければよい)
f
f
Ｖ
Ｖ
e
n 1
●
Ｐｒ［Ｂｅｆ］≦Ｐｒ［条件２，３，４|条件１]


 n  1 1 2 n 1 L L 1

n 1
x p (1  xp ) dx 
＝

2


0
L 0 

 L 

n 1
1 2 n
2
1 2 n
2
1 2 n
2


 n 1  n  1
L
n 1
p　(
xp
)
(1

xp
)
dx



0 

 L 0  L 

1
1
p  (1  xp ) n 1 (1  xp ) n 1dx
0
1
p  (1  x 2 p 2 ) n 1dx
 21 2 n p
0
３．６ CONTINUOUS TIME
確率的グリーディーパッキング
設定
・K＋1-uniformなハイパーグラフＨ＝（Ｖ，Ｅ）
(枝に含まれる頂点がちょうどＫ＋１個）
|Ｖ|＝Ｎ．
・Ｄ‐regular すべての頂点の次数がＤ
・ＣｏｄeｇｒｅｅＣｏｎｄｉｔｉｏｎ
∀v, v’ ∈Ｖについて、共通する枝の数はo(D)
ハイパーグラフでのパッキング
パッキングＰ：共通の頂点を持たない枝集合
｜Ｐ｜≦Ｎ/（ｋ＋１）
（Ｋ＋１＝２なら、通常のグラフのマッチング）
サイズが大きいパッキングを求めたい。
確率的グリーディーアルゴリズム
アルゴリズム
●
●
●
●
１各枝に対し、ランダムに生成時間を与える。
( [０，Ｄ)から一様・独立に選ぶ )
２時刻０からスタート．Ｐ←φ
３時刻ｃに枝eが生成されたとき、eをＰに加えて
も頂点が重ならないなら、Ｐ←Ｐ∪｛e｝
４時刻Ｄになるまで３を繰り返して終了。
時刻ｃでのＰをＰＣ、ＰＤをＰＦＩＮＡＬとする。
定理３．６．１
E[｜ＰＦＩＮＡＬ｜]～Ｎ/(ｋ+１)
方針
ＳCは、時刻ｃにＰに入っていない(survive)頂点
集合。
*
f (c)  lim Pr[v  Sc] となるようなｆ（ｃ）を示し、
ｆ（ｃ）→０となることを示す。
（lim* は、N,D→∞、δ→０をあらわす）
δはCodgreeCondition ∀v,v’∈Vについて、
共通の枝の数＜δD
ｆ（ｃ）の定義
●
ｆ（ｃ）＝Pr[Birth ProcessでEveが生き残る]
・Birth Process
時刻ｃから始まり、時刻は減少していく。
まず時刻ｃにEVEが生まれる。
EVEは平均して単位時間当たり1回出産する。
（産む回数は平均ｃのポアソン分布）
1回の出産でｋ人同時に産む。
生まれた子も、EVEと同様に子を産んでいく。
時刻０になったら、Menendez Ruleを適用する。
Example：
k=2、c=10
Alice
Olive
Eve
時刻10
Tc
Barbara
Nancy
時刻ｔに生まれた者は、平均t回子供を
生む。
Rachel
Sienna
（生む回数は、平均ｔのポアソン分布）
一回につき、ｋ人の子供を生む。
Mayavati
Linda
時刻０
ｆ（ｃ）=Pr[Eveが生き残る]
時刻10
Eve
Alice
Olive
Barbara
Nancy
Menendez Rule
同時刻に生んだ子供が
すべて生き残っているとき、
親は死ぬ。
Rachel
Mayavati
Sienna
Linda
時刻０
Tｃ（ｖ）
パッキングのアルゴリズムによって、時刻ｃの時
点で頂点ｖが生き残っているかどうかを判定する
木Tc(v)を作成する。
●
●
●
ｖを含む枝で出生時刻がｔ≦ｃならば、その枝のｖ
以外の頂点は、ｖの子供として時刻ｔに生まれたと
する。
新しく生まれた頂点に対しても同様の処理を行
って木をつくる。
ただし、複数の頂点から同じ頂点が生まれた場
合、Tc（ｖ）の生成は失敗。
（３．１）式
*
lim Pr[Tc(v)  T ]  Pr[Tc  T ]
N、D、δを適当に選ぶことによって、Birth Process に
よってつくられるTcと、パッキングアルゴリズムによっ
からできるTc(v)を同一視することができる。
（３．１）
●
●
パッキングアルゴリズムでは、すべての枝の出生
時刻は、[０、D)から一様に選んでいる。
ｖを含む枝D個のうち時刻ｃ以前に生まれる枝の
個数は、BIN[D,ｃ/D]の2項分布。
（Dを大きくすれば、平均ｃのポアソン分布となる）
（３．１）
●
頂点ｖ,ｖ‘が共有する枝はo(D)個だから、その
ような枝のペアはo(D2)個。
その中で時刻ｃ以前に生まれた枝のペアの個数
の期待値は、
（ｃ/D）2o(D2)=o(1)
（３．１）
ある頂点ｗが時刻ｘに生まれたとき
●
●
●
いくつかの頂点がすでに生まれている。
それらとｗとの共通する枝は、o(D)個。
ｗを含み、それらの頂点を含まない枝の数は
D－o(D)＞D（１－δ)個。
ｗを含み、出生時刻がｘ以前の枝は、ｗから生ま
れる。
ｗが産む回数の期待値は、
BIN[D（１－δ),ｘ/D]となり、
δ、Dを適当にとれば平均ｔのポアソン分布になる。
（３．１）
*
lim Pr[Tc(v)  T ]  Pr[Tc  T ]
Tc上でのMenendez Ruleは、
Tc(v)上でのグリーディーパッキングと等価だから、
*
f (c)  lim Pr[v  Sc]
lim f(c)
0
を示す
c 
d>c ならば、f(d)≦f（ｃ）
（ｆ（ｃ）は単調非増加）
Ev
e
時刻ｄ
Ev
e
時刻ｃ
lim f(c)  0
c 
とすると、
0にならないなら、ｆ（ｘ）は単調非増加だから、
任意のｘについてｆ（x）＞LとなるL≧0が存在。
EVEの一回の出産につき、K個の子供がいて、それらがすべて生きる確率
は Lｋより大きい。
EVEがそれらによって死なない確率は、１－Lｋ以下。
i 回出産すれば、EVEが生き残る確率は（１－Lｋ）I
以下。
EVEの出産回数は平均ｃのポアソン分布になっているから、

i
c
k i
f (c )   e
(1  L )
i!
i 0
c
 c c (1 Lk )
 e e
lim f(c)  0
c 
e
 Lk c
E[| Sc |]  f (c) N
(k  1) | Pc |  | Sc | N
E[| Pc |]  (1  f (c)) N /( k  1)
E[| P
FINAL
|]  E[| PC |]
(1  f (c)) N

 N /( k  1)
k 1
定理３．６．１
E[｜ＰＦＩＮＡＬ｜]～Ｎ/(ｋ+１)
系３．６．２
|P| ～Ｎ/(ｋ+１)となるパッキン
グPが存在する。

Download Report