動機
當壞事件的概率之和小於 1 時,聯集界(union bound)可以證明存在一個避開所有壞事件的結果。但當壞事件數量很多時,即使每個事件都很罕見、且只與少數其他事件相互作用,聯集界也會失效。Lovász 局部引理(Lovász local lemma)利用這種稀疏的依賴結構,證明避開所有壞事件的結果依然存在。
這個結論是存在性的。下面的證明並不提供尋找這個結果的高效算法。它還要求一個精確的依賴條件:分別與每個較遠的事件兩兩獨立,並不足以證明可以對這些事件的整體同時取條件。
定義
定義 6.5.1
(依賴圖)
設 是概率空間中的事件。依賴圖(dependency graph)是以事件下標為頂點的無向圖,使得每個 都與由所有滿足 且 不與 相鄰的事件 所生成的聯合 -代數相互獨立。用 表示 的鄰點集合。這種聯合獨立性意味著 與由這些非鄰點事件所決定的任何事件都相互獨立,其中包括它們的補事件之交。
對於相互獨立的隨機變量,依賴於互不相交的變量集合的事件是相互獨立的。可以把變量集合有重疊的事件用邊相連,從而得到一個有效的依賴圖,即使其中某些被連接的事件剛好是相互獨立的。允許多餘的邊存在,但這可能使所得的界變弱。
定理
定理 6.5.2
(一般局部引理)
設存在數 ,使得對每個 都有
則 。
定理 6.5.3
(對稱局部引理)
若每個事件的概率至多為 ,依賴圖的最大度至多為 ,且 ,則避開所有壞事件的概率為正。
證明:條件壞事件概率
證明
(對集合大小歸納證明條件壞事件概率)
我們先對 用歸納法證明:對每個下標 以及每個不含 的集合 ,都有
並且作為條件的事件具有正概率。空集的情形由假設直接得到,因為乘積至多為 1。對於一組被避開的事件,其交的正概率可這樣得到:先把這些事件排序,再應用已經建立的條件概率上界,每一次繼續避開一個事件的條件概率至少為 。
歸納步驟中,把 分為 與 。令 為下標屬於 的所有事件都被避開這一事件, 為下標屬於 的所有事件都被避開這一事件。由歸納假設,事件 具有正概率。由於 與其非鄰點聯合獨立,故 。
將 的下標排序。由歸納假設,在以 以及避開 中較早的事件為條件時,下一個壞事件的概率至多為它對應的 。這裏相關的條件集合不含這個下一個下標,且大小小於 。因此
現在有
最後一個不等式用到了假設,以及 是 的子集這一事實。歸納至此完成。最後,把全部 個壞事件排序,將相繼的條件避開概率相乘,每一個都至少為 ,從而證明了一般引理。
證明透視
每個假設用在何處
證明用到三個假設,每個只在一個步驟中使用。 與其非鄰居的聯合獨立性只用一次,即把 換成 ,其中 是 中所有事件的補事件之交。只有與其中每一個事件的兩兩獨立並不足夠,下面的反例會說明。歸納假設用於 中的鄰居,所用的條件集合嚴格小於 ;這就是歸納對 進行的原因,也說明了為甚麼無須假設鄰居之間如何相互依賴。數值假設在最後用來吸收分母:除以 至多損失不在 中的鄰居所對應的因子,而這些因子都在 之內。
證明:對稱判據
證明
(由一般引理推出對稱判據)
對於 ,對每個 取 。由於每個頂點的度至多為 ,所以
最後一個不等式來自 。因此 蘊含一般引理的假設。當 時,這些壞事件在所需的意義下是聯合獨立的,每個事件的概率至多為 ;避開它們的概率是一些正因子的乘積。沒有事件的情形是平凡成立的。
例題詳解
例題 6.5.4
(一個稀疏的 3-CNF 公式)
考慮一個 3-CNF 公式,其中每個子句含有三個不同的變量,並且至多與另一個子句共享變量。在獨立的公平隨機賦值下,每個子句為假的概率是 。把共享變量的子句用邊相連,得到的依賴圖最大度 。由於 ,所以存在某個賦值使所有子句都被滿足。
例題 6.5.5
(聯集界可能太弱)
對於十個這樣的子句,它們各自失敗概率之和為 ,因此僅憑聯集界無法給出全部被滿足的概率的任何正下界。但如果上一個例子中的依賴條件成立,局部引理仍然保證存在一個滿足所有子句的賦值。
例題 6.5.6
(獨立事件)
設 100 個壞事件相互獨立,每個的概率為 。它們的概率之和是 25,但避開所有這些事件的概率是 。此時依賴圖的度為零,這說明事件的個數本身並不是真正的障礙。
例題 6.5.7
(檢驗一個不成立的判據)
若 且 ,則 。對稱判據不適用。這一計算並不能證明無法避開所有事件;它只是說明這個充分性檢驗沒有給出結論。
常見錯誤
反例模式
兩兩獨立不等於聯合獨立
設 是兩個獨立的公平位元,令 。這三個位元兩兩獨立,但 由數對 所決定。因此事件 分別與事件 和 獨立,卻不與它們的交相互獨立。若僅憑兩兩獨立就省去兩條邊,所得的依賴圖並不滿足上面的定義。
常見錯誤
(把依賴邊當作實際存在的依賴)
依賴圖中的一條邊表示容許存在依賴,而不是說依賴必定發生。添加不必要的邊仍然是有效的,但會增大度,並可能使對稱不等式不再成立。反過來,省去一條邊需要完整的聯合獨立性,而不僅僅是一個相關性的計算。
常見錯誤
(由存在性期望高概率或算法)
該引理保證的是正概率,因而是存在性。它並不說明均勻隨機抽樣得到的賦值會以高概率成功,本身也不能給出找到成功結果所需時間的界。構造性的版本需要額外的算法和假設。
謹慎地應用引理
首先明確概率空間和壞事件。然後計算或估計每個事件的概率。構造一個滿足聯合獨立條件的圖並估計其最大度;對於由獨立變量定義的事件,變量集合互不相交可以方便地給出理由。最後檢驗數值不等式,並把對每個壞事件的避開轉化回所要求的對象。
一個重複出現某個變量的子句,其失敗概率可能不同於 。重言子句永遠不會為假。該例假設三個變量互不相同,這樣使子句為假所需的三個賦值就是三個獨立的公平位元約束。依賴度是按與之至少共享一個變量的其他子句的個數來計算的,而不是按子句中變量的個數。
當某些事件的概率遠小於其他事件,或鄰點比其他事件更少時,非對稱定理會很有用。它的參數 是逐個選取的,所以即使最壞情形下的單一 使對稱判據失效,它仍可能成功。在每個應用中,選取這些參數並檢驗各乘積,仍然是證明的一部分。
超圖染色的一個應用
設一個有限超圖的每條邊恰好含有 個不同的頂點,並且每條邊至多與 條其他邊相交。對每個頂點獨立地以各一半的概率染成紅色或藍色。對於邊 ,令 為其所有頂點顏色相同這一事件。在 種染色中有兩種是單色的,所以 。
當兩條超邊相交時,把對應的壞事件相連。一個事件只依賴於它自己那條邊的頂點顏色,並且與建立在互不相交的邊上的事件所構成的整體相互獨立。該依賴圖的最大度至多為 。因此,只要
局部引理就給出一種沒有單色邊的染色。這是一個通常意義下的合適二染色,即每條超邊都同時含有兩種顏色。圖中可以有很多條邊;該條件控制的是局部的重疊,而不是壞事件的總數。
例如,若 且每條超邊至多與另一條相交,則 ,並且 。於是存在合適的二染色。該結論並沒有說明如何高效地找到它,也沒有說明有多少種這樣的染色。
一個非對稱的計算
設有兩個壞事件,由一條依賴邊相連,其概率分別至多為 和 。取 ,。乘積條件為 以及 。一般引理給出避開概率至少為 。
僅對兩個事件而言,聯集界剛好給出更強的下界 。這個例子的目的是展示如何檢驗不相等的參數,而不是聲稱局部引理總能優於其他所有界。在更大的稀疏系統中,當事件概率之和超過 1 時,它的優勢才會顯現。
保證歸納是有據可依的
證明中的條件概率要求分母非零。在對集合 的歸納階段,對每個更小集合,避開事件的正概率可由逐次補事件的已建立下界相乘得到。在分解 中,條件事件 具有正概率,而在 條件下 的乘積下界同樣為正。因此 在作除法之前就具有正概率。
聯合獨立性假設只用於 ,而 是由 的鄰域之外的事件所決定的。 中的事件可以任意地依賴於 以及彼此;歸納控制了它們的條件避開概率,而無需假設獨立性。將這兩種作用區分開來,可以避免把相鄰事件的無條件避開概率直接相乘這一錯誤的捷徑。
歸納中的條件概率不等式是有意取成單向的。在以 為條件的概率空間中,事件 是 的子集,所以它的概率至多為 。再除以 的正概率,就得到所示的上界。除非已知 與 之間有額外的關係,否則不能把這個不等式換成等式。
一般假設中的乘積取遍整個鄰域,而歸納中只除以屬於 的那些因子。每個因子都介乎零和一之間,所以去掉一些因子會使乘積變大。因此該比值至多為 。局部的數值假設正是在這一點上吸收了因對鄰近事件取條件而可能產生的損失。
正的下界可以極其微小。例如,許多小於 1 的因子之積,可能隨事件個數增加而趨於零,儘管對每個固定的有限實例它都是正的。該定理適用於命題中所述的有限事件族;無限的版本需要另外的假設和論證。
對由獨立變量決定的事件,簡單的重抽樣程序在期望意義下很快就找到。
自然延伸的下一個問題
能有效率地找出該結果嗎?
對由獨立變量決定的事件,簡單的重抽樣程序在期望意義下很快就找到。
對由獨立隨機變量決定的事件,重抽樣程序有效:只要還有某個壞事件成立,就重抽該事件所涉及的變量。已知在與引理同類的條件下,它的期望重抽樣次數是多項式的。其證明是另一種算法式論證,此處不給出。
總結
局部引理在依賴關係稀疏的情況下,仍能控制壞事件的條件概率。與非鄰點的聯合獨立性以及乘積條件保證了相繼避開每個事件時仍保持正概率。對稱不等式給出一個方便的充分性檢驗,但並不提供搜尋算法。
練習
快速檢查
(對 和 計算 ,並判斷對稱檢驗是否適用。)
解答 · 答案
其值為 ,所以只要所述的依賴度和事件概率的界成立,該檢驗就保證避開所有事件的概率為正。
快速檢查
(為甚麼在獨立賦值下,變量集合互不相交的兩個子句在依賴圖中可以不相鄰?)
解答 · 答案
每個子句為假的事件只依賴於該子句的變量。對互不相交的變量集合作獨立賦值,使它與所有建立在其他互不相交的變量集合上的事件所構成的整體相互獨立。
快速檢查
(若局部引理的不等式成立,它的結論是甚麼:存在性、高概率,還是高效算法?)
解答 · 答案
它的結論是避開事件的概率為正,因此至少存在一個避開所有壞事件的結果。它本身並不保證高概率或高效搜尋。
快速檢查
(給出避開兩個概率分別為 和 的獨立壞事件的一個數值下界。)
解答 · 答案
由獨立性,剛好有 。局部引理同樣給出一個正的下界,但精確的獨立性給出的是這個更精確的值。