Isolation Lemmaとその証明

F\mathcal{F}E={e1,,en}E=\{e_1,\dots,e_n\} の部分集合族とする。

EE の各要素 eie_i に重み w(ei)w(e_i) を割り当てる。 w(ei)w(e_i) はそれぞれ独立に {1,,N}\{1,\dots,N\} の中から一様ランダムに選ぶ。

FFF\in \mathcal{F} の重みを w(F)=eFw(e)w(F)=\displaystyle\sum_{e\in F}w(e) と定義する。

このとき,確率 1nN1-\dfrac{n}{N} 以上でF\mathcal{F} の要素の中で重みを最小にするものはただ一つである。

離散最適化のややマニアックな定理を紹介します。

Isolation Lemma の嬉しさ

Isolation Lemma は離散最適化で活躍する定理です。

多くの離散最適化の問題について「重みを {1,,N}\{1,\dots ,N\} の中からランダムに選べば,十分高い確率で最適解はただ一つしかない」と言うことができます。これを利用して乱択アルゴリズムを構成できたりします。

例えば EE がグラフの枝集合,F\mathcal{F} がマッチングの集合,w(F)w(F) がマッチングの重みと考えると分かりやすいかもしれません。

F\mathcal{F} の構造がどんなものでも成立するというのは素晴らしいですね。

Isolation Lemma の証明

定理の主張から見て証明は相当難しそうですが,実はそこまで難しくありません。重み w(F)w(F) を最小にする FF を重み最小解と呼ぶことにします。

証明

まず,EE の一つの要素 eie_i に注目する。eie_i 以外の重みを固定して,eie_i の重み w(ei)w(e_i) を動かしたときの様子を見る。以下の3パターンのいずれかが起こる。

  • w(ei)w(e_i) をどのように決めても eie_i は全ての重み最小解に含まれない場合

  • w(ei)w(e_i) をどのように決めても eie_i は全ての重み最小解に含まれる場合

  • 上記のいずれにも当てはまらない場合
    このとき,あるしきい値 pp が存在して,
    w(ei)>pw(e_i) >p なら eie_i は全ての重み最小解に含まれない,
    w(ei)<pw(e_i) <p なら eie_i は全ての重み最小解に含まれる,
    となる。 よって,eie_i を含む重み最小解も eie_i を含まない重み最小解も存在するような w(ei)w(e_i) の値は高々一つである。

ここから重みの固定を外して考える。「eie_i を含む重み最小解も eie_i を含まない重み最小解も存在する」という事象を AiA_i とおくと,上記の観察により P(Ai)1NP(A_i)\leq \dfrac{1}{N} である。

よって,重み最小解が一つしかない確率は

1P(A1A2An)1i=1nP(Ai)1nN1-P(A_1\cup A_2\cup\cdots \cup A_n)\geq 1-\displaystyle\sum_{i=1}^nP(A_i)\geq 1-\dfrac{n}{N}

となる。ただし,一つ目の不等号はブールの不等式(ユニオンバウンド)による。

上の証明からも分かるように「重みを {1,2,,N}\{1,2,\cdots,N\} から選ぶ」ではなく「重みを {r1,r2,,rn}\{r_1,r_2,\cdots,r_n\} から選ぶ(ただし rir_i は相異なる実数)」としても Isolation Lemma は成立します。

今日の記事は特別マニアックなので高校生はもちろん,大学生も理解しなくて大丈夫です。