隨機算法不僅需要平均表現,還需要失敗概率的保證。集中不等式把隨機變量的資訊轉化為異常事件的概率界。我們先證明兩個基本界,再說明放大成功率時獨立性在哪裏起作用。
定義
定理 3.2.1
(馬爾可夫(Markov)不等式)
若 X≥0、a>0 且期望有限,則 Pr(X≥a)≤E[X]/a。
逐點有 X≥a1{X≥a}。兩邊取期望並除以 a 即得。
反例模式
沒有非負性,馬爾可夫不等式不成立
設 X 以各一半的概率取 100 或 −100。則 E[X]=0,若在 a=100 套用馬爾可夫界,會得到 Pr(X≥100)≤0,但真實概率為 1/2。只有當變量非負時,該不等式才成立。
定理 3.2.2
(切比雪夫(Chebyshev)不等式)
若 X 的均值為 μ、方差為有限數 σ2,則對 a>0,
Pr(∣X−μ∣≥a)≤a2σ2.
將馬爾可夫不等式應用於非負變量 (X−μ)2,閾值取 a2。
若獨立隨機變量 X1,…,Xn 具有共同均值 μ 和方差 σ2,其平均值 Xˉ 的方差為 σ2/n,因此 Pr(∣Xˉ−μ∣≥ε)≤σ2/(nε2)。獨立性使交叉協方差為零;分別給出均值和方差界時,無須要求同分佈。若右邊大於一,可改用概率的平凡上界一。
放大判定算法的成功率
假設每次獨立試驗以至少 2/3 的概率給出正確答案,進行奇數次 n 次試驗。令 Yi 為第 i 次失敗的指示變量,S=i∑Yi。於是 ES≤n/3,而獨立性給出 Var(S)=i∑pi(1−pi)≤n/4。多數投票失敗必有 S≥n/2,故 S−ES≥n/6。切比雪夫不等式給出
Pr(多數投票失敗)≤(n/6)2n/4=n9.
這是多項式下降的上界;更強的集中界可以得到指數下降。單純重複並不足夠:若所有答案複製同一次隨機試驗,多數投票的失敗概率與原來完全相同。僅知道錯誤次數的期望也不能證明獨立性。
練習
每次獨立運行得到一個方差為 4 的無偏估計。取 n=400 次的平均值,其方差為 0.01。當 ε=0.2 時,誤差至少為 0.2 的概率至多為 0.01/0.04=1/4;這不是說實際概率等於 1/4。
快速檢查
(非負隨機變量的期望為 3。求它至少為 12 的概率上界。)
取 a=12 套用馬爾可夫不等式。
解答 · 答案
馬爾可夫不等式給出 Pr(X≥12)≤3/12=1/4。
快速檢查
(獨立無偏估計的方差均至多為 9。為保證平均值偏離真值至少 1 的概率至多為 0.01,切比雪夫不等式需要多少次運行?)
對平均值套用切比雪夫不等式,其方差至多為 9/n。
解答 · 答案
平均值方差至多為 9/n,故概率至多為 9/n。取 n≥900 即可。這是充分條件,不一定是某個具體分佈的最小次數。
定理/命題
換一種尺度後仍可應用馬爾可夫不等式。若 λ>0 且 E[eλX] 有限,指數函數單調性給出
Pr(X≥a)=Pr(eλX≥eλa)≤e−λaE[eλX].
參數 λ 可以自由選擇。先計算或估計指數矩,再選使右邊小的參數,便得到有用的上界。這個推導本身不需要獨立性;對和的指數矩進行乘積分解時才需要獨立性。
定理 3.2.4
(獨立伯努利(Bernoulli)試驗的霍夫丁(Hoeffding)界)
設 Y1,…,Yn 獨立且服從伯努利分佈,不必同分佈,各自均值為 pi。令 S=i∑Yi、μ=ES。對每個 a>0,
Pr(S−μ≥a)≤e−2a2/n.
對均值為 p 的伯努利變量 Y,定義
g(λ)=logEeλ(Y−p).有 g(0)=g′(0)=0。求兩次導數得到 g′′(λ)=q(1−q)≤1/4,其中 q=peλ/(1−p+peλ);p=0,1 兩種端點情形可直接驗證。積分兩次得到當 λ≥0 時 g(λ)≤λ2/8。獨立性使指數矩分解,因此
Pr(S−μ≥a)≤exp(−λa+nλ2/8).取 λ=4a/n 即得結論。
證明透視
霍夫丁證明在哪裏用到各假設
各假設用在哪裏:每個 Yi 有界,給出 g′′≤1/4,因此不論均值 p 為何,都有二次上限 g(λ)≤λ2/8。獨立性只用一次,即把 n 個指數矩相乘。關鍵一步是用二階導數控制矩母函數的對數:因減去了均值,g(0)=g′(0)=0,而 g′′=q(1−q) 是傾斜後伯努利變量的方差。收尾一步是優化:−λa+nλ2/8 在 λ=4a/n 處最小,值為 −2a2/n。沒有獨立性便無法把矩相乘,本節稍後的重複反例就說明了這一點。
對獨立的判定試驗,若每次失敗概率至多為 1/3,多數失敗蘊含 S−ES≥n/6,因此概率至多為 e−n/18,隨試驗次數指數下降。若要它至多為 δ∈(0,1),取奇數 n≥18log(1/δ) 即可。這裏的對數為自然對數。結論針對固定輸入:每次試驗都須在同一輸入上滿足成功保證,並使用新的獨立隨機性。
例題詳解
假設每次獨立運行失敗概率恰為 1/3,取 n=180,並把票數相同視為失敗。前述切比雪夫界為 9/180=0.05,指數界為 e−10<0.000046。後者是保證,而非精確二項尾概率。多數投票通常取奇數次;若取 181 次,相應界分別為 9/181 和 e−181/18。如果只知道方差,卻沒有有界性或適當指數矩,即使較弱的界仍可能有用。
快速檢查
(100 個獨立伯努利變量的均值總和為 40。求它們的和至少為 50 的概率上界。)
解答 · 答案
取 a=10、n=100,霍夫丁界為 e−2(10)2/100=e−2。各變量不必有相同的成功概率。
單側與雙側界
上尾不等式控制高於均值的偏差。將它應用於獨立伯努利變量 1−Yi,便控制低於均值的偏差。再用聯集界合併兩個事件,得到
Pr(∣S−μ∣≥a)≤2e−2a2/n.
聯集界不要求這兩個事件獨立:由 1A∪B≤1A+1B 取期望即可。獨立性是在此前估計各指數矩時需要的。係數二來自需要覆蓋兩個偏差方向。右邊大於一時不等式仍成立,但沒有資訊;概率本來就不超過一。
對均值同為 p 的獨立伯努利樣本,令 S=np^,得到
Pr(∣p^−p∣≥ε)≤2e−2nε2.
要使它至多為 δ,取 n≥log(2/δ)/(2ε2) 即可。此界對未知的 p 一致成立,所以可在觀察樣本前確定樣本量。這是對隨機抽樣程序的保證,並非說固定觀察區間包含固定參數的概率是隨機的。
要以至多 0.05 的失敗概率把伯努利均值估計到誤差 0.1 以內,取 n≥log(40)/0.02≈184.44,所以 185 個獨立樣本足夠。這個界可能保守;它沒有聲稱 185 對所有分佈和估計方法都是最小樣本數。
同時估計多個量
假設要估計 m 個量,每個量內部使用獨立樣本。如果每個估計的誤差至少為 ε 的概率至多是 δ/m,聯集界說明至少一個估計失敗的概率至多為 δ。最後這一步不要求不同估計之間獨立。對伯努利樣本,每個量取
n≥2ε2log(2m/δ)
個樣本就足夠,其中 m 是正整數且 0<δ<1。對 m 的依賴是對數級,但若樣本不能共享,m 組數據仍可能需要 mn 個觀測。證明運行時間時必須計算實際抽樣成本,不能把概率界當作複雜度分析。
對 m=10、ε=0.1、δ=0.05,公式要求 n≥log(400)/0.02≈299.57,故每個量取 300 次觀測足夠。即使十個失敗事件高度相關,只要各自滿足概率界,聯集界仍成立。
相關性會破壞重複的效果
反例模式
沒有獨立性的重複
令 B 為單個伯努利變量,Pr(B=1)=1/3,並令每次試驗的失敗指示變量 Yi=B。每次試驗各自失敗的概率都是 1/3,但無論重複多少次,多數失敗恰在 B=1 時發生。此時 S=nB,所以 Var(S)=n2Var(B),而非 nVar(B);被遺漏的協方差項解釋了差別。
獨立隨機性是對聯合分佈的數學條件,不僅僅是把算法運行多次。重複使用隨機種子、共享隨機預處理或共享樣本都可能引入相關性。某些相關過程可以用別的集中方法分析,但需要單獨證明。
快速檢查
(五個估計器各自失敗的概率至多為 0.02。不假設它們獨立,至少一個失敗的概率有甚麼上界?)
解答 · 答案
聯集界給出 5(0.02)=0.10。事件不需要互斥或獨立;若它們重疊,概率相加可能重複計數。
快速檢查
(獨立伯努利樣本的均值為 p。要以至多 0.01 的失敗概率估計到誤差 0.05 以內,雙側界要求多少樣本?)
由 2e−2nε2≤δ 解出 n。
解答 · 答案
取 n≥log(200)/(2(0.05)2)=200log(200)≈1059.66 即可,故 1060 個樣本足夠。該界控制誤差大於或等於 0.05 的事件,因此也控制誤差嚴格大於 0.05 的事件。
僅知道期望能保證甚麼?
僅知道均值和非負性時,馬爾可夫界有時已無法改進。固定 0<μ<a,令 X 以概率 μ/a 取 a,其餘時候取零。則 EX=μ,而 Pr(X≥a)=μ/a,恰好達到馬爾可夫界。若要得到更強的普遍結論,必須加入分佈的其他資訊。
這對運行時間分析很重要。若非負運行時間 T 的期望至多為某個 M>0,馬爾可夫界給出 Pr(T≥10M)≤1/10。這不意味著每次運行都在 10M 內結束,也不意味著尾概率隨閾值指數下降。期望為 M 的算法仍可能偶爾運行很久;均值限制這些情況對平均值的貢獻,卻不能消除它們。
令 T 以概率 0.01 取 100,其餘時候取零。期望為一,但一次運行耗時 100 的概率為百分之一。事件 T≥100 的概率為 0.01,恰好達到馬爾可夫界 1/100。這是抽象模型;實際算法如有正的最小開銷,可加上一個常數。
常見錯誤
假設判定算法在每個輸入上的錯誤概率各自至多為 1/3。對一個固定輸入,使用新的獨立隨機性重複,便能應用多數投票界。但不能因此斷言某一次隨機選擇對所有可能輸入同時正確。若輸入集合有限且需要同時正確,可以嘗試對輸入使用聯集界,但必須把集合大小計入計算。如果輸入在隨機性公開後被適應性選擇,逐輸入保證的解釋也會改變,須另行論證。
例如,若有 m 個固定輸入,每個輸入放大後的失敗概率至多為 e−n/18,則至少一個輸入失敗的概率至多為 me−n/18。這裏不要求不同輸入的失敗事件獨立。取奇數 n≥18log(m/δ) 可使該界至多為 δ。當 δ<1 時,這證明存在一組對所有這些輸入都有效的隨機種子;但並不自動給出有效的確定性方法找到它。
快速檢查
(非負算法運行時間的期望至多為 20 秒。馬爾可夫不等式對超過 100 秒的概率給出甚麼結論?)
解答 · 答案
Pr(T>100)≤Pr(T≥100)≤20/100=0.2。不等式並不說明運行時間必定不超過 100 秒。
總結
可用假設決定適用的界。馬爾可夫不等式使用非負性和有限均值;切比雪夫不等式將它用於偏差的平方,並使用有限方差。這裏的指數界增加了獨立有界伯努利試驗的條件,得到更強尾界。聯集界合併失敗事件時不要求這些事件獨立。每次應用時,應先確定隨機試驗、目標事件和假設,再代入數值。上界可能不緊、大於一,也可能在特殊情況下達到;它並不自動等於精確概率。固定輸入的高概率保證也不同於對所有輸入同時成立的保證。假設失效時,即使公式看似合理,也可能有反例推翻結論。