第 9 章 機率與統計演算法#

前面各章的演算法大多「給定輸入，答案就確定了」；這一章引入不確定性——隨機數、期望值、統計推論。機率不是旁支：蒙地卡羅積分（6.3 節）的理論基礎、密碼學金鑰的安全性（第 2 章）、Pollard ρ 的隨機性（3.3 節），全都站在本章的概念上。

9.1 節隨機數產生器：電腦其實不會「擲骰子」，它產生的是偽隨機數——由確定性演算法生成的、統計性質像隨機的數列。你將實作線性同餘產生器（LCG），親眼看到它的週期與相關性缺陷，並學會區分「一般用途的 PRNG」與「密碼學安全的 CSPRNG」。9.2 節期望值與變異數：兩個描述隨機變數的核心量，加上「不重要抽樣/反變換法」等把均勻隨機數變成任意分布的技術，並用模擬驗證大數法則與中央極限定理。9.3 節假設檢定的計算實作：t 檢定與卡方檢定的完整計算流程——統計量怎麼算、p 值怎麼來、結論怎麼下，全部落成程式碼。

本章的方法論特色是「模擬即驗證」：每個理論公式（期望值、信賴區間、p 值）都可以用十萬次模擬交叉檢驗。養成這個習慣，統計公式對你將不再是背誦的黑盒，而是可以動手驗證的演算法。