跳转至

概率不等式

算法競賽中有時會用到 隨機化算法，這些算法的正確性與時空複雜度通常依賴於「某些隨機事件發生的概率很小」這一前提。例如，快速排序的複雜度依賴於「所選的 pivot 元素幾乎是最小或最大元素」這一事件較少發生。

本文將簡要介紹一些用於分析隨機化算法的工具並給出幾個簡單應用的例子。

Union Bound

記 \(A_1, \cdots, A_m\) 為隨機事件，則

\[ P\left\{ \bigcup_{i=1}^m A_i \right\} \leq \sum_{i=1}^m P\{A_i\} \]

即：一組事件中至少一個發生的概率，不超過每一個的發生概率之和。

實際上，這一結論還可以稍作加強：

  • 一組事件中至少一者發生的概率，不小於 每一個的發生概率之和，減掉每兩個同時發生的概率之和。
  • 一組事件中至少一者發生的概率，不超過 每一個的發生概率之和，減掉每兩個同時發生的概率之和，加上每三個同時發生的概率之和。
  • ……

隨着層數越來越多，交替出現的上界和下界也越來越緊。這一系列結論形式上類似容斥原理，證明過程也和容斥類似，這裏略去。

Markov 不等式

設 \(X\) 是一個取值非負的隨機變量，則對任意正實數 \(a\) 有

\[ P\{ X \geq a \} \leq \frac{EX}{a} \]

事實上，由於 Markov 不等式本身並沒有用到隨機變量除期望外的與分佈有關的任何信息，因此直接應用這個不等式得到的約束通常很鬆。

證明

記 \(I\) 為事件 \(X \geq a\) 的示性函數，則有

\[ I \leq \frac{X}{a} \]

進而

\[ P\{ X \geq a \} = EI \leq E \left[ \frac{X}{a} \right] = \frac{EX}{a} \]

Chebyshev 不等式

設 \(X\) 是一隨機變量，則對任意的 \(a > 0\) 都有

\[ P \{ |X - EX| \geq a \} \leq \frac{DX}{a^2} \]

特別地，當 \(a\) 取 \(k\sigma\) 時有

\[ P \{ |X - EX| \geq k\sigma \} \leq \frac{1}{k^2} \]

其中 \(\sigma\) 是 \(X\) 的標準差。

證明

由已知，有

\[ P \{ |X - EX| \geq a \} = P \{ (X - EX)^2 \geq a^2 \} \]

注意到 \((X - EX)^2\) 非負，故由 Markov 不等式可知

\[ P \{ (X - EX)^2 \geq a^2 \} \leq \frac{E(X - EX)^2}{a^2} = \frac{DX}{a^2} \]

Chernoff 不等式

一般的 Chernoff 不等式可以從直接對隨機變量 \(\mathrm{e}^{tX}\) 應用 Markov 不等式得出：

設 \(X\) 是一隨機變量，則對任意的 \(t > 0\) 都有

\[ P\{ X \geq a \} = P\{ \mathrm{e}^{tX} > \mathrm{e}^{ta} \} \leq \frac{E \mathrm{e}^{tX}}{\mathrm{e}^{ta}} \]

類似地，當 \(t < 0\) 時有

\[ P\{ X \leq a \} = P\{ \mathrm{e}^{tX} > \mathrm{e}^{ta} \} \leq \frac{E \mathrm{e}^{tX}}{\mathrm{e}^{ta}} \]

Poisson 試驗之和的 Chernoff 不等式

算法競賽中涉及的隨機變量通常沒有那麼「一般」，我們可以用概率論中的 Poisson 試驗對其進行描述。

所謂 Poisson 試驗，是指在只有兩種可能結果的隨機試驗。

一次的 Poisson 試驗的結果可以用一個取值為 \(0\) 或 \(1\) 的隨機變量 \(X\) 進行刻畫，其概率分佈為

\[ P\{ X = i \} = \begin{cases} p_i, & i = 1 \\ 1 - p_1, & i = 0 \end{cases} \]

對於 Poisson 試驗，我們有如下結論：

對於 \(n\) 個獨立的 Poisson 試驗 \(X_1, X_2, \cdots, X_n\)，記 \(X = \sum_{i=1}^{n} X_i\) 以及 \(\mu = EX\)，則對任意 \(0 < \epsilon < 1\) 有

\[ P\left\{ |X - \mu| \geq \epsilon \mu \right\} \leq 2 \exp\left( - \frac{1}{3} \mu \epsilon^2 \right) \]

Hoeffding 不等式

若 \(X_1, \cdots, X_n\) 為互相獨立的實隨機變量且 \(X_i\in [a_i,b_i]\)，記隨機變量 \(X=\sum\limits_{i=1}^n X_i\)，則

\[ P\{ |X - EX| \geq \epsilon \} \leq 2\exp \left( \frac {-2\epsilon^2}{\sum\limits_{i=1}^n (b_i-a_i)^2} \right) \]

Chernoff 不等式和 Hoeffding 不等式都限制了隨機變量偏離其期望值的程度。這兩個不等式的證明過程較為冗長，有興趣的同學可以查閲 Probability and Computing 一書中的相關章節。

從經驗上講，如果 \(EX\) 不太接近 \(a_1+\cdots+a_n\)，則該不等式給出的界往往相對比較緊；如果非常接近的話（例如在 UOJ #72 全新做法 中），給出的界則往往很鬆，此時更好的選擇是使用 Chernoff 不等式。

應用舉例

例：隨機撒點估算圓周率

考慮下列估計圓周率 \(\pi\) 的精確值的算法：

在正方形區域 \([-1, 1]^2\) 內隨機生成 \(n\) 個點，記其中落入單位圓盤 \(x^2 + y^2 \leq 1\) 的點數為 \(m\)，則可以取 \(\dfrac{4m}{n}\) 為 \(\pi\) 的近似值。

問題：若要保證上述算法以至少 \((1 - \delta)\) 的概率返回相對誤差不超過 \(\epsilon\) 的結果，\(n\) 應該如何取定？

解答

記 \(X_i\) 表示事件「隨機生成的第 \(i\) 個點在單位圓內」，則圓內總點數 \(X = \sum_{i=1}^{n} X_i\)。我們需要找到一個合適的 \(n\) 使得

\[ P\left\{ \left| \frac{4X}{n} - \pi \right| \geq \epsilon \pi \right\} \leq \delta \]

上式等價於

\[ P\left\{ \left| X - \frac{\pi}{4}n \right| \geq \epsilon \cdot \frac{\pi}{4}n \right\} \leq \delta \]

根據 Chernoff 不等式，我們只需令

\[ 2 \exp\left( - \frac{1}{3} \epsilon^2 \cdot \frac{\pi}{4}n \right) \leq \delta \]

即可，由此可解得

\[ n \geq \frac{12}{\pi} \epsilon^{-2} \ln \frac{2}{\delta} \]

即當 \(n = \Omega(\epsilon^{-2} \ln \frac{1}{\delta})\) 時可以達到需要的準確率。

例：抽獎問題

一個箱子裏有 \(n\) 個球，其中恰有 \(k\) 個球對應着大獎。你要進行若干次獨立、等概率的隨機抽取，每次抽完之後會把球放回箱子。請問抽多少次能保證以至少 \((1 - \epsilon)\) 的概率，滿足 每一個 獎球都被抽到至少一次？

解答

假如只有一個獎球，則抽取 \(M=n\log\epsilon^{-1}\) 次即可保證，因為 \(M\) 次全不中的概率

\[ \Big(1-\dfrac 1n\Big)^{n\log\epsilon^{-1}}\leq e^{\log\epsilon}=\epsilon \]

現在有 \(k>1\) 個獎球，那麼根據 Union Bound，我們只需保證每個獎球被漏掉的概率都不超過 \(\dfrac \epsilon k\) 即可。於是答案是 \(n \log \dfrac{k}{\epsilon}\)。

例：隨機選取一半元素

給出一個算法，從 \(n\) 個元素中等概率隨機選取一個大小為 \(\dfrac{n}{2}\) 的子集，保證 \(n\) 是偶數。你能使用的唯一的隨機源是一枚均勻硬幣，同時請你儘量減少拋硬幣的次數（不要求最少）。

解法

首先可以想到這樣的算法：

  • 通過拋 \(n\) 次硬幣，可以從所有子集中等概率隨機選一個。
  • 不斷重複這一過程，直到選出的子集大小恰好為 \(\dfrac n2\)。
    • 注意到大小為 \(\dfrac n2\) 的子集至少佔所有子集的 \(\dfrac 1n\)，因此重複次數的期望值 \(\leq n\)。

這一算法期望需要拋 \(n^2\) 次硬幣。

另一個算法：

  • 我們可以通過拋期望 \(2\lceil\log_2 n\rceil\) 次硬幣來實現隨機 \(n\) 選 1。
    • 具體方法：隨機生成 \(\lceil\log_2 n\rceil\) 位的二進制數，如果大於等於 \(n\) 則重新隨機，否則選擇對應編號（編號從 0 開始）的元素並結束過程。
  • 然後我們從所有元素中選一個，再從剩下的元素中再選一個，以此類推，直到選出 \(\dfrac n2\) 個元素為止。

這一算法期望需要拋 \(n\lceil\log_2 n\rceil\) 次硬幣。

將兩個算法縫合起來：

  • 先用第一個算法隨機得到一個子集。
  • 如果該子集大小不到 \(\dfrac n2\)，則利用第二個算法不斷添加元素，直到將大小補到 \(\dfrac n2\)。
  • 如果該子集大小超過 \(\dfrac n2\)，則利用第二個算法不斷刪除元素，直到將大小削到 \(\dfrac n2\)。

嘗試分析第二、第三步所需的操作次數（即添加/刪除元素的次數）：

  • 記 01 隨機變量 \(X_i\) 表示 \(i\) 是否被選入初始的子集，令 \(X:=X_1+\cdots+X_n\) 表示子集大小，則第二、第三步所需的操作次數等於 \(\big|X-\mathrm{E}[X]\big|\)。在 Hoeffding 不等式中取 \(t=c\cdot\sqrt n\)（其中 \(c\) 為任意常數），得到 \(\mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\leq 2\mathrm{e}^{-c^2}\)。也就是説，我們可以通過允許 \(\Theta(\sqrt n)\) 級別的偏移，來得到任意小的常數級別的失敗概率。

至此我們已經説明：該算法可以以很大概率保證拋硬幣次數在 \(n+\Theta(\sqrt n\log n)\) 以內。

  • 其中 \(n\) 來自獲得初始子集的拋硬幣次數；\(\Theta(\sqrt n\log n)\) 是 \(\Theta(\sqrt n)\) 次添加/刪除元素的總開銷。
計算期望複雜度

我們再從另一個角度分析，嘗試計算該算法的期望拋硬幣次數。

用 Hoeffding 不等式求第二、第三步中操作次數期望值的上界：

\[ E|X - EX| = \int_0^\infty P\{ |X - E[X]| \geq t \} \mathrm{d}t \leq 2 \int_0^\infty \exp \left(-\frac {t^2}{n}\right) \mathrm{d}t=\sqrt{\pi n} \]

從而第二、第三步所需拋硬幣次數的期望值是 \(\sqrt{\pi n}\cdot2\lceil\log_2 n\rceil\)。

綜上，該算法期望需要拋 \(n+2\sqrt{\pi n}\lceil\log_2 n\rceil\) 次硬幣。

練習：Balls and Bins

\(n\) 個球獨立隨機地扔到 \(n\) 個盒子裏，試證明：球最多的盒子中的球數以 \(1 - \dfrac{1}{n}\) 的概率不少於 \(\Omega \left( \dfrac{\log n}{\log \log n} \right)\)。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用