基於期望往返時間之馬可夫鏈蒙地卡羅法收斂速率分析

Abstract

馬可夫鏈蒙地卡羅法被廣泛運用於高維度分佈之抽樣，並且至今已經有大量的研究被投入於優化此演算法；無論是基於經驗法則或是理論證明，學界已經發現加速此演算法收斂速度的關鍵之一，是令演算法快速地漫步於抽樣空間裡。在這篇論文裡，我們算出演算法的漸進變異數與期望往返時間的關係；基於此我們證明了樹狀馬可夫鏈無法被均勻加速的猜法、提供了一個新的方法推導離散時間最優馬可夫鏈，並且更進一步推導出連續時間最優馬可夫過程。

Markov chain Monte Carlo(MCMC) is a popular strategy for sampling high dimensional distribution, and researches have been devoted to optimize the sampler. It has been known both heuristically and theoretically that a good sampler should travel fast among states in order to attain better convergence. In this thesis, the relation between the asymptotic variance of the sampler and the mean commute time is derived explicitly. Based on this relation, the conjecture in Chen and Hwang(2013) is shown rigorously; also, an alternative derivation of the optimal Markov chain presented in Chen et al.(2012) is given, and is further extended to construct the optimal Markov process under the average case criterion.