為何證明特例?
現有隨機複雜度筆記使用 Hoeffding 不等式,但沒有在該處證明。這裏用對數矩估計及 Markov 不等式證明其多數表決論證所需的 Bernoulli 指示變量特例;我們不證明任意 值隨機變量的一般定理。
固定一個輸入。令 為獨立 Bernoulli 隨機變量,其中 且 。 可以不同,也可等於零或一。令 、。在應用中, 是「隨機算法第 次獨立運行出錯」的指示變量,所以 是出錯運行的次數。我們要對每個 證明 。
控制單個中心化矩
證明建基於單個 Bernoulli 變量的一個函數。
定義 6.1.1
(Bernoulli 變量的中心化對數矩)
設 為 Bernoulli 變量,。其矩母函數為
對每個實數 都為正。中心化對數矩定義為
右邊的等式成立,是因為 是常數,可以提出期望之外。下一個命題說明 至多二次增長,而且與 無關。
引理 6.1.2
(Bernoulli 矩界)
對每個 及每個 ,
證明
(對有界二階導數積分兩次)
令 。對 微分得 ;再微分並利用 ,得
又 ,。由 得 ,所以處處有 。從 積分到 得 ,再積分一次得 。
過程中沒有除以 或 ,所以 和 也包括在內。
從矩到尾概率
定理 6.1.3
(獨立 Bernoulli 和的指數尾界)
設 為獨立 Bernoulli 變量,,並令 、。對每個 ,
證明
(Markov、分解、最優化)
對任意 ,把 Markov 不等式用於非負隨機變量 ,得到
獨立性使期望分解成各中心化矩的乘積,再對每個因子使用矩界:
因此對每個 都有 。指數是 的凸二次式,在 時最小;因 且 ,此值為正。代入得 。
證明透視
每個假設在哪裏發揮作用
證明有三步,每步恰好用到一個假設。Markov 不等式需要非負變量,所以我們先取指數,而不直接處理 ; 使事件 變成事件 。乘積步驟是唯一用到獨立性的地方。其後矩界逐個因子使用,所以 不必相等,而 的變量只貢獻因子 。最後取 ,是在線性收益 與二次代價 之間取捨;它是唯一的自由參數,而之所以可以這樣取,是因為引理對所有 成立。若沒有獨立性,單項的矩界無法說明乘積的期望。
乘積這一步並非技術細節。下面的例子放棄獨立性,說明所述的界隨即失效。
反例模式
完全相關的運行使上界失效
斷言:無論是否獨立,任意 Bernoulli 變量都滿足 。取 及 ,其中 是同一個公平位元。每個 都是 的 Bernoulli 變量,故 ,但 以各 的概率取 或 。取 ,事件 恰是 ,概率為 。斷言所給的界為 ,所以斷言不成立。獨立性使 成為乘積;這裏 ,比各邊緣矩的乘積 更大。
多數表決放大與精確核對
推論 6.1.4
(獨立運行的多數表決)
設 為奇數。假設在固定輸入上的 次運行相互獨立,且各自出錯的概率至多為 。則多數答案錯誤的概率至多為 。
證明
(把門檻平移 )
令 指示第 次運行出錯,則 。多數錯誤要求 ,所以 。取 用尾界,,所以多數錯誤的概率至多為 。
這是上界,一般不是精確錯誤概率。下面的例題分開不等式的兩種用途:先在小得可以精確計算的情形核對,再用它決定重複次數。
例題 6.1.5
(三個公平位元的精確核對)
令 為獨立公平位元,所以 、,取 。事件 恰是 ,概率為 。上界為 。確實 :界有效但不緊。這個例子核對的是尾界本身,並非滿足「錯誤率至多 」的多數表決例子。
例題 6.1.6
(要運行多少次才能令錯誤至多 ?)
由多數表決推論, 次( 為奇數)獨立運行、各自錯誤率至多 ,則多數錯誤的概率至多為 。要使 ,即 ,所以 。滿足此式的最小奇數是 。核對: 時 ,保證不適用; 時 。另外, 時上界為 。這個界給出的是充分的次數,不一定是最少的次數。
例題 6.1.7
(退化與不等的概率)
令 、, 為公平位元,三者獨立,所以 、、。則 。取 :事件 即 ,概率為 ;上界為 ,有效。各中心化矩為 、、,所以兩個確定性變量沒有貢獻。定理仍除以完整的 ,因此這裏遠非尖銳。證明並不要求 。
常見錯誤
(把指數式當成錯誤概率)
是在「每次運行出錯概率至多 」這個較弱假設下得到的上界,並不是多數錯誤的概率。在三個公平位元的核對中,精確概率是 ,而界是 。這類量應當作為保證來報告,不能當作實際錯誤的估計。
常見錯誤
(把單邊界用於雙邊事件)
定理只界定 。對事件 ,要再對 用定理(它們是獨立 Bernoulli 變量,以 取代 ),然後用聯集界,所得為 。同樣, 是絕對偏差:偏差 即 ,得 。
習題與解答
快速檢查
(若 , 是多少?)
先計算 。
解答 · 答案
時 ,所以 ,且 。因此對所有 都有 ,顯然滿足 。所以退化情形無須另行處理。
快速檢查
(為何證明中可取 ?)
檢查對 的正負要求。
解答 · 答案
假設 和 使 為正,這正是 Markov 步驟及矩界所需的條件。它也令二次指數 最小,因為導數 在此點為零。
快速檢查
(獨立性在證明的哪一步使用?)
找出把一個期望變成多個期望的步驟。
解答 · 答案
只在把 分解為各 的乘積時使用。Markov 不等式、單個變量的矩界以及對 的最優化都沒有用到它。
快速檢查
(在三個公平位元的核對中,界 等於精確概率嗎?)
與 比較。
解答 · 答案
不等於。精確概率為 ,而 。指數式只是有效的上界,並非等式。