Blog
こんにちは。吉田です。前回は京都賞受賞記念のサテライトワークショップの話をしました。そこでは様々な講演がなされたので今回はその内容に触れたいと思います。ただ殆どは非常に専門的かつ狭い話だったので、その中で(比較的)分かりやすく(理論的な)応用も広いLovasz Local Lemmaについて紹介します。
Lovasz Local Lemmaは、その名の通りロヴァース氏によって証明された定理です。\(A_1,\ldots,A_n\)をある確率空間における確率事象とします。Lovasz Local Lemmaはある条件下のもとで\(\Pr[\bigwedge_i \bar{A_i}] > 0\)、つまりどの事象\(A_i\)も起こらない確率が正ということを示す定理です。
どういう時に\(\Pr[\bigwedge_i \bar{A_i}] >0\)が示せるかを考えてみましょう。もし\(\Pr[A_i] > 0 (1\leq i \leq n)\)かつ全ての\(A_i,A_j (i\neq j)\)が互いに独立であれば非常に簡単です。実際、\(\Pr[\bigwedge_i \bar{A_i}] = \prod_i (1-\Pr[A_i]) > 0\)となります。
逆に独立性を全く仮定しないとUnion Boundを使うことになるでしょう。もし\(\sum_i \Pr[A_i] < 1\)であれば、\(\Pr[\bigwedge_i \bar{A_i}]\geq 1-\sum_i\Pr[A_i] > 0\)となります。
Lovasz Local Lemmaはこれとは全く条件から\(\Pr[\bigwedge_i \bar{A_i}] >0 \)を示すことが出来ます。
(Lovasz Local Lemma) \(A_1,\ldots,A_n\)を任意の確率空間上の確率事象とする。集合\(E=\{(i,j) \mid i \neq j, A_i\)と\(A_j\)は従属\(\}\)と定める。また\(\Pr[A_i] \leq x_i \prod_{(i,j)\in E}(1-x_j)\)を満たす実数\(x_1,\ldots,x_n \in [0,1)\)が存在するとする。この時、\(\Pr[\bigwedge_i \bar{A_i}] \geq \prod_i (1 – x_i)\)が成り立つ。
また下の特殊ケースも有名です
(Lovasz Local Lemma, Symmetric case) \(A_1,\ldots,A_n\)を任意の確率空間上の確率事象とする。各事象\(A_i\)は高々\(d\)個を除く全ての\(A_j (j\neq i)\)と互いに独立とする。また\(Pr[A_i]\leq p (1 \leq i \leq n)\)とする。もし\(ep(d+1)\leq 1\)であれば、\(\Pr[\bigwedge_i\bar{A_i}]>0\)が成り立つ。
[証明] \(d=0\)の時は自明である。そうでなければ、各\(i\)について\(|\{j \mid j \neq i, A_i\)と\(A_j\)は従属\(\}|\leq d\)である。Lovasz Local Lemmaにおいて\(x_i=1/(d+1)(<1)\)とおけば、\(d\geq 1\)の時\((1-\frac{1}{d+1})^d>1/e\)であることから定理が成り立つ。
Lovasz Local Lemmaの証明をする前に、簡単な応用を見てみましょう。CNFとはリテラルの論理和からなる節を論理積で繋げたものです。例えば
\((x \vee y) \wedge (\bar{x} \vee z)\)
は\(x,y,z\)を変数、\(x,y,\bar{x},z\)をリテラル、\((x \vee y),(\bar{x} \vee z)\)を節に持つCNFです。\(\bar{x}\)は\(x\)の否定を意味しています。目的は変数にtrue/falseを割り当てて、CNFが全体としてtrueになるようにすることです。
さて、各節が\(k\)個のリテラルの論理和からなり(\(k\)-CNFとも呼ばれる)、全体として\(m\)個の節の論理積からなるCNFを考えます。
さらにどの節に対しても、その節と変数を共有する節の個数は\(d\)以下であるとします。Lovasz Local Lemmaを用いると\(k,d\)の関係だけからこのCNFが充足可能であることが証明できます。つまり節の個数\(m\)には関係ありません。
Lovasz Local Lemmaを用いるには確率空間を導入する必要があるので、各変数にtrue/falseを\(1/2\)の確率で付与するということを考えましょう。
\(A_i\)を節\(i\)が充足されない事象とします。明らかに\(\Pr[A_i]=1/2^k\)です。 仮定から\(A_i\)と従属な\(A_j (j\neq i)\)の数は高々\(d\)個です。よってLovasz Local Lemmaから\(e2^{-k}(d+1)\leq 1\)であればこのCNFは充足可能であることがわかります。
この議論では単に充足可能であることが示されただけであることに注意してください。充足可能であることが分かっても変数割り当てを得ることは全く自明ではありません。
Lovasz Local Lemmaを構成的にする、つまり変数割り当ても得られるようにするという話題だけで多くの論文が書かれています。
それでは最後にLovasz Local Lemmaを証明しましょう。
[証明] 整数\(s\)の帰納法で、任意の\(S\subseteq \{1,\ldots,n\}, |S|=s<n\)と\(i\not \in S\)について、\(\Pr[A_i \mid \bigwedge_{j\in S}\bar{A_j}] \leq x_i\)を示す。\(s=0\)の時は自明なので、\(s'<s\)の時はこれが成り立っていると仮定して、集合\(S\)に対して証明する。
\(S_1 = \{j \in S \mid (i,j) \in E\}, S_2 = S \setminus S_1\)とする。すると、
\(\Pr[A_i \mid\bigwedge_{j\in S} \bar{A_j}]=\frac{\Pr[A_i\wedge (\bigwedge_{j\in S_1}\bar{A}_j)\mid\bigwedge_{\ell\in S_2}\bar{A}_{\ell}]}{\Pr[\bigwedge_{ j\in S_1}\bar{A}_j\mid\bigwedge_{\ell \in S_2}\bar{A}_{\ell}]}\)
が成り立つ。
\(A_i\)が\(\{A_\ell \mid \ell \in S_2\}\)と独立であることに注意すると、分子は
\(\Pr[A_i\wedge (\bigwedge_{j\in S_1}\bar{A}_j)\mid\bigwedge_{\ell\in S_2}\bar{A}_{\ell}]\leq\Pr[A_i\mid\bigwedge_{\ell\in S_2}\bar{A}_{\ell}]=\Pr[A_i]\leq x_i\prod_{(i,j)\in E}(1-x_j)\)
となる。
分母は帰納法の仮定から次のように抑えることが出来る。\(S_1=\{j_{1},j_{2},\ldots,j_{r}\}\)と置く。もし\(r=0\)であれば、分母は\(1\)になり、題意が示される。もしそうでなければ、次が成り立つ。
\(\Pr[\bar{A}_{j_1}\wedge \ldots \bar{A}_{j_r} \mid \bigwedge_{\ell \in S_2}\bar{A}_{\ell} ]= (1-\Pr[A_{j_1} \mid\bigwedge_{\ell \in S_2}\bar{A}_{\ell} ]) \cdot \cdots \cdot (1-\Pr[A_{j_r} \mid \bar{A}_{j_1} \wedge \ldots \wedge \bar{A}_{j_{r-1}} \wedge \bigwedge_{\ell\in S_2}\bar{A}_{\ell} ]) \geq (1-x_{j_1})\cdots (1-x_{j_r}) \geq \prod_{(i,j\in E)}(1-x_j)\)
ここから\(\Pr[A_i \mid \bigwedge_{j\in S}\bar{A_j}] \leq x_i\)が得られる。
よって、
\(\Pr[\bigwedge_i A_i] = (1-\Pr[A_1])\cdot \cdots (1-\Pr[A_n \mid \bigwedge_{i=1}^{n-1}\bar{A}_i]) \geq \prod_i(1-x_i)\).
もう少し数式が見やすくなれば良いのですが。次回からは工夫してみたいと思います。
Tag
