動機
證明一個好的對象存在,不必總是直接構造它。可以先定義隨機試驗,證明結果質素的期望很高,再推出至少有一個好結果。條件期望法更進一步:逐個確定隨機選擇,同時保持最終質素的條件期望下界。我們用最大割說明這兩個步驟,並區分概率論證和高效計算條件期望所需的算法工作。
定義
定義 6.6.1
(割、割重量與二分之一近似保證)
設 是有限無自環無向圖,邊權 都是非負實數。割是劃分 ;邊的端點屬於不同部分時稱該邊跨越割。割的重量是所有跨越邊的權重和。令 ,並令 為最大割重量。若隨機算法對每個這樣的輸入都滿足期望割重量至少為 ,稱其期望近似比至少為 。期望針對固定圖上的算法隨機選擇;它不保證每次運行達到該值。
定理/命題
定理 6.6.2
(隨機割的期望)
每個頂點獨立地以各 的概率放入兩部分之一。所得割的期望重量為 ,而且至少存在一個重量不小於 的割。
定理 6.6.3
(條件期望構造)
存在確定性算法,逐個確定頂點所在側而不降低最終割重量的條件期望,最終輸出重量至少為 的割。
證明思路
證明
(對邊指示變量使用期望的線性性)
對每條邊 ,令指示變量 在兩端位於不同側時為 1,否則為 0。兩端獨立公平選擇,故 。割重量為 ,期望線性性給出
期望線性性不要求所有邊的指示變量聯合獨立。三角形中跨越邊的條數必為偶數,所以三個指示變量不可能同時為 1;但每個變量為 1 的概率都是 。故三者同時為 1 的概率為零,而不是 。僅僅共享頂點並不能證明不獨立:簡單圖中不同的兩條邊的指示變量在此公平選擇實驗下是獨立的。獨立性用於計算每條邊自身跨越的概率。可能的割只有有限多個,其平均重量為 ,因此至少一個割的重量不低於平均值;否則平均值也會更低。
證明
(條件期望從不下降)
對於確定性構造,假設部分頂點的側已固定,其餘頂點仍獨立公平選擇。設當前條件期望為 ,未固定頂點 放入 、 後的條件期望分別為 。全期望公式給出 。兩者至少有一個不小於 ;選擇該側並繼續。所有頂點確定後,條件期望就是實際割重量。由於過程中從未下降,最終重量至少為初始值 。
條件值易於計算。兩端均已確定的邊,跨越時貢獻全部權重,否則貢獻零。至少一端未確定的邊,其條件跨越概率為 ,貢獻一半權重;這裏使用剩餘選擇的獨立公平性。因此可掃描關聯邊求出 ,算法是多項式時間。採用適當記錄,固定兩個端點時每條邊只需常數次處理。
證明透視
為甚麼不變量不會下降
證明維持一個不變量:給定到目前為止已固定的側,最終割重量的條件期望 不低於 。開始時甚麼都未固定,,不變量成立。唯一不尋常的一步,是 為 與 的平均:下一個頂點的公平選擇獨立於已固定的側,各以概率 取兩側,所以兩者中較大的一個不可能低於它們的平均值。這正是存在性證明中的平均論證,逐個決定地使用,也正是它把存在性變成一個程序。
結束時沒有隨機性剩下, 就是輸出割的重量。不變量本身對權重沒有任何假設;非負性只在把 與 比較時才用到。這個程序還需要 與 可以計算,上面的證明已經提供了這一點。
例題詳解
例題 6.6.4
(三角形)
單位權重三角形有 ,隨機割期望為 。將一個頂點放一側、其餘兩個放另一側,會跨越兩條邊,重量為 2,高於平均值。所有頂點放同一側的結果重量為零,說明單次隨機運行不一定達到期望。
例題 6.6.5
(根據條件期望選擇)
設單位權重三角形的 已放在 , 尚未確定。若 放入 , 貢獻零,而 各貢獻 ,條件期望為 1。若 放入 , 貢獻 1,另兩條邊各貢獻 ,條件期望為 2。因此選 。無論 隨後放在哪側,最終重量都是 2。
例題 6.6.6
(不同權重)
三頂點路徑的兩條邊權為 2 和 6,則 、隨機割期望為 4。把中間頂點放一側、兩端放另一側可跨越兩條邊,重量為 8。權重非負保證 ,這把 保證連接到 。
常見錯誤
常見錯誤
(平均值不是逐次運行的保證)
期望是平均值,不是逐次運行的保證。三角形的零重量結果反駁了「每個隨機割至少為 」。高平均值本身證明存在,卻不自動提供高效的確定性搜尋;上面的構造依賴條件期望能夠高效計算。
反例模式
負權重使二分之一近似保證失效
一個誘人的說法是:無論權重如何,隨機割的期望重量都至少為 。取兩個頂點之間一條權重為 的邊。此時 ,隨機割的期望重量為 ,與線性性的預測一致。但把兩個頂點放在同一側,不跨越任何邊,所以 ,而 ,上述說法不成立。
失效的是 這一步,它需要非負權重;這裏 。對任意實權重, 的計算仍然成立,但其近似意義必須重新分析。
總結
隨機選擇給出平均值,平均值給出存在性。當下一步條件值可高效計算時,條件期望法將證明轉化為構造。邊指示變量不必彼此獨立,但計算每條邊的跨越概率使用了頂點的獨立公平選擇。
近似保證及其局限
每個割只使用邊集的一個子集。權重非負時,其重量至多為 ,所以 。因此隨機割的期望和確定性構造均滿足
這是相對於可能難以高效計算的最優值的下界,並未斷言 ;奇圈不可能每條邊都跨越割。若 ,所有權重為零,每個割重量都為零,上述不等式仍成立。此時直接把兩個數值重量相除沒有定義,因此用不等式表述較穩妥。
對於一條權重為 1 的邊,隨機割的期望為 ,最優值為 1,因此這個隨機試驗的分析可以達到等號。條件期望法會把兩端放在不同側,在此例中達到最優,但這不證明它在每個圖上都找到最優割。
概念視角代數
用正負號表示割的權重
用符號 表示頂點所在的一側。邊 被割開當且僅當 ,所以它的指示變量是 ,於是
對獨立的公平符號,,由此再次得到 。要使割最大,就是要使帶符號的和盡可能小(負得盡可能多)。對權重為 的一條邊,,符號相反時等於 。
對於較低的門檻,可以得到概率保證。設 ,令 為未跨越邊的總權重。權重非負給出 ,而 。馬爾可夫(Markov)不等式給出
因此 。這比每次達到半最優的保證弱,卻是真正的單次概率結論。它同樣依賴非負權重和 。獨立重複可提高至少一次超過 的概率;放大需要各次運行之間使用獨立隨機選擇。
明確的條件更新
確定未賦值頂點 時,考慮一條權重為 的關聯邊 ,其中 已確定。在選擇之前它貢獻 的條件期望。把 放在 的對側,貢獻變為 ;放在同側則變為零。若 的另一鄰點尚未確定,不管如何選擇 ,這條邊仍貢獻 ,因為鄰點仍公平隨機。與 不關聯的邊不變。因此較好的選擇是跨越與已確定頂點相連邊的總權重至少一半的那一側。
例如, 已確定的鄰點中,位於 的關聯邊總權重為 7,位於 的為 4。把 放入 就跨越前者的 7;放入 則跨越後者的 4。前者保持或增加條件期望。比較時只需要已固定的鄰點;未來的邊並沒有被忽略,而是在兩種選擇下的條件貢獻相同。
這一更新也具體說明運行時間。按固定次序處理頂點;每條邊的第二個端點被處理時,查看第一個端點所在側,並把該邊權加入相應總和。在常見鄰接表表示下,每個鄰接項只訪問常數次。在實數算術操作模型下,圖操作和算術操作次數為 。若有理權重以位元編碼,位元複雜度還取決於其表示方式和算術成本。
平均論證的另一種用途
假設有限個候選解有實數分數,平均值為 。至少一個分數不低於 ,也至少一個不高於 。除了從候選集中均勻選一個之外無需其他概率模型。對加權分佈,同樣的結論適用於正概率的結果,因為期望是分數的凸組合。若平均值等於最大值,每個正概率結果都必須達到最大值;否則較小的分數會降低平均值。
這個定理沒有說好結果有多少。例如一個結果分數為 100,另外 99 個分數為零,平均值為 1,卻只有一個結果達到或超過平均值。存在性證明也不保證抽樣得到好對象有很高概率;要得到高概率算法保證,需要另作集中或抽樣分析。
練習
快速檢查
(圖有四條邊,權重為 。隨機割的期望重量是多少?)
把權重相加,再取一半。
解答 · 答案
總權重為 8,故期望割重量為 4。只要每條邊連接不同頂點,圖的具體形狀不改變此計算。
快速檢查
(部分確定後的圖,下一頂點放入 時條件期望為 7,放入 時為 9。當前條件期望是多少?哪種選擇使它不下降?)
把兩個條件值取平均。
解答 · 答案
當前期望為 。選擇條件值為 9 的 。選擇 會使這一步的條件期望下降,雖然最終仍可能碰巧得到好割。
快速檢查
(三條邊均為單位權重的路徑,其隨機割期望是多少?給出達到最優的割。)
沿路徑交替分配兩側。
解答 · 答案
期望為 。沿四個頂點交替分配兩側,可跨越全部三條邊,重量為 3。任何割至多使用全部邊,所以這是最優值。
快速檢查
(某頂點已確定鄰點的關聯權重在 側為 2、5,在 側為 4、1。選擇哪側可使條件期望不下降?)
比較已確定鄰點在兩側各自的總權重。
解答 · 答案
兩側總重分別為 7 和 5。將頂點放入 會跨越通往 的 7。賦值之前這些邊的期望貢獻為 ,之後為 7。連接未確定鄰點的邊仍各貢獻其權重的一半。
快速檢查
(條件期望證明是否要求下一頂點的兩個選擇產生不同的值?)
若兩個值相等,全期望公式說明甚麼?
解答 · 答案
不要求。若 ,兩者都等於平均值 ,選擇任何一側都保持不變量。可以用固定規則處理平局,例如總選 。孤立頂點是簡單例子:它放在哪側都不改變邊的貢獻,兩個條件值相同。確定平局規則才能完整說明確定性算法,雖然不同規則可能產生不同的割。