School Colloquium——Mixing times and Hitting times for general Markov Processes
2019-08-30 15:00-16:00 Room 1114, Sciences Building No. 1
一般馬科夫鏈的mixing time和hitting time
Abstract: Nonstandard analysis, a powerful machinery derived from mathematical logic, has had many applications in probability theory as well as stochastic processes. Nonstandard analysis allows construction of a single object—a hyper?nite probability space—which satis?es all the ?rst order logical properties of a ?nite probability space, but which can be simultaneously viewed as a measure-theoretical probability space via the Loeb construction. As a consequence, the hyper?nite/measure duality has proven to be particularly in porting discrete results into their continuous settings.
In this talk, for every general-state-space discrete-time Markov process satisfying appropriate conditions, we construct a hyper?nite Markov process which has all the basic order logical properties of a ?nite Markov process to represent it. We show that the mixing time and the hitting time agree with each other up to some multiplicative constants for discrete-time general-state-space reversible Markov processes satisfying certain condition. Finally, we show that our result is applicable to a large class of Gibbs samplers and Metropolis-Hasting algorithms.
摘要：概率和統計學中的不少靈感來自于離散模型，但是現代概率問題往往通過測度論研究連續概率模型。 自Abraham Robinson 創造非標準分析以來，其一直扮演著連接離散數學和連續數學的橋梁。在非標準分析的環境下，積分可以被看做超限加法，布朗運動可以被看做超限隨機游走等等。
在本報告當中我們使用非標準分析來研究離散馬可夫鏈的mixing time和hitting time。Mixing time 一直是馬可夫鏈當中的一個關鍵概念因為其可被用來計量MCMC算法的效率。但是mixing time一般很難被直接估測。在Yuval Peres 和 Perla Sousi 的文章中，他們證明了有限可逆馬可夫鏈中mixing time和hitting time的等價性。對于一般離散馬可夫鏈， 我們用非標準分析構造超限馬可夫鏈。然后基于于超限馬可夫鏈和有限馬可夫鏈的相似性，我們將Yuval Peres 和 Perla Sousi 的結論延拓到滿足強Feller條件的一般馬可夫鏈。最后，我們說明Gibbs sampling 和 Metropolis-Hastings chain 的mixing time 和 hitting time 也滿足此關系。