条件付き確率法

数学とコンピュータサイエンスにおいて、条件付き確率法^{[1] [2]は、}非構成的確率的存在証明を、目的のオブジェクトを明示的に構築する効率的な決定論的アルゴリズムに変換する体系的な方法です。^[3]

多くの場合、確率的方法は、いくつかの望ましい組み合わせ特性を持つ数学的オブジェクトの存在を証明するために使用されます。この方法の証明は、ある確率分布から選択されたランダムなオブジェクトが、正の確率で望ましい特性を持つことを示すことによって機能します。したがって、それらは非構成的であり、望ましいオブジェクトを計算するための効率的な方法を明示的に説明しません。

条件付き確率法は、そのような証明を「非常に正確な意味で」、望ましい特性を持つオブジェクトを計算することが保証された効率的な決定論的アルゴリズムに変換します。つまり、この方法は証明を非ランダム化します。基本的な考え方は、ランダムな実験における各ランダムな選択を決定論的な選択に置き換えて、これまでの選択を前提として、失敗の条件付き確率を 1 未満に保つことです。

この方法は、ランダム化された丸め（確率的方法を使用して近似アルゴリズムを設計する） のコンテキストで特に関連しています。

条件付き確率法を適用する場合、悲観的推定量という専門用語は、証明の基礎となる真の条件付き確率 (または条件付き期待値) の代わりに使用される量を指します。

ラガヴァン^[2]は次のように説明しています。

まず、確率的方法を使用して、証明可能な良好な近似解の存在を示します... [次に] 確率的存在証明を、非常に正確な意味で、決定論的近似アルゴリズムに変換できることを示します。

Raghavan はランダムな丸めのコンテキストでこの方法について議論していますが、これは一般に確率的方法でも機能します。

この方法を確率的証明に適用するには、証明でランダムに選択されたオブジェクトが、一連の「小さな」ランダム選択からなるランダム実験によって選択可能でなければなりません。

この原則を説明するための簡単な例を示します。

補題: 3 枚のコインを投げて、表の数が少なくとも 2 になるようにすることが可能です。

確率的証明。3枚のコインをランダムに投げた場合、表が出る期待数は 1.5 です。したがって、表の数が少なくとも 1.5​​ になるような結果 (コインを投げる方法) が存在する必要があります。表の数は整数なので、そのような結果には少なくとも 2 つの表があります 。QED

この例では、ランダム実験は 3 枚の公平なコインを投げることから構成されます。実験は、隣の図のルート付きツリーで示されています。結果は 8 つあり、それぞれがツリーの葉に対応しています。ランダム実験の試行は、ルート (コインが投げられていないツリーの最上位ノード) から葉までランダム ウォークを行うことに対応します。成功した結果は、少なくとも 2 枚のコインが裏になった結果です。ツリーの内部ノードは、これまでに 0、1、または 2 枚のコインのみが投げられた、部分的に決定された結果に対応しています。

条件付き確率法を適用するには、実験が段階的に進むにつれて、選択肢が与えられた場合の条件付き失敗確率に注目します。図では、各ノードにこの条件付き確率のラベルが付けられています。(たとえば、最初のコインだけが投げられて裏が出た場合、それはルートの 2 番目の子に相当します。その部分的な状態を条件として、失敗確率は 0.25 です。)

条件付き確率法は、ランダム実験におけるランダムなルートからリーフへのウォークを決定論的なルートからリーフへのウォークに置き換えます。各ステップは、次の不変量を帰納的に維持するように選択されます。

現在の状態を前提とすると、条件付き失敗確率は 1 未満です。

このようにして、ラベル 0 のリーフに到達すること、つまり成功の結果が保証されます。

不変条件は最初（ルート）に成立します。これは、元の証明で（無条件の）失敗の確率が 1 未満であることが示されていたためです。任意の内部ノードでの条件付き確率は、その子ノードの条件付き確率の平均です。後者の特性が重要なのは、条件付き確率が1 未満の任意の内部ノードには、条件付き確率が 1 未満の子ノードが少なくとも 1 つあることを意味するためです。したがって、任意の内部ノードから、不変条件を維持するために、常にいずれかの子ノードを選択して移動することができます。不変条件は最後に成立するため、移動が葉に到達し、すべての選択が決定されたとき、この方法で到達した結果は必ず成功となります。

この方法の典型的な応用では、可能な結果の数が膨大 (指数関数的に大きい) であっても、結果として得られる決定論的プロセスを、適度に効率的なアルゴリズム (「効率的」という言葉は通常、 多項式時間で実行されるアルゴリズムを意味します) によって実装できるようにすることを目標とします。たとえば、コイン投げのタスクを、大きなnに対してn回投げるように拡張して考えてみましょう。

理想的なケースでは、部分的な状態 (ツリー内のノード) が与えられれば、条件付き失敗確率 (ノードのラベル) を効率的かつ正確に計算できます (上記の例は次のようになります)。これが可能な場合、アルゴリズムは現在のノードの各子の条件付き確率を計算し、条件付き確率が 1 未満の子に移動することで、次に移動するノードを選択できます。上で説明したように、そのようなノードが存在することが保証されています。

残念ながら、ほとんどのアプリケーションでは、条件付き障害確率を効率的に計算するのは簡単ではありません。これに対処するための標準的な関連手法が 2 つあります。

多くの確率的証明は次のように機能します。確率的証明では、ランダム変数Q を暗黙的に定義し、(i) Qの期待値は最大でも (または少なくとも) あるしきい値であり、(ii) Qが最大でも (少なくとも) このしきい値である結果はすべて成功であることを示します。次に、(i) は、Qが最大でも (少なくとも) しきい値である結果が存在することを意味し、これと (ii) は、成功した結果が存在することを意味します。(上記の例では、Q は裏の数であり、少なくともしきい値 1.5 である必要があります。多くのアプリケーションでは、Q は、特定の結果で発生する「悪い」イベントの数 (必ずしも互いに独立している必要はありません) であり、各悪いイベントは、実験が失敗する可能性のある 1 つの方法に対応し、発生する悪いイベントの期待数は 1 未満です。)

この場合、条件付き失敗確率を 1 未満に保つには、Qの条件付き期待値をしきい値未満 (またはしきい値以上) に保つだけで十分です。これを行うには、条件付き失敗確率を計算する代わりに、アルゴリズムはQの条件付き期待値を計算し、それに応じて処理を進めます。各内部ノードには、条件付き期待値が最大 (または最小) ノードの条件付き期待値である子ノードが存在します。アルゴリズムは現在のノードからそのような子ノードに移動し、条件付き期待値をしきい値未満 (またはしきい値以上) に保ちます。

場合によっては、量Qの正確な条件付き期待値の代理として、悲観的推定量と呼ばれる適度に厳しい境界を使用します。悲観的推定量は現在の状態の関数です。これは、現在の状態を与えられたQの条件付き期待値の上限 (または下限) でなければならず、実験の各ランダム ステップで期待値が増加 (または減少) しない必要があります。通常、適切な悲観的推定量は、元の証明のロジックを正確に分解することで計算できます。

この例では、条件付き期待値を使用した条件付き確率の方法を示します。

任意の無向グラフ G = ( V , E ) が与えられた場合、最大カット問題は、グラフの各頂点を 2 色 (黒または白など) のいずれかで色付けして、端点が異なる色を持つ辺の数を最大化することです。 (そのような辺がカットされているとします。)

最大カット補題:任意のグラフG = ( V , E ) において、少なくとも | E |/2 のエッジをカットできます。

確率的証明。公平なコインを投げて、各頂点を黒または白に着色します。計算により、Eの任意の辺 eが切断される確率は 1/2 です。したがって、期待値の線形性により、切断される辺の期待数は | E |/2 です。したがって、少なくとも | E |/2 の辺を切断する着色が存在します。QED

条件付き確率法を適用するには、まずランダム実験を小さなランダムステップのシーケンスとしてモデル化します。この場合、各ステップを特定の頂点の色の選択と見なすのが自然です (つまり、| V | ステップがあります)。

次に、各ステップでのランダムな選択を決定論的な選択に置き換えて、これまでに色付けされた頂点を考慮して、失敗の条件付き確率を 1 未満に保ちます。(ここでの失敗とは、最終的に | E |/2未満のエッジがカットされることを意味します。)

この場合、条件付き失敗確率を計算するのは簡単ではありません。実際、元の証明では失敗確率を直接計算していませんでしたが、代わりに、カットエッジの予想数が少なくとも | E |/2 であることを示すことで証明が機能しました。

ランダム変数Q を切断されたエッジの数とします。条件付き失敗確率を 1 未満に保つには、Qの条件付き期待値を しきい値 | E |/2 以上に保つだけで十分です。これは、 Qの条件付き期待値が少なくとも | E |/2である限り、 Qが少なくとも | E |/2である到達可能な結果が存在するはずであり、その結果に到達する条件付き確率は正であるためです。Qの条件付き期待値を | E |/2 以上に保つために、アルゴリズムは各ステップで、結果のQの条件付き期待値を最大化するように、検討中の頂点に色を付けます。条件付き期待値が少なくとも現在の状態の条件付き期待値である (したがって少なくとも | E |/2) 子が存在するはずなので、これで十分です。

いくつかの頂点がすでに色付けされているとすると、この条件付き期待値は何でしょうか? 元の証明の論理に従うと、カットされた辺の数の条件付き期待値は次のようになります。

これまでに端点が異なる色で表示されているエッジの数

+ (1/2)*(少なくとも 1 つの端点がまだ色付けされていないエッジの数)。

アルゴリズムは、上記の条件付き期待値の結果値を最大化するために各頂点に色を付けます。これにより、条件付き期待値が | E |/2 以上になることが保証され、条件付き失敗確率が 1 未満に保たれることが保証され、結果的に成功が保証されます。計算により、アルゴリズムは次のように簡略化されます。

1. V内の各頂点uについて（順序は問わない）：2. u
 のすでに色付けされた隣接頂点を考えます。
 3. これらの頂点のうち、白よりも黒の方が多い場合は、u を白にします。
 4. それ以外の場合は、黒にします。

この決定論的アルゴリズムは、その導出により、指定されたグラフのエッジの少なくとも半分をカットすることが保証されます。これにより、このアルゴリズムはMax-cut の 0.5 近似アルゴリズムになります。

次の例は悲観的な推定値の使用法を示しています。

トゥランの定理を述べる一つの方法は次のとおりです。

任意のグラフG = ( V , E )には、少なくとも | V |/( D + 1)のサイズの独立集合が含まれます。ここで、 D = 2| E |/| V | はグラフの平均次数です。

独立集合Sを構築するための次のランダムプロセスを考えます。

1. S を空集合として初期化します。2. V内の
 各頂点uについてランダムな順序で:
 3. uの隣接要素がSにない場合は、u をSに追加します
 。4. Sを返します。

明らかに、このプロセスは独立集合を計算します。すべての近傍よりも先に考慮される頂点u はSに追加されます。したがって、d ( u ) をuの次数とすると、 u がSに追加される確率は少なくとも 1/( d ( u )+1) です。期待値の線形性により、 Sの期待サイズは少なくとも

${\displaystyle \sum _{u\in V}{\frac {1}{d(u)+1}}~\geq ~{\frac {|V|}{D+1}}.}$

（上記の不等式は、1/( x +1) がxに関して凸であるため、各d ( u ) = D = 2| E |/| V | のとき、次数の合計が 2| E | に固定されていることを条件に、左辺が最小化されるために成り立ちます。）QED

この場合、ランダムプロセスには | V | ステップがあります。各ステップでは、まだ考慮されていない頂点u を考慮し、その隣接頂点がまだ追加されていない場合はu をSに追加します。ランダム変数Q をSに追加された頂点の数とします。証明では、E [ Q ] ≥ | V |/( D +1) であることが示されています。

各ランダムステップを、 Qの条件付き期待値を| V |/( D +1)以上に保つ決定論的ステップに置き換えます。これにより、独立集合Sのサイズが少なくとも | V |/( D +1) となり、トゥランの定理の境界が実現されるという 成功結果が保証されます。

最初の t ステップが実行されたと仮定して、S ^{( t ) は}これまで追加された頂点を表すものとします。R ^{( t )}は、まだ考慮されておらず、S ^{( t )}に隣接頂点を持たない頂点を表すものとします。最初の t ステップが与えられた場合、元の証明の推論に従うと、R ^{( t )}内の任意の頂点w は、 Sに追加される条件付き確率が少なくとも 1/( d ( w )+1)であるため、 Qの条件付き期待値は少なくとも

${\displaystyle |S^{(t)}|~+~\sum _{w\in R^{(t)}}{\frac {1}{d(w)+1}}.}$

上記の量をQ ^{( t )}で表すと、これを条件付き期待値の 悲観的推定量と呼びます。

証明では、悲観的推定量は最初は少なくとも | V |/( D +1) であることが示されました。(つまり、Q ⁽⁰⁾ ≥ | V |/( D +1) です。) アルゴリズムは、悲観的推定量が減少しないように、つまり各tに対してQ ^{( t +1)} ≥ Q ^{( t )}となるように各選択を行います。悲観的推定量は条件付き期待値の下限であるため、これにより条件付き期待値が | V |/( D +1) を上回り、条件付き失敗確率が 1 未満に保たれることが保証されます。

uを次の(( t +1)番目のステップ でアルゴリズムによって考慮される頂点とします。

u がすでにS内に隣接ノードを持っている場合、u はSに追加されず、（Q ^{( t )の検査により）悲観的推定量は変更されません。} u がS内に隣接ノードを持たない場合、uはSに追加されます。

計算により、残りの頂点からuがランダムに選択される場合、悲観的推定量の期待される増加は非負になります。[計算。R ( ^{t )内}の頂点を選択することを条件として、悲観的推定量の合計から特定の項 1/( d ( w )+1) が削除される確率は最大で ( d ( w )+1)/| R ^{( t )} | であるため、合計の各項の期待される減少は最大で 1/| R ^{( t ) | です。合計には}R ^{( t )}項があります。したがって、合計の期待される減少は最大で 1 です。一方、Sのサイズは 1 増加します。]

したがって、悲観的な推定値が減少しないようにする uの選択肢が存在するはずです。

以下のアルゴリズムは、各頂点u を選択して、結果として得られる悲観的推定値を最大化します。前述の考慮事項により、これにより悲観的推定値が減少することが防止され、成功が保証されます。

以下、N ^{( t )} ( u )はR ^{( t )}におけるuの隣接点（つまり、Sになく、 Sに隣接点を持たないuの隣接点）を表します。

1. S を空集合として初期化します。2. S内に隣接頂点を持たない、
まだ考慮されていない頂点uが存在する場合:3. u が を最小化する頂点
uをSに追加します。${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}}$
4. Sを返します。

条件付き確率法が機能するには、アルゴリズムが悲観的推定値を減少 (または必要に応じて増加) しないようにするだけで十分です。アルゴリズムは必ずしも悲観的推定値を最大化 (または最小化) する必要はありません。これにより、アルゴリズムを導出する際にある程度の柔軟性が得られます。次の 2 つのアルゴリズムはこれを示しています。

1. S を空集合として初期化します。2.グラフ内に頂点u が
存在し、その頂点はS内に隣接していない。
3. 頂点u をSに追加します。ここでu はd ( u ) ( uの初期次数)を最小化します。
4. Sを返します。

1. S を空集合として初期化します。
2. 残りのグラフが空ではない場合:3.残りのグラフで最小次数を持つ頂点
uをSに追加します。
4.グラフからuとそのすべての隣接要素を削除します。
5. Sを返します。

各アルゴリズムは、前と同じ悲観的推定量で分析されます。どちらのアルゴリズムでも、各ステップで悲観的推定量の純増加は

${\displaystyle 1-\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}},}$

ここでN ^{( t )} ( u )は残りのグラフ（つまりR ^{( t ) ）内の}uの近傍を表す。

最初のアルゴリズムでは、 uの選択により、純増加は非負となる。

${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d(u)+1){\frac {1}{d(u)+1}}=1}$、

ここで、d ( u )は元のグラフにおける uの次数です。

2番目のアルゴリズムでは、 uの選択により、純増加は非負となる。

${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d'(u)+1){\frac {1}{d'(u)+1}}=1}$、

ここでd′ ( u )は残りのグラフにおける uの次数です。

• 確率的方法
• 非ランダム化
• ランダムな丸め

条件付き丸めの方法は、いくつかの教科書で説明されています。

• アロン、ノガ、スペンサー、ジョエル(2008)。確率的手法。Wiley-Interscience 離散数学と最適化シリーズ (第 3 版)。ニュージャージー州ホーボーケン: John Wiley and Sons。250 ページ以降。ISBN 978-0-470-17020-5. MR  2437651。（引用ページは第2版、ISBN 9780471653981） 

• モトワニ、ラジーブ、ラガヴァン、プラバカール（1995年8月25日）。ランダム化アルゴリズム。ケンブリッジ大学出版局。pp. 120– 。ISBN 978-0-521-47465-8。

• Vazirani、Vijay (2002 年 12 月 5 日)、近似アルゴリズム、Springer Verlag、pp. 130–、ISBN 978-3-540-65367-7

• 確率的方法 - 条件付き確率の方法、Neal E. Young によるブログ記事、2012 年 4 月 19 日にアクセス。