本文首發(fā)在我的博客：《概率與計算》

這是一個挖坑貼，隨機算法是大數(shù)據(jù)算法中的重要的算法，《概率與計算》是講隨機算法的書中風(fēng)評比較好的，此外還有一本《數(shù)學(xué)女孩-隨機算法》。這本書比較偏理論，但是有很多算法領(lǐng)域的例子及其對應(yīng)的隨機算法和概率分析，有部分習(xí)題需要編程解決。刷完這本書的工程量比較大，這里先看下這本書里都有什么內(nèi)容。

《概率與計算：算法與數(shù)據(jù)分析中的隨機化和概率技術(shù)》 2019年
[美] 邁克爾·米森馬徹（Michael Mitzenmacher） 伊萊·阿法爾（Eli Upfal） 著

概率與計算

第一部分：Chap1~7，基礎(chǔ)

• Chap1~3: 復(fù)習(xí)基礎(chǔ)概率論，包括 random sampling, expectation, Markov’s inequality, variance, and Chebyshev’s inequality
• Chap4~7: 概率論高階內(nèi)容，包括 Chernoff bounds, balls-and-bins models, the probabilistic method, and Markov chains.

第二部分：Chap8~17，additional advanced topic，各章獨立

• 第1章　事件與概率
  • 1.1　應(yīng)用：驗證多項式恒等式
  • 1.2　概率論公理
  • 1.3　應(yīng)用：驗證矩陣乘法
  • 1.4　應(yīng)用：樸素貝葉斯分類器
  • 1.5　應(yīng)用：最小割隨機化算法

• 第2章　離散型隨機變量與期望
  • 2.1　隨機變量與期望
    • 2.1.1　期望的線性性
    • 2.1.2　詹森不等式
  • 2.2　伯努利隨機變量和二項隨機變量
  • 2.3　條件期望
  • 2.4　幾何分布
  • 2.5　應(yīng)用：快速排序的期望運行時間

• 第3章　矩與離差
  • 3.1　馬爾可夫不等式
  • 3.2　隨機變量的方差和矩
  • 3.3　切比雪夫不等式
  • 3.4　中位數(shù)和平均值
  • 3.5　應(yīng)用：計算中位數(shù)的隨機化算法
    • 3.5.1　算法
    • 3.5.2　算法分析

• 第4章　切爾諾夫界與霍夫丁界
  • 4.1　矩母函數(shù)
  • 4.2　切爾諾夫界的導(dǎo)出和應(yīng)用
    • 4.2.1　泊松試驗和的切爾諾夫界
    • 4.2.2　例：投擲硬幣
    • 4.2.3　應(yīng)用：估計參數(shù)
  • 4.3　某些特殊情況下更好的界
  • 4.4　應(yīng)用：集合的均衡
  • 4.5　霍夫丁界
  • 4.6　應(yīng)用：稀疏網(wǎng)絡(luò)中的數(shù)據(jù)包路由選擇
    • 4.6.1　超立方體網(wǎng)絡(luò)上排列的路由選擇
    • 4.6.2　蝶形網(wǎng)絡(luò)上排列的路由選擇

• 第5章　球、箱子和隨機圖
  • 5.1　例：生日悖論
  • 5.2　球放進箱子
    • 5.2.1　球和箱子模型
    • 5.2.2　應(yīng)用：桶排序
  • 5.3　泊松分布
  • 5.4　泊松近似
  • 5.5　應(yīng)用：散列法
    • 5.5.1　鏈散列
    • 5.5.2　散列：二進制數(shù)字串
    • 5.5.3　Bloom過濾器
    • 5.5.4　放棄對稱性
  • 5.6　隨機圖
    • 5.6.1　隨機圖模型
    • 5.6.2　應(yīng)用：隨機圖中的哈密頓圈
  • 5.8　探索性作業(yè)

• 第6章　概率方法
  • 6.1　基本計數(shù)論證
  • 6.2　期望論證
    • 6.2.1　應(yīng)用：求最大割
    • 6.2.2　應(yīng)用：最大可滿足性
  • 6.3　利用條件期望消除隨機化
  • 6.4　抽樣和修改
    • 6.4.1　應(yīng)用：獨立集合
    • 6.4.2　應(yīng)用：有較大圍長的圖
  • 6.5　二階矩方法
  • 6.6　條件期望不等式
  • 6.7　洛瓦茲局部引理
    • 6.7.1　應(yīng)用：邊不相交的路徑
    • 6.7.2　應(yīng)用：可滿足性
  • 6.8　利用洛瓦茲局部引理的顯式構(gòu)造
  • 6.9　洛瓦茲局部引理：一般情況
  • 6.10　洛瓦茲算法局部引理

• 第7章　馬爾可夫鏈及隨機游動
  • 7.1　馬爾可夫鏈：定義及表示
    • 7.1.1　應(yīng)用：2可滿足性的隨機化算法
    • 7.1.2　應(yīng)用：3可滿足性的隨機化算法
  • 7.2　狀態(tài)分類
  • 7.3　平穩(wěn)分布
  • 7.4　無向圖上的隨機游動
  • 7.5　Parrondo悖論

• 第8章　連續(xù)分布與泊松過程
  • 8.1　連續(xù)隨機變量
    • 8.1.1　R中的概率分布
    • 8.1.2　聯(lián)合分布與條件概率
  • 8.2　均勻分布
  • 8.3　指數(shù)分布
    • 8.3.1　指數(shù)分布的其他性質(zhì)
    • 8.3.2　例：有反饋的球和箱子
  • 8.4　泊松過程
    • 8.4.1　到達(dá)間隔分布
    • 8.4.2　組合與分解泊松過程
    • 8.4.3　條件到達(dá)時間分布
  • 8.5　連續(xù)時間馬爾可夫過程
  • 8.6　例：馬爾可夫排隊論
    • 8.6.1　均衡的M/M/1排隊
    • 8.6.2　均衡的M/M/1/K排隊
    • 8.6.3　M/M/∞排隊中的顧客數(shù)

• 第9章　正態(tài)分布
  • 9.1　正態(tài)分布
    • 9.1.1　標(biāo)準(zhǔn)正態(tài)分布
    • 9.1.2　一般單變量正態(tài)分布
    • 9.1.3　矩母函數(shù)
  • 9.2　二項分布的極限
  • 9.3　中心極限定理
  • 9.4　多維正態(tài)分布
  • 9.5　應(yīng)用：生成正態(tài)分布的隨機值
  • 9.6　最大似然點估計
  • 9.7　應(yīng)用：針對混合高斯分布的EM算法

• 第10章　熵、隨機性和信息
  • 10.1　熵函數(shù)
  • 10.2　熵和二項式系數(shù)
  • 10.3　熵：隨機性的測度
  • 10.4　壓縮
  • 10.5　編碼：香農(nóng)定理

• 第11章　蒙特卡羅方法
  • 11.1　蒙特卡羅方法
  • 11.2　應(yīng)用：DNF計數(shù)問題
    • 11.2.1　樸素算法
    • 11.2.2　DNF計數(shù)問題的完全多項式隨機方案
  • 11.3　從近似抽樣到近似計數(shù)
  • 11.4　馬爾可夫鏈蒙特卡羅方法
  • 11.6　最小支撐樹的探索作業(yè)

• 第12章　馬爾可夫鏈的耦合
  • 12.1　變異距離和混合時間
  • 12.2　耦合
    • 12.2.1　例：洗牌
    • 12.2.2　例:超立方體上的隨機游動
    • 12.2.3　例：固定大小的獨立集合
  • 12.3　應(yīng)用：變異距離是不增的
  • 12.4　幾何收斂
  • 12.5　應(yīng)用：正常著色法的近似抽樣
  • 12.6　路徑耦合

• 第13章　鞅
  • 13.1　鞅
  • 13.2　停時
  • 13.3　瓦爾德等式
  • 13.4　鞅的尾部不等式
  • 13.5　Azuma-Hoeffding不等式的應(yīng)用
    • 13.5.1　一般形式
    • 13.5.2　應(yīng)用：模式匹配
    • 13.5.3　應(yīng)用：球和箱子
    • 13.5.4　應(yīng)用：色數(shù)

• 第14章　樣本復(fù)雜度、VC維度以及拉德馬赫復(fù)雜度
  • 14.1　“學(xué)習(xí)”問題
  • 14.2　VC維度
    • 14.2.1　VC維度的其他例子
    • 14.2.2　增長函數(shù)
    • 14.2.3　VC維度的合成界
    • 14.2.4　ε-網(wǎng)和ε-樣本
  • 14.3　ε-網(wǎng)定理
  • 14.4　應(yīng)用：PAC學(xué)習(xí)
  • 14.5　ε-樣本定理
    • 14.5.1　應(yīng)用：不可知學(xué)習(xí)
    • 14.5.2　應(yīng)用：數(shù)據(jù)挖掘
  • 14.6　拉德馬赫復(fù)雜度
    • 14.6.1　拉德馬赫復(fù)雜度和樣本錯誤
    • 14.6.2　估計拉德馬赫復(fù)雜度
    • 14.6.3　應(yīng)用：二值分類的不可知學(xué)習(xí)

• 第15章　兩兩獨立及通用散列函數(shù)
  • 15.1　兩兩獨立
    • 15.1.1　例：兩兩獨立的二進制數(shù)字的構(gòu)造
    • 15.1.2　應(yīng)用：消去最大割算法的隨機性
    • 15.1.3　例：構(gòu)造關(guān)于一個素數(shù)模的兩兩獨立的值
  • 15.2　兩兩獨立變量的切比雪夫不等式
  • 15.3　通用散列函數(shù)族
    • 15.3.1　例：一個2維通用散列函數(shù)族
    • 15.3.2　例：強2維通用散列函數(shù)族
    • 15.3.3　應(yīng)用：完美散列
  • 15.4　應(yīng)用：在數(shù)據(jù)流中尋找重量級的源終點

• 第16章　冪律及相關(guān)的分布
  • 16.1　冪律分布：基本定義和性質(zhì)
  • 16.2　語言中的冪律
    • 16.2.1　Zipf定律和其他例子
    • 16.2.2　語言優(yōu)化
    • 16.2.3　猴子隨意打字
  • 16.3　偏好鏈接
  • 16.4　冪律在算法分析中的應(yīng)用
  • 16.5　其他相關(guān)的分布
    • 16.5.1　對數(shù)正態(tài)分布
    • 16.5.2　具有指數(shù)截斷的冪律

• 第17章　平衡分配和布谷鳥散列
  • 17.1　兩種選擇的影響力
  • 17.2　兩種選擇：下界
  • 17.3　兩種選擇影響力的應(yīng)用
    • 17.3.1　散列法
    • 17.3.2　動態(tài)資源分配
  • 17.4　布谷鳥散列
  • 17.5　布谷鳥散列的擴展
    • 17.5.1　帶刪除的布谷鳥散列
    • 17.5.2　處理故障
    • 17.5.3　更多的選擇和更大的箱子