馬可夫不等式（Markov's inequality）
/ MAR-kov /
假設你只知道一座城市的平均通勤時間——比如 30 分鐘——其他一概不知。會不會有四分之一的通勤者每人花 4 小時？不會：若太多人通勤時間巨大，平均就必然超過 30 分鐘。馬可夫不等式正是把這個常識上限變精確：一個非負的量不能太常遠高於它的平均，因為高值會把平均拉高。
精確地說：若 X 是非負隨機變數且 a > 0，則 Pr[X >= a] <= E[X] / a。證明是一行的記帳論證。由於 X >= 0，期望 E[X] 至少包含那些 X >= a 的結果所貢獻的部分，而每個這樣的結果至少貢獻 a；所以 E[X] >= a 乘以 Pr[X >= a]，兩邊除以 a 即得此界。一個好用的改寫：X 超過其平均 k 倍的機率最多為 1/k——所以 X 至少是平均 10 倍的情形，至多 10% 的時間發生。這正是讓你把拉斯維加斯演算法變成蒙地卡羅的依據：若期望時間為 mu，跑超過 2 mu 的機率最多為二分之一，因此在 2 mu 截斷只有一半的時間失敗。
馬可夫不等式之所以重要，是因為它幾乎什麼都不需要——只要非負性與平均——使它成為最早、最容易的尾界，也是更強尾界的基石（切比雪夫把馬可夫用在平方偏差上；切爾諾夫把它用在指數上）。它的誠實也是它的弱點：只知道平均，這個界往往很鬆。有了更多資訊——已知變異數，或各部分間的獨立性——切比雪夫與切爾諾夫給出緊得多、指數般小的界。馬可夫是地板，不是天花板。
若某演算法平均做 1000 次比較，那麼它做至少 10000 次比較的機率最多為 1000/10000 = 1/10。僅憑平均你就只能推到這裡——現實中可能好得多，但絕不會比這更差。
Pr[X >= k 倍平均] <= 1/k，僅憑平均即可——簡單但寬鬆。
馬可夫要求 X 非負；用在可能變負的量上會得出胡言。又因為它只用平均，請預期它很鬆——當你還知道變異數或有獨立性時，改用切比雪夫或切爾諾夫。