動機
一階矩論證控制的是壞事件概率之和。當事件數量很多時,這種方法可能失效,即使每個事件只與少數其他事件相互作用。局部依賴提供了另一條途徑,用來證明所有壞事件可以同時避免。
證明所需要的不只是兩兩獨立。對若干個各自互不相關的事件同時取條件,可能揭示出任何單個事件對中都看不到的資訊。因此,依賴圖所編碼的是:一個事件與由全體非鄰點構成的整個集合相互獨立,而對條件概率作歸納,正是使這個集合變得可處理的辦法。
本節證明有限局部引理的一般假設形式,也證明一個方便的對稱特例,並給出完整的著色與子句應用。這是一個存在性定理;若要得到快速的構造性重抽樣算法,還需要額外的結果,不能僅憑正概率推出。
定義
定義 2.3.1
(壞事件與依賴圖)
設 是有限概率空間中的事件。依賴圖是定義在這些事件下標上的簡單圖,使得每個事件 都與由所有下標既不是 也不是 的鄰點的事件所生成的 -代數相互獨立。
因此,對於由這些非鄰點事件及其補事件構成的任意聯合條件,只要該條件的概率為正, 在此條件下就保持其原有概率。對每個事件分別兩兩獨立是較弱的要求,並不是這裏所用的定義。以 表示鄰點集合。
對下標集合 ,迴避指事件 ;當 為空集時,其概率為一。只有在已證明條件事件的概率為正之後,才使用相應的條件概率。
一種有用的構造從相互獨立的基礎變量出發。如果事件 只依賴於其中的一組變量,那麼只要兩個事件下標對應的變量集合有重疊,就在它們之間連邊。非鄰點事件聯合起來只依賴於 的變量集合之外的變量;基礎變量組之間的獨立性恰好給出所需的 -代數獨立性。
有限的 -一致超圖是由 元頂點子集構成的族。這裏的合規二著色指沒有任何超邊是單色的。對於 -CNF 的應用,每個子句使用 個互不相同的變量,每個變量恰有一個文字,且不含互反的重言文字對。
定理/命題
定理 2.3.2
(非對稱有限局部引理)
設數 滿足
對每個 成立。則
更一般地,對每個下標 以及不含 的集合 ,有
此斷言中出現的所有條件事件,其概率為正均屬於定理結論的一部分。
推論 2.3.3
(一個對稱的局部依賴判準)
如果依賴圖的最大度至多為 ,每個壞事件的概率至多為 ,並且
則同時迴避所有壞事件的概率為正。這裏 是通常的指數常數。當 時,充分條件就是 ,並且聯合獨立性給出各個迴避概率的乘積。
推論 2.3.4
(稀疏重疊保證著色與滿足賦值的存在)
設 -一致超圖滿足 ,且每條邊至多與 條其他邊相交。當 時,該超圖存在無單色邊的二著色。如果每個頂點至多屬於 條邊,則取 即可。
每個變量至多出現在 個子句中的 -CNF 公式,只要
就是可滿足的。
零重疊的情形沿用前面獨立事件的約定。這些只是充分條件,並不能刻劃所有可著色的超圖或所有可滿足的公式。
證明思路或證明
先對條件壞事件概率作歸納界定,再作乘積
證明
(對條件集合作歸納得到條件迴避界)
我們對 的大小作歸納來證明條件界,同時證明所有迴避條件的概率為正。當 時,所假設的概率不等式至多為 ,因為乘積中的每個因子都至多為一。
假設對大小小於 的條件集合,條件界已經證明。大小至多為 的任意集合,其迴避概率為正:把它的下標按任意順序排列,用鏈式法則分解其迴避概率。每個相繼的因子至少為相應下標的 ,所用的條件集合大小至多為 。它們的乘積為正。
現在取 ,並把它分為 與 。第二個集合只含非鄰點。如果第一個集合為空,則由依賴獨立性得到原來的概率,它已經至多為 。
否則,先對迴避 取條件,得到
由依賴性假設,分子等於 。透過給 排序來分解分母。每個條件迴避因子的條件集合由 與 中靠前的一個真子部分組成,其大小至多為 。因此,由歸納假設,它被相應的 從下方界定。
於是
這就證明了下一層條件界。同樣的鏈式法則論證隨後給出大小為 的迴避集合的概率為正。歸納可到達每一個有限集合,所以計算中沒有對概率為零的事件取條件。
最後,把全部 個事件排序,並分解完整的迴避概率。其各因子至少為相應的 ,由此得到定理中乘積為正的下界。當沒有事件時,空乘積為一,與同一結論一致。
證明透視
歸納控制的是鄰點條件所產生的分母
關鍵的一步是證明比所求更多的東西:對每個條件集合都有條件界,而不只是最後的乘積。單有乘積界並不能歸納,條件界卻可以直接供鏈式法則使用。
此後每個假設各有一項任務。依賴圖只用於分子,而且必須是聯合的 -代數形式,因為迴避 是對許多非鄰點的聯合條件。歸納假設只用於分母,條件集合大小至多為 ;正是在這裏,鄰點的迴避可能降低概率。最後一個不等式丟掉了 以外鄰點的因子 ;這些餘量正是假設要帶上完整鄰點乘積的原因。每一層都先證明概率為正,下一層才作除法,邏輯次序因此成立。
對有界度選取同一個參數
證明
(以同一個參數得到對稱判準)
當 時,取每個 。至多有 個鄰點的頂點滿足
最後的嚴格比較就是 ,它來自 ,後者可透過在 上對 積分得到。因此,對 所述的非嚴格上界已經足夠。非對稱引理適用,並給出迴避概率為正。
當 時,每個事件與所有其他事件聯合獨立。分解迴避概率恰好得到 ,只要每個概率都小於一,它就為正。
公式 在 時給出 ,超出了引理的參數範圍;這正是要把這一邊界情形單獨說明的原因。
獨立的基礎選擇驗證的是所需的圖,而不僅僅是兩兩計數
證明
(著色與滿足賦值)
對超圖的每個頂點獨立且均勻地從兩種顏色中取色。某條 元邊為單色的事件概率為 。它的基礎變量是其 個頂點的顏色。不相交的超邊使用不相交的基礎變量集合,而所有非鄰點事件合起來仍然只使用該邊之外的頂點顏色。因此,相交圖是一個有效的依賴圖。
如果每個頂點至多屬於 條超邊,則一條邊的 個頂點中,每個頂點至多把它與另外 條邊相連。重複計數只會高估,所以 是成立的。應用對稱判準,即得到一個迴避所有單色邊事件的著色。
對於子句,獨立且公平地為所有布爾(Boole)變量賦值。含 個互不相同變量的子句,恰在其 種賦值中的一種上為假,概率為 。讓共享變量的子句相連。同樣的分組獨立性論證驗證這是一個依賴圖,度至多為 。迴避所有子句為假的事件,恰好就是一個滿足賦值,這就證明了第二個應用。
不同子句中文字符號相反並不會使這個圖失效:依賴性由共享的基礎變量決定,而不取決於文字的書寫是否相同。變量互異與非重言的條件保證了所給出的子句概率;對其他子句化簡則需要重新計算它們的參數。
存在性與高效構造仍是不同的問題
引理給出的正下界可能極小。即使是 個獨立的公平位元壞事件,當每個事件都是其位元為零時,迴避概率也是 。迴避的賦值存在,但獨立地整體重新抽樣直至成功,其期望試驗次數為 。
因此,僅憑存在性定理並不能證明找到該對象的期望運行時間是多項式的。局部重抽樣定理也許可以利用更多結構,但它需要自己的算法、不變量與終止性分析。目前這些應用證明的是解存在,並沒有給出未經陳述的高效搜尋保證。
例題詳解
例題 2.3.5
(十一致稀疏關聯對任意多條邊都成立)
設十一致超圖的每個頂點至多位於十條邊中。依賴度至多為 ,每個壞事件的概率為 。
利用 得 。無論邊的總數是多少,合規的二著色都存在。而初等的一階矩求和則要求邊數小於 ,這說明了局部依賴為甚麼能超越那種全局檢驗。
例題 2.3.6
(變量出現次數有界保證八-CNF 有模型)
取每個子句含八個互不相同變量的子句,並設每個變量至多出現在十個子句中。每個失敗概率為 ,依賴度至多為 。
充分表達式為 。因此該公式可滿足,這裏不需要對子句總數加以限制。如果數值檢驗失敗,定理保持沉默,而不是證明不可滿足。
例題 2.3.7
(非對稱證書可用精確分數來檢驗)
取三個獨立的有限選擇,事件概率分別為 、、。以它們三個下標構成的路徑是有效的依賴圖;添加不必要的依賴邊是允許的。取每個 。
端點的允許量是 ,超過 。中間的允許量是 ,超過 。因此迴避概率至少為 。實際的獨立迴避概率是 ,這說明有效的證書不必是精確的。
概念視角組合
依賴界以局部相互作用取代壞事件的總數
該圖並不聲稱事件之間相互獨立。它標出了取條件可能起作用的位置,而參數 則為這種局部效應付出代價。獨立的變量分組為該圖提供依據;隨後條件概率的歸納給出全局同時迴避的結論。
常見錯誤
反例模式
兩兩獨立並不能證明依賴圖為空
設 是獨立的公平位元。令 、、。每個事件的概率為二分之一,每一對的聯合概率為四分之一。
然而迴避 與 迫使 ,這使 發生,所以同時迴避的概率為零。空的依賴圖因而是無效的: 並不與由 和 構成的聯合條件獨立。兩兩的概率檢驗不能代替 -代數的假設。
其餘兩個錯誤涉及引理的參數及其結論的適用範圍。
常見錯誤
(在度為零時代入 )
證明要除以 的乘積,所以需要 。在 時,統一的選取 等於一,引理不適用。這種情形要直接處理:聯合獨立性給出迴避概率 ,當每個 時它為正。
常見錯誤
(把充分檢驗當作刻劃或算法)
充分的數值檢驗沒有逆命題:若 ,定理保持沉默,該實例仍可能可著色或可滿足。檢驗成立證明的是存在性,而不是快速算法,因為所保證的概率可能小至 。
總結
依賴圖提供了對非鄰點的聯合獨立性。條件迴避的歸納證明了非對稱局部引理及其正的乘積界,隨後取同一個 便得到有界度判準。稀疏重疊的著色與 SAT 問題由獨立的基礎變量推出,其概率、表示以及算法方面的局限都已明確。
練習
快速檢查
(一個十二一致超圖中每個頂點至多位於二十條邊中。利用度界與 驗證它可二著色。)
其單色事件的概率為 。
解答 · 答案
度至多為 。判準為 ,它小於 。因此存在迴避所有單色邊的二著色。該陳述並沒有限制超邊的總數,也沒有提供多項式時間的搜尋算法。
快速檢查
(對每個變量至多出現在四個子句中的六-CNF 檢驗該充分判準。解釋為甚麼對另一個公式此檢驗失敗並不能證明其不可滿足。)
使用共享變量的依賴圖。
解答 · 答案
度界為 ,壞事件的概率為 。因此 ,證明了可滿足性。判準失敗只表示這一充分性定理不能確立模型的存在;可滿足的實例可能含有許多相互依賴的子句或冗餘的重複。
快速檢查
(對雙位元反例,列出四種結果以及各自發生的壞事件。驗證兩兩獨立性與同時迴避的概率為零。)
在結果 時,三個事件全部發生。
解答
在 處,事件 全部發生。在 處只有 發生;在 處只有 發生;在 處只有 發生。每個事件佔四種結果中的兩種,每一對只在 處相交,概率為四分之一,等於它們邊緣概率之積。
每種結果都有一個壞事件發生,所以不可能迴避。儘管通過了每一項兩兩檢驗,空圖仍不滿足所需的聯合獨立性條件,這恰好就是證明中所用到的區別。