2015/10/21

Isolation Lemmaとその証明

分野: 場合の数  レベル: 大学数学

$\mathcal{F}$ を $E=\{e_1,\dots,e_n\}$ の部分集合族とする。
$E$ の各要素 $e_i$ に重み $w(e_i)$ を割り当てる。 $w(e_i)$ はそれぞれ独立に $\{1,\dots,N\}$ の中から一様ランダムに選ぶ。

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

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


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

Isolation Lemmaの嬉しさ

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

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

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

Isolation Lemmaの証明

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

証明

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

  • $w(e_i)$ をどのように決めても $e_i$ は全ての重み最小解に含まれない場合
  • $w(e_i)$ をどのように決めても $e_i$ は全ての重み最小解に含まれる場合
  • 上記のいずれにも当てはまらない場合
  • このとき,あるしきい値 $p$ が存在して,
    $w(e_i) >p$ なら $e_i$ は全ての重み最小解に含まれない,
    $w(e_i) <p$ なら $e_i$ は全ての重み最小解に含まれる,
    となる。

よって,$e_i$ を含む重み最小解も $e_i$ を含まない重み最小解も存在するような $w(e_i)$ の値は高々一つである。

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

よって,重み最小解が一つしかない確率は
$1-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,\cdots,N\}$ から選ぶ」ではなく「重みを $\{r_1,r_2,\cdots,r_n\}$ から選ぶ(ただし $r_i$ は相異なる実数)」としてもIsolation Lemmaは成立します。

今日の記事は特別マニアックなので高校生はもちろん,大学生も理解しなくて大丈夫です。
分野: 場合の数  レベル: 大学数学