吉布斯分佈的局部、動態與快速採樣算法






	購買中國簡體書籍請注意： 1. 因裝幀品質及貨運條件未臻完善，中國簡體書可能有出現磨痕、凹痕、折痕等問題，故簡體字館除封面破損、內頁脫落、缺頁等較嚴重的狀態外，其餘所有商品將正常出貨。


	目錄第1部分　緒論與預備知識第1章　緒論 1.1　研究背景2 1.2　研究問題6 1.3　主要成果11 1.4　本書結構與章節安排15 第2章　吉布斯分佈與預備知識 2.1　吉布斯分佈17 2.1.1　概率圖模型17 2.1.2　自旋系統與具體模型21 2.2　採樣與近似計數23 2.3　瑪律可夫鏈25 2.3.1　基本概念25 2.3.2　瑪律可夫鏈蒙特卡洛方法26 2.3.3　混合時間分析工具29 第2部分　分散式採樣第3章　分散式採樣總覽 3.1　分散式運算與LOCAL模型44 3.2　分散式採樣與分散式計數46 3.3　分散式採樣部分章節安排48 第4章　分散式採樣演算法 4.1　問題定義50 4.2　局部梅特羅波利斯演算法51 4.2.1　演算法與主要結論51 4.2.2　局部梅特羅波利斯演算法的平穩分佈54 4.2.3　局部梅特羅波利斯演算法的混合時間61 4.3　梅特羅波利斯演算法的分散式類比68 4.3.1　主要結論71 4.3.2　類比演算法74 4.3.3　演算法分析84 4.4　本章小結101 第5章　分散式採樣複雜性 5.1　分散式採樣下界102 5.2　分散式JerrumValiantVazirani（JVV）定理117 5.2.1　基本定義117 5.2.2　近似採樣和近似推斷之間的歸約122 5.2.3　分散式JVV採樣演算法123 5.3　強空間混合性質與分散式採樣/計數138 5.4　本章小結143 第3部分　動態採樣第6章　動態採樣總覽 6.1　研究背景146 6.2　問題定義147 6.3　主要結論149 第7章　條件吉布斯採樣技術 7.1　局部拒絕採樣演算法161 7.2　精確吉布斯採樣演算法164 7.3　正確性分析167 7.3.1　均衡條件167 7.3.2　局部拒絕採樣演算法均衡條件驗證174 7.3.3　精確吉布斯採樣演算法均衡條件驗證181 7.3.4　推廣版演算法185 7.4　收斂性分析189 7.4.1　局部拒絕採樣演算法收斂性分析189 7.4.2　精確吉布斯採樣演算法收斂性分析195 7.5　本章小結209 第8章　動態瑪律可夫鏈技術 8.1　動態吉布斯採樣演算法210 8.1.1　動態自旋系統上瑪律可夫鏈的耦合211 8.1.2　動態瑪律可夫鏈的資料結構215 8.1.3　動態吉布斯採樣演算法分析217 8.2　動態瑪律可夫鏈在推斷問題上的應用223 8.2.1　支援多參數更新的動態瑪律可夫鏈226 8.2.2　演算法的實現與分析233 8.3　本章小結241 第4部分　快速採樣演算法第9章　洛瓦茲局部引理採樣問題 9.1　研究背景244 9.2　主要結論246 9.3　基本定義與背景知識252 9.4　採樣演算法256 9.4.1　CNF公式滿足解採樣演算法256 9.4.2　狀態壓縮技術265 9.4.3　一般約束滿足問題採樣演算法273 9.5　演算法分析278 9.5.1　主定理證明279 9.5.2　投影策略的構造290 9.5.3　InvSample副程式分析301 9.5.4　混合時間分析316 9.6　局部引理問題實例的近似計數389 9.7　本章小結406 第10章　譜獨立性與混合時間 10.1　研究背景408 10.2　主要結論410 10.2.1　譜獨立性與吉布斯採樣演算法混合時間410 10.2.2　圖染色模型上的應用414 10.3　混合時間分析418 10.3.1　主定理證明418 10.3.2　局部隨機遊走的耦合423 10.4　圖染色模型的譜獨立性430 10.4.1　一般性定理的證明433 10.4.2　邊緣概率上界分析450 10.4.3　邊緣概率上界分析的緊致性456 10.5　本章小結458 致謝459 參考文獻462 附錄　文中部分專業名詞中英翻譯對照表481 攻讀博士學位期間的科研成果484 攻讀博士學位期間參與的科研課題486