第二十章：偏差與均值 — 動畫敘事
第二十集 · Ch.20 偏差與均值
離平均有
多遠？
多遠？
期望值告訴我們「平均」是多少，
但現實中每次結果都會偏離平均。
Markov 不等式和 Chebyshev 不等式
讓我們估計這個偏離有多嚴重。
但現實中每次結果都會偏離平均。
Markov 不等式和 Chebyshev 不等式
讓我們估計這個偏離有多嚴重。
變異數與標準差
衡量「散布程度」
變異數（Variance）：
標準差（Standard Deviation）：
獨立時的可加性：
若 X, Y 獨立，
Var[X] = E[(X-E[X])²] = E[X²] - (E[X])²標準差（Standard Deviation）：
σ = √Var[X]獨立時的可加性：
若 X, Y 獨立，
Var[X+Y] = Var[X] + Var[Y]
Markov 不等式
Markov 不等式
若 X ≥ 0，則對任意 a > 0：
直覺：如果平均值是 10，那麼超過 100 的機率最多是 10/100 = 10%。
限制：只需要知道期望值，但給出的上界通常很鬆。
Pr(X ≥ a) ≤ E[X] / a直覺：如果平均值是 10，那麼超過 100 的機率最多是 10/100 = 10%。
限制：只需要知道期望值，但給出的上界通常很鬆。
Chebyshev 不等式
Chebyshev 不等式
對任意 k > 0：
偏離均值超過 k 個標準差的機率最多是 1/k²：
k=2：至多 25%
k=3：至多 11%
k=4：至多 6.25%
Pr(|X - E[X]| ≥ k·σ) ≤ 1/k²偏離均值超過 k 個標準差的機率最多是 1/k²：
k=2：至多 25%
k=3：至多 11%
k=4：至多 6.25%
比 Markov 更緊的界——利用了變異數的資訊。
互動：Chebyshev 視覺化
2
觀念測驗
一個隨機變數期望值 50，標準差 10。由 Chebyshev 不等式，超過 80（即偏離 3σ）的機率上界是？
小結
機率不等式
給出保證
給出保證
Markov 和 Chebyshev 不等式讓我們
在不知道完整分布的情況下，
也能給出機率上界。
這在理論分析和演算法設計中極為重要。
在不知道完整分布的情況下，
也能給出機率上界。
這在理論分析和演算法設計中極為重要。
下一集（Ch.21）：隨機漫步與 PageRank
閱讀完整第二十章互動教材 →
1 / 7
本頁為動畫敘事版。看完後可前往 完整第二十章 進行互動練習。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)