アルゴリズム Lovász 局所補題

理論計算機科学において、アルゴリズム的ロヴァーシュ局所補題は、限定的な依存性を持つ制約体系に従うオブジェクトを構築するアルゴリズム的方法を提供する。

確率空間において、 A _i間の依存関係が限定的で、それぞれの確率に特定の上限が設定されている有限個の悪い事象 { A ₁ , ..., A _n }が与えられた場合、ロヴァースの局所補題は、これらの事象すべてをゼロでない確率で回避できることを証明します。しかし、この補題は、悪い事象を回避する方法についての洞察を与えないため、非構成的です。

イベント { A ₁ , ..., A _n } が互いに独立した有限個の確率変数によって決定される場合、 Robin MoserとGábor Tardos ^{[ 1 ]}によって提案された期待多項式実行時間の単純なラスベガスアルゴリズムは、すべてのイベントが回避されるように確率変数への割り当てを計算できます。

ロヴァーシュの局所補題は、確率論的手法において、特定の特性を持つ複雑な数学的対象の存在を証明するためによく用いられる強力なツールです。典型的な証明では、複雑な対象に対してランダムな操作を行い、ロヴァーシュの局所補題を用いて、いずれかの特性が欠落する確率を制限します。特性の欠如は悪い事象​​とみなされ、そのような悪い事象すべてが同時にゼロでない確率で回避できることが示されれば、存在が証明されます。補題自体は次のようになります。

させて${\displaystyle {\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}}$は確率空間Ωにおける有限個の事象の集合とする。${\displaystyle A\in {\mathcal {A}}}$させて$\displaystyle \Gamma (A)$のサブセットを表す${\displaystyle {\mathcal {A}}}$そのため${\displaystyle A}$イベントの集合とは独立している${\displaystyle {\mathcal {A}}\setminus (\{A\}\cup \Gamma (A))}$. 実数の割り当てが存在する場合${\displaystyle x:{\mathcal {A}}\rightarrow (0,1)}$次のような出来事に対して

${\displaystyle \forall A\in {\mathcal {A}}:\Pr[A]\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

すると、すべてのイベントを回避する確率は${\displaystyle {\mathcal {A}}}$特に肯定的である

$\displaystyle \Pr \left[\,{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\,\right]\geq \prod _{A\in {\mathcal {A}}}(1-x(A)).}$

ロヴァーシュの局所補題は非構成的である。なぜなら、構造的性質や複雑な対象の存在を結論づけることしかできず、実際にそれらを効率的に発見または構築する方法を示さないからである。確率空間Ωからのランダムサンプリングは、関心のある事象の確率が非効率的である可能性が高いことに注意されたい。

${\displaystyle \Pr \left[{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right]}$

小さな数の積によってのみ制限される

$\displaystyle \prod _{A\in {\mathcal {A}}}(1-x(A))}$

したがって、非常に小さい可能性が高い。

すべてのイベントが${\displaystyle {\mathcal {A}}}$互いに独立した有限個の確率変数によって決定される${\displaystyle {\mathcal {P}}}$Ωにおいて、Robin MoserとGábor Tardosは、ランダム変数への割り当てを計算する効率的なランダム化アルゴリズムを提案した。${\displaystyle {\mathcal {P}}}$すべてのイベントが${\displaystyle {\mathcal {A}}}$避けるべきである。

したがって、このアルゴリズムは、Lovász局所補題が適用されるほとんどの問題において、所定の特徴を持つ複雑なオブジェクトの証拠を効率的に構築するために使用できる。

以下の例は、ロヴァーシュ局所補題のアルゴリズム版を単純な問題に適用する方法を示しています。

Φ を変数X ₁ , ..., X _nに関するCNF式とし、 n個の節を含み、各節に少なくともk個のリテラルがあり、各変数X _{i は}最大で次の節に現れるものとする。${\displaystyle {\frac {2^{k}}{ke}}}$節。すると、Φは充足可能である。

この主張は、アルゴリズム的ロヴァシュ局所補題の対称版を用いることで容易に証明できる。X 1 _, ..., X _{n を}互いに独立な確率変数の集合とする。${\displaystyle {\mathcal {P}}}$これらは一様にランダムにサンプリングされます。

まず、Φ の各節をk個のリテラルのみを含むように切り詰めます。各節は選言であるため、これは充足可能性を損なうものではありません。切り詰められた式に対して充足可能な割り当てが見つかれば、切り詰められたリテラルを再挿入することで、元の式に対しても容易に充足可能な割り当てに拡張できるからです。

ここで、 Φ の各節に対して、不良イベントA _jを定義します。ここで、 A _jは、Φ の節jが現在の割り当てで満たされないイベントです。各節にはk個のリテラル (したがってk個の変数) が含まれており、すべての変数が一様にランダムにサンプリングされているため、各不良イベントの確率は次のように制限できます。

${\displaystyle \Pr[A_{j}]=p=2^{-k}.}$

各変数は最大で${\displaystyle {\frac {2^{k}}{ke}}}$節があり、各節にはk 個の変数があり、各悪いイベントA _jは最大で

${\displaystyle D=k\left({\frac {2^{k}}{ke}}-1\right)\leq {\frac {2^{k}}{e}}-1}$

その他の出来事。したがって：

${\displaystyle D+1\leq {\frac {2^{k}}{e}},}$

両辺にepを掛けると次のようになります。

${\displaystyle ep(D+1)\leq e2^{-k}{\frac {2^{k}}{e}}=1}$

対称的なロヴァーシュの局所補題により、Φ のすべての節を満たすX ₁、 ...、X _nへのランダムな割り当ての確率はゼロではなく、したがってそのような割り当ては必ず存在することになる。

さて、アルゴリズム的ロヴァーシュ局所補題を用いることで、上述のアルゴリズムを適用することにより、このような割り当てを効率的に計算することが可能になります。アルゴリズムの手順は以下のとおりです。

まず、変数X ₁ , ..., X _nにランダムに真理値を割り当てます。これらの変数は一様にランダムにサンプリングされます。Φ に満たされない節が存在する間、Φ 内の満たされない節C をランダムに選択し、 Cに含まれるすべての変数に新しい真理値を割り当てます。これらの変数は一様にランダムに選択されます。Φ 内のすべての節が満たされると、アルゴリズムは現在の割り当てを返します。したがって、アルゴリズム的 Lovász 局所補題により、このアルゴリズムの期待実行時間は最大で であることが証明されます。

${\displaystyle {\frac {n}{{\frac {2^{k}}{e}}-k}}}$

上記の 2 つの条件を満たす CNF 式に関するステップ。上記の記述のより強力なバージョンは Moser によって証明されています。^{[ 3 ]} Berman、Karpinski、Scott も参照してください。^{[ 4 ]}

このアルゴリズムは、一般的なブール充足可能性問題を解決するために使用されるWalkSATに似ています。主な違いは、WalkSATでは、満たされない節Cが選択された後、 C内の単一の変数がランダムに選択され、その値が反転されることです（これは、1つの変数の中から均一に選択することと見なすことができます）。${\displaystyle k}$すべてではなく${\displaystyle 2^{k}}$Cへの値割り当て ）。

前述のとおり、ロヴァーシュ局所補題のアルゴリズム版は、一般的なロヴァーシュ局所補題が証明手法として用いられるほとんどの問題に適用できます。これらの問題の一部については、以下の記事で解説されています。

• 非確率的定理の確率的証明
• ランダムグラフ

上記のアルゴリズムは、2 つの独立したイベントを再サンプリングするため、並列化に適しています。${\displaystyle A,B\in {\mathcal {A}}}$つまり${\displaystyle \operatorname {vbl} (A)\cap \operatorname {vbl} (B)=\emptyset }$並列処理は、A、Bを順次リサンプリングすることと同等です。したがって、メインループの各反復において、独立かつ条件を満たすイベントの最大集合Sを決定し、 S内のすべてのイベントを並列にリサンプリングすることができます。

割り当て関数x が、やや強い条件を満たすという仮定の下で：

${\displaystyle \forall A\in {\mathcal {A}}:\Pr[A]\leq (1-\varepsilon )x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

あるε > 0に対して、MoserとTardosは並列アルゴリズムの方が実行時間計算量が少ないことを証明した。この場合、アルゴリズムの並列バージョンは期待値で

${\displaystyle O\left({\frac {1}{\varepsilon }}\log \sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)}}\right)}$

終了するまでのステップ数。このアルゴリズムの並列バージョンは、上記の逐次アルゴリズムの特殊なケースと見なすことができ、したがってこの結果は逐次の場合にも当てはまります。