動機
為了降低所有試驗都失敗的概率,可以為重複運行選取互相獨立的隨機種子。在很大的種子空間上,這可能需要大量隨機位元。在正則圖上的漫步只使用一個隨機初始頂點,此後每一步隨機選取一個鄰點。漫步經過的各頂點互相關聯,因此不能用獨立性來論證乘積界。然而,譜方法仍然可以界定「所造訪的每個頂點都落在某個固定壞集合中」的概率。
本單元明確陳述所需的圖假設。它既不構造擴展圖族,也不證明存在具有特定度數和譜的擴展圖。隨機位元的節省取決於是否有一個合適的圖,並且其鄰點可以被有效率地計算。
定義
定義 5.1.1
(正則圖的絕對譜界)
設 為有 個頂點的有限無向 -正則圖,,其對稱轉移矩陣為 。均勻概率向量為 。令 ,並假設 在與 正交的子空間上的每個特徵值的絕對值至多為 。等價地,記 ,則對稱算子 的範數至多為 。
定義 5.1.2
(壞集合與漫步樣本)
固定一個壞頂點集合 ,其相對大小為 。令 為對角矩陣,當 時 ,其餘為零。漫步從均勻隨機選取的頂點 出發,並透過互相獨立的均勻鄰點步驟依次到達 。儘管每個邊際分佈都是均勻的,各位置一般是相依的。定義 。
定理
定理 5.1.3
(對固定壞集合的重複造訪)
對每個整數 ,
特別地,若 ,則 ,且該界限隨 呈指數下降。
定理 5.1.4
(單邊放大)
設某確定性驗證器在獲得一個均勻隨機的種子頂點後運行。對每個固定的正例輸入,其壞種子集合 固定,相對大小至多為 ,其中 ;並且對任何種子,它都不會接受負例輸入。把它依次作用於漫步的 個頂點,只要有一次運行接受就接受。則對固定的正例輸入,拒絕的概率至多為
而負例輸入仍然永遠不會被接受。記 為此統一上界的因子。
證明思路或證明
證明
(遮罩算子的二次型界)
對任何支撐在 上的向量 ,由柯西–施瓦茨(Cauchy–Schwarz)不等式得
由於 ,譜假設給出
這裏較精細的中間不等式用到 在 上為零,以及它在正交分量上的範數界。對任意向量 ,取 ,得 。矩陣 是對稱的,因此由實譜定理得 。
全部落在壞集合中這一事件的概率等於
當 時等式同樣成立,此時把零次冪理解為單位矩陣。應用柯西–施瓦茨不等式和算子範數界。由於 ,結果至多為 。這直接控制了一個聯合事件,並沒有斷言漫步各位置互相獨立。
證明
(從聯集界到放大)
關於放大:先固定輸入。拒絕意味著所用的每個種子都屬於其壞集合。第一個定理適用於這個固定集合,而右端在 上關於 不減,所以由 得到所示的界限。對負例輸入,驗證器每次運行對每個種子都拒絕,因此組合後的過程不可能接受。該保證是針對每個固定輸入的;它並不要求同一條漫步對所有輸入同時有效。
證明透視
兩個假設、一個遮罩、每步一個因子
證明有兩個步驟。第一,對支撐在 上的 ,界 結合了兩個假設: 很小,由柯西–施瓦茨不等式把沿 的分量限制在 以內;譜假設則使正交分量以 收縮。單靠任何一個假設都得不到 。
第二,對角遮罩把聯合事件變成矩陣乘積 ,其中每次轉移都帶有範數至多為 的因子 ,而第一個遮罩通過 貢獻 。 的對稱性使二次型的界升級為算子範數的界。證明從不使用獨立性;對相對大小為 的每個 ,無論其內部有甚麼邊,界都相同,所以它可能偏鬆,本單元稍後的三角形小例子就說明了這一點。
例題詳解
例題 5.1.5
(失敗概率的數值保證)
若 ,,,則 ,全部為壞的概率至多為 。這五個種子並不互相獨立;該數值來自聯合事件定理。
例題 5.1.6
(只造訪一次的情形)
當 時,均勻初始化給出 恰好成立。定理給出 。這種情形不需要任何轉移,譜界在其中不起作用。
例題 5.1.7
(完全混合的理想情形)
若 ,則 ,且每個下一頂點都是均勻的,並與前一頂點獨立。此時界限變為 ,即熟知的獨立抽樣概率。稀疏圖一般有正的 ,界限較弱,但換來了較廉價的鄰點選取。
常見錯誤
反例模式
均勻的邊際分佈不能直接相乘
在無自環的正則圖上,平穩漫步在每個時刻都是均勻的,但它不可能一步之內停留在同一個頂點。因此相鄰位置並不獨立。邊際概率的乘積需要另行論證;帶遮罩算子的計算給出的是另一種聯集界。具體地,在只有一個壞頂點 的三角形中,,但 ,而不是 。
常見錯誤
(壞集合必須在抽樣之前固定)
集合 必須在對漫步抽樣之前就已針對該輸入固定。若在看到每個頂點之後自適應地選取不同的壞集合,則本定理並不適用。
常見錯誤
(去掉絕對值會漏掉負特徵值)
不帶絕對值的特徵值界限也無法控制接近 的負特徵值;所述的算子範數假設同時包含了正負兩種符號。
為甚麼帶遮罩的矩陣是壓縮的
證明把向量分解為常數部分和正交部分。 並不壓縮常數部分,這正是僅有關於非常數特徵值的界限不能斷言每個向量都會縮小的原因。但支撐在真子集上的向量不可能主要是常數:柯西–施瓦茨估計把它的常數分量的平方限制在至多 乘以其範數平方。其餘分量位於適用絕對特徵值界限的子空間中。要得到 ,既需要壞集合較小,也需要真正的譜隙。
為了更明確地計算,寫 ,其中 。則 ,且 。譜假設蘊含 。由於 且 ,可得
負特徵值已包含在二次型的絕對界之內。對稱性在下一步中很重要:對實對稱矩陣,其算子範數等於最大的絕對特徵值,也就是絕對瑞利(Rayleigh)商的最大值。沒有對稱性時,僅有二次型的界限未必能以同樣的方式控制算子範數。
遮罩是一個投影: 且 。乘以 並不會重新歸一化概率分佈,而是捨棄位於 之外的頂點上的質量。剩餘的總質量就是相應的一系列成員檢驗均已成功的概率。因此,矩陣公式追蹤的是無條件概率;若在每一步之後插入歸一化,計算就會改變,並需要另外追蹤歸一化因子。
概念視角組合
數留在壞集合內的漫步
每條含 個頂點的漫步的概率都是 ,所以全部落在壞集合的概率,等於 個頂點都在 內的漫步條數除以 。因此定理的意思是:這樣的漫步至多有 條,而平凡的計數是 。因子 是 內平均分支數的限制:漫步只能透過 內頂點通向 內另一頂點的少數邊留在 內。
造訪次數的選取
令 。若 且 ,則使失敗概率至多為 的一個充分條件是
其中要求對數的分子為正;結果向上取整為整數。若 ,則對這個界限而言一次造訪已經足夠。若 ,則沒有壞種子,失敗概率為零。這些條件是充分的,並不表示對特定的圖和壞集合該不等式是緊的。
例如,取 且 ,則 。要使界限至多為 ,只需選取 使 。計算結果為取整後 :。這個數可以直接驗算,而不必依賴四捨五入的對數。實際失敗概率可能更小,因為算子估計把所有支撐在壞集合上的向量都當作達到了最壞的壓縮率。
例題 5.1.8
(完整的失敗界計算)
設某輸入至多有四分之一的壞種子,且圖滿足所要求的絕對特徵值界限 。對八個漫步頂點,所有驗證器運行都失敗的概率至多為 。因此只要有一次運行成功就接受,則對該固定正例輸入,成功概率至少為 。該定理並不保證精確的成功概率等於這個值。
隨機性與算法成本
若 且 ,則初始頂點可用 個公平隨機位元抽取,此後每個均勻選取的鄰點用 個新的公平隨機位元,總共 個位元。互相獨立的均勻種子頂點則需要 個位元。當 遠小於 時,這一比較才有意義。對於大小不是 2 的冪的情形,精確的均勻抽樣需要明確指定的方法,並且必須分析其位元成本;簡單的取模約化可能產生偏差。
種子圖還必須能被算法實際使用。證明某個圖具有較小的非常數特徵值,本身並不等於有一個有效率的鄰點計算過程。具體的實現需要:頂點的表示、計算每個帶編號鄰點的方法、經過驗證的度數與譜保證,以及把每個頂點映射為驗證器種子的方法。驗證器的執行次數仍然是 ,所以隨機性的節省並不會自動減少運行時間。這些是對應用的條件,而不是譜不等式的額外結論。
均勻初始化是定理的一部分。若從某個固定頂點出發,且該頂點為壞頂點,則第一次造訪時全部為壞的概率就可能為一。預熱期可以使分佈接近均勻,但其近似誤差必須納入新的分析;所示表達式並不會悄悄地涵蓋它。類似地,壞種子的集合可以依賴於所固定的輸入,但證明是在考慮隨機漫步之前先固定該輸入的。
單邊錯誤的解釋
驗證器的單邊保證包含兩個部分。在正例輸入上,至多有指定比例的種子是壞的,因此重複造訪可以降低錯過所有好種子的概率。在負例輸入上,每個種子都必須拒絕。後一性質保證無論存在何種相關性,只要有一次運行接受就接受並不會引入假陽性。若負例輸入具有非零的假陽性率,則只要有一次運行接受就接受可能會放大該錯誤;此時需要單獨的分析和聚合規則。
該陳述在以下意義上對輸入是一致的:同一個數值界限適用於滿足假設的每個固定輸入。它並不自動蘊含一條隨機生成的漫步同時對所有可能的輸入都成功。要對有限的輸入族推出同時成立的陳述,可以對該族應用聯集界,代價是乘以該族的大小。對於無窮或非常大的輸入族,還需要更多結構。區分這些量詞可以避免誇大逐輸入的保證。
小圖中的直接驗證
考慮一個三角形,壞集合由單個頂點構成。這裏 ,,簡單隨機漫步的兩個非常數特徵值均為 ,所以 且 。定理把兩次連續造訪壞頂點的概率界定為 。事實上其概率為零:造訪了唯一的壞頂點之後,無自環的漫步必須移動到另一個頂點。這個例子既說明了該界限的正確性,也說明了它可能的寬鬆程度。一般的估計不能假定每個壞集合都具有這種特殊形狀。
當 時,事件概率恰好等於集合的相對大小,與圖無關。對於之後的步驟, 內部的邊的數目與排佈會產生影響。譜假設把這些與具體圖有關的細節壓縮為一個對給定大小的每個集合都有效的單一界限。兩個頂點數相同的壞集合可以有不同的內部邊和不同的實際全壞概率,儘管同一個上界對兩者都適用。
這些假設也解釋了失效的情形。若圖不連通,則某個非常數特徵向量可以具有特徵值一;從小連通分量出發的漫步會永遠留在其中。若連通圖是二分圖,則特徵值負一會使絕對譜界無法小於一。懶惰化的修改可以消除週期性,但必須為修改後的漫步重新計算其特徵值和位元成本。配套的譜混合單元對正則圖證明了這些事實;本單元則把由此得到的絕對界限作為假設使用。
總結
支撐在小集合上的向量,其均勻分量受該集合大小的限制。非均勻分量則按絕對譜界壓縮。這兩個事實合起來界定了帶遮罩的轉移算子,進而界定了整條漫步始終留在壞集合中的概率。
練習
快速檢查
(取 ,,,計算該界限。)
先計算 。
解答 · 答案
這裏 ,所以界限為 。
快速檢查
(為甚麼 且 蘊含 ?)
分解 。
解答 · 答案
由於 ,故 。
快速檢查
(當 為空集時,該定理給出甚麼?)
空集的 是多少?
解答 · 答案
此時 ,對每個 ,概率和界限都為零。
快速檢查
(僅有各頂點邊際分佈的界限能否建立全壞界?請說明。)
回想只有一個壞頂點的三角形。
解答 · 答案
不能。相繼的位置是相關的。證明所採用的是界定帶遮罩轉移算子乘積的範數。