簡介
本書適合作為高等院校計算機科學和套用數學專業高年級本科生與低年級研究生的教材，也適合作為數學工作者和科技人員的參考書。..
隨機化與機率技術在現代計算科學中起著重要的作用，其套用遍及組合最佳化、機器學習、通信網路以及安全協定等諸多領域。
本書詳細地介紹了機率技術以及在機率算法與分析發展中使用過的範例。本書分兩部分，第一部分介紹了隨機抽樣、期望、馬爾可夫不等式、切比雪夫不等式、切爾諾夫界、球和箱子模型、機率技術和馬爾可夫鏈等核心內容。第二部分主要研究連續機率、有限獨立性的套用、熵、馬爾可夫鏈蒙特卡羅方法、耦合、鞅和平衡配置等比較高深的課題。...
目錄
譯者序
前言.
第1章事件與機率
套用：驗證多項式恆等式
機率論公理
套用：驗證矩陣乘法
套用：最小割隨機化算法
練習
第2章離散隨機變數與期望
隨機變數與期望
期望的線性性
詹森不等式
伯努利隨機變數和二項隨機變數
條件期望
幾何分布
例：贈券收集問題
套用：快速排序的期望運行時間
練習
第3章矩與離差
馬爾可夫不等式
隨機變數的方差和矩
例：二項隨機變數的方差
切比雪夫不等式
例：贈券收集問題
套用：計算中位數的隨機化算法
算法
算法分析
練習
第4章切爾諾夫界
矩母函式
切爾諾夫界的導出和套用
泊松試驗和的切爾諾夫界
例：投擲硬幣
套用：估計參數
某些特殊情況下更好的界
套用：集合的均衡
套用：稀疏網路中的數據包路由選擇
超立方體網路上排列的路由選擇
蝶形網路上排列的路由選擇
練習
第5章球.c箱子和隨機圖
例：生日悖論
球和箱子模型
球和箱子模型
套用：桶排序
泊松分布
二項分布的極限
泊松近似
例：贈券收集問題再討論
套用：散列法
鏈散列
散列：二進制數字串
Bloom過濾器
放棄對稱性
隨機圖
隨機圖模型
套用：隨機圖中的哈密頓圈
練習
探索性作業
第6章機率方法
基本計數論證
期望論證
套用：求最大割
套用：最大可滿足性
利用條件期望消除隨機化
抽樣和修改
套用：獨立集合
套用：有較大圍長的圖
二階矩方法
套用：隨機圖的閾性質
條件期望不等式
洛瓦茲局部引理
套用：邊不相交的路徑
套用：可滿足性
利用洛瓦茲局部引理的顯式構造
套用：可滿足性算法
洛瓦茲局部引理：一般情況
練習
第7章馬爾可夫鏈及隨機遊動
馬爾可夫鏈：定義及表示
套用: 可滿足性的隨機化算法
套用：可滿足性的隨機化算法
狀態分類
例：賭徒的破產
平穩分布
例：簡單的佇列
無向圖上的隨機遊動
套用：s-t連通性算法
Parrondo悖論
練習..
第8章連續分布與泊松過程
連續隨機變數
R中的機率分布
聯合分布與條件機率
均勻分布
均勻分布的其他性質
指數分布
指數分布的其他性質
例：有反饋的球和箱子
泊松過程
到達間隔分布
組合與分解泊松過程
條件到達時間分布
連續時間馬爾可夫過程
例：馬爾可夫排隊論
均衡的M/M/1排隊
均衡的M/M/1/K排隊
M/M/∞排隊中的顧客?
練習
第9章熵 隨機性和信息
熵函式
熵和二項式係數
熵：隨機性的測度
壓縮
編碼：香農定理
練習
第10章蒙特卡羅方法
蒙特卡羅方法
套用：DNF計數問題
樸素算法
DNF計數問題的完全多項式隨機方案
從近似抽樣到近似計數
馬爾可夫鏈蒙特卡羅方法
Metropolis算法
練習
最小支撐樹的探索性作業
第11章馬爾可夫鏈的耦合
變異距離和混合時間
耦合
例：洗牌
例：超立方體上的隨機遊動
例：固定大小的獨立集合
套用：變異距離是不增的
幾何收斂
套用：正常著色法的近似抽樣
路徑耦合
練習
第12章鞅
鞅
停時
例：選舉定理
瓦爾德方程
鞅的尾部不等式
Azuma-Hoeffding不等式的套用
一般形式
套用：模式匹配
套用：球和箱子
套用：色數
練習
第13章兩兩獨立及通用散列函式
兩兩獨立
例：兩兩獨立的二進制數字的構造
套用：消去最大割算法的隨機性
例：構造關於一個素數模的兩兩獨立的值
兩兩獨立變數的切比雪夫不等式
套用：利用少量隨機二進制數字的抽樣
通用散列函式族
例：一個2維通用散列函式族
例：一個2維強通用散列函式族
套用：完美散列
套用：在數據流中尋找重量級的源終點
練習
第14章平衡配置
兩種選擇的影響力
上界
兩種選擇：下界
兩種選擇影響力的套用
散列
動態資源配置
練習
進一步閱讀材料
索引...
