本課程中的若干分析,實際上都是關於平均值的陳述:隨機化排序的期望比較次數、雜湊表中的期望碰撞數、偶爾失敗的隨機化子程序的期望重複次數。每一個都是期望的計算,而同一個工具使它們都變得簡短:把所求的量寫成若干指示變量之和,再把各自的期望相加。本節建立只需計數的有限概率語言,證明兩個基本事實(期望的線性性與 Markov 不等式),並加以應用。本節以本章的計數各節為基礎,因為均勻概率就是兩個計數之比。
定義
定義 1.5.1
(有限概率空間與事件)
有限概率空間由有限集 (樣本空間)和函數 組成,滿足 。事件是子集 ,其概率為 。若對每個 有 ,則稱空間為均勻的,此時 。由定義得 ,並且對任意事件 ,並集界成立:
因為並集中每個結果在右邊至少被計算一次。若 ,則稱事件 獨立。當 時,條件概率為 。
定義 1.5.2
(隨機變量、期望與指示變量)
隨機變量是函數 。它的期望(均值)為
其中第二個和對 所取的有限多個值 求和;把取值相同的結果歸在一起,便知兩種寫法相等。事件 的指示變量是隨機變量 :當 時 ,否則為 。於是 。若對所有取值 都有 ,則稱隨機變量 獨立。
線性性與 Markov 不等式
定理 1.5.3
(期望的線性性)
設 是同一個有限概率空間上的隨機變量, 為實常數,則
不要求各 相互獨立。
證明
(交換兩個有限和)
按對結果求和的定義, ,其中交換了兩個有限和的次序。
定理 1.5.4
(Markov 不等式)
若 在每個結果上都有 ,且 ,則 。
證明
(在閾值處拆分求和)
把 的和拆成 的結果與其餘結果。每一項都非負,所以 。兩邊除以 即得。
定理 1.5.5
(獨立變量的乘積)
若 與 獨立,則 。
證明
(獨立性使求和分解)
按取值對分組,。
指示變量法。 要求某個「壞對象」個數 的期望 ,可寫 ,其中 是第 個候選對象為壞對象的事件。由線性性,。只需要各個概率 ,這些事件之間可能很複雜的相依關係完全不必考慮。
命題 1.5.6
(期望等待時間)
設某實驗每次試驗獨立地以概率 成功, 為第一次成功的試驗序號。則對 有 ,且 。
證明
(對尾概率求和)
事件 表示前 次試驗全部失敗,其概率為 。對取值於 的變量 ,有 ,因為 且各項非負(上述定義對非負變量可原樣推廣到可數樣本空間)。因此
例題
例題 1.5.7
(隨機排列的不動點)
設 是 的均勻隨機排列, 為其不動點個數。令 。滿足 的排列有 個,所以 。於是 ,對每個 都有 。各事件 並不獨立,但線性性並不需要獨立。
以 驗算,列出全部六個排列:恆等排列有 個不動點;三個對換各有 個;兩個 -循環各有 個。六個排列共有 個不動點,平均為 。
例題 1.5.8
(雜湊中的碰撞)
把 個鍵獨立且均勻地雜湊到 個槽。設 為落在同一槽的鍵對 的個數, 為鍵 與鍵 碰撞的事件。已知鍵 的槽,鍵 必須選同一個槽:。共有 對,所以 。當 、 時為 。因為 且取整數值,取 的 Markov 不等式給出 。
例題 1.5.9
(隨機排列的逆序數)
排列 的逆序是滿足 且 的一對位置。固定 ,排列 與把位置 上的值交換後得到的排列同樣可能出現,而且恰有一個在 處有逆序;所以 。共有 對,期望逆序數為 。當 時,六個排列 的逆序數為 ,總和 ,平均 。這也是插入排序處理隨機輸入次序時元素移位的期望次數。
例題 1.5.10
(期望重複次數)
某隨機化子程序每次獨立運行時,以概率 返回正確答案,並且可以識別答案是否正確。重複運行直到成功,需要 次,。若 ,則 ,且 。
常見錯誤與細節
反例模式
乘積公式不能去掉獨立性
一個誘人的說法是:像線性性一樣,對所有變量都有 。設 取 和 的概率各為 ,且 。則 ,所以 ,但 。這兩個變量並不獨立:。乘積公式需要上述定理中的獨立性假設;線性性則不需要。
常見錯誤
(把均值當作變量的典型取值)
期望是加權平均,不是變量通常取的值。骰子的均值是 ,卻永遠擲不出;第一個例題中不動點個數的均值為 ,但當 時以正概率等於 。
常見錯誤
(把期望搬進非線性函數內)
一般有 。設 在 上均勻,則 而 ; 而 。
常見錯誤
(過分解讀粗略的界)
並集界對任意事件都成立,但右邊可能超過 ,此時它甚麼也沒說明。Markov 不等式要求 ,所給的尾界也較粗;對於以概率 取 、否則取 的變量(均值為 ),它恰好取等號,說明其常數一般不能改進。
最後,用指示變量法時,必須按所述的隨機實驗計算 。在雜湊例題中,各鍵雜湊值的獨立性使 ;對較弱的雜湊族,則需另外證明 ,同一論證便給出上界。
練習
快速檢查
(擲一枚公平硬幣 次。求正面次數的期望,以及滿足「第 次與第 次都是正面」的位置 個數的期望。)
解答 · 答案
設 為第 次擲出正面的指示變量,。正面次數的期望為 。對相鄰位置,因為各次獨立,「第 次與第 次都是正面」的概率為 ,這樣的位置有 個,由線性性期望為 。
快速檢查
(設 是 的均勻隨機排列,下降是滿足 的位置 。求期望下降數,並對 求值。)
解答 · 答案
對固定的 ,值對 取 與取 同樣可能,所以 。共 個位置,期望為 ; 時等於 。
快速檢查
(一個非負隨機變量的均值為 。用 Markov 不等式界定 ,並給出一個隨機變量說明這個界不能改進。)
解答 · 答案
Markov 給出 。令 以概率 取 ,否則取 。則 ,,等號成立。
快速檢查
(某檢驗在每次獨立運行中,接受一個合數的概率至多為 。證明 次運行全都接受該合數的概率至多為 ,並求使其小於 的最小 。)
解答 · 答案
各次運行獨立,所以 次運行都接受該合數的概率是各次接受概率的乘積,每個至多為 ,故至多為 。要求 ,即 。因為 ,,所以最小的 為 。
練習 1.5.11
(兩個球獨立且均勻地投入 個箱子。分別用 (a) 指示變量和 (b) 按兩球是否落在同一箱作條件,求空箱個數的期望。)
核心
解答(3)
- 1
用指示變量計算
令 表示箱子 為空。這要求兩球都不落入該箱,所以 ,由線性性,空箱個數的期望為 。
- 2
按兩球是否落在同一箱作條件
以概率 ,第二個球與第一個球落在同一箱,此時有 個空箱;否則(概率 )有兩個箱子被佔用, 個為空。期望為 。
- 3
比較兩種方法
兩種方法都給出空箱個數的期望為 。