Isolation Lemmaとその証明
更新
を の部分集合族とする。
の各要素 に重み を割り当てる。 はそれぞれ独立に の中から一様ランダムに選ぶ。
の重みを と定義する。
このとき,確率 以上で の要素の中で重みを最小にするものはただ一つである。
離散最適化のややマニアックな定理を紹介します。
Isolation Lemma の嬉しさ
Isolation Lemma の嬉しさ
Isolation Lemma は離散最適化で活躍する定理です。
多くの離散最適化の問題について「重みを の中からランダムに選べば,十分高い確率で最適解はただ一つしかない」と言うことができます。これを利用して乱択アルゴリズムを構成できたりします。
例えば がグラフの枝集合, がマッチングの集合, がマッチングの重みと考えると分かりやすいかもしれません。
の構造がどんなものでも成立するというのは素晴らしいですね。
Isolation Lemma の証明
Isolation Lemma の証明
定理の主張から見て証明は相当難しそうですが,実はそこまで難しくありません。重み を最小にする を重み最小解と呼ぶことにします。
まず, の一つの要素 に注目する。 以外の重みを固定して, の重み を動かしたときの様子を見る。以下の3パターンのいずれかが起こる。
-
をどのように決めても は全ての重み最小解に含まれない場合
-
をどのように決めても は全ての重み最小解に含まれる場合
-
上記のいずれにも当てはまらない場合
このとき,あるしきい値 が存在して,
なら は全ての重み最小解に含まれない,
なら は全ての重み最小解に含まれる,
となる。 よって, を含む重み最小解も を含まない重み最小解も存在するような の値は高々一つである。
ここから重みの固定を外して考える。「 を含む重み最小解も を含まない重み最小解も存在する」という事象を とおくと,上記の観察により である。
よって,重み最小解が一つしかない確率は
となる。ただし,一つ目の不等号はブールの不等式(ユニオンバウンド)による。
上の証明からも分かるように「重みを から選ぶ」ではなく「重みを から選ぶ(ただし は相異なる実数)」としても Isolation Lemma は成立します。
今日の記事は特別マニアックなので高校生はもちろん,大学生も理解しなくて大丈夫です。