报告人：Haosui Duanmu (University of California, Berkeley)
时间：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 hyperfinite probability space—which satisfies all the first order logical properties of a finite probability space, but which can be simultaneously viewed as a measure-theoretical probability space via the Loeb construction. As a consequence, the hyperfinite/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 hyperfinite Markov process which has all the basic order logical properties of a finite 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 也满足此关系。
相关附件
Haosui_cv.pdf
