Oct, 2013

有限马尔可夫链的绝对谱差通用混合时间上界

PDF
TL;DR该论文研究了有限马尔可夫链的总变差混合时间的上限，并给出了尖锐的结果，其中证明了线性递推关系和 Schur 函数之间的联系以及自然数平方和公式的推导。此外，该论文还提供了一个新的界限，这个界限不仅具有实际意义，而且可以解释许多理论现象。
markov chainspectral gapmixing timestationary timegeometry
发现论文，激发创造
  • 估计遍历马尔可夫链的混合时间

    研究了如何从 1 条路径中估计任意遍历有限状态 Markov 链的混合时间，引入了假谱间隙的概念，并构建了全经验置信区间，将精度优化至多项式依赖的最小稳态概率和假谱间隙。

    Feb, 2019

  • 进化集、混合与热核界

    文中引入的新的概率技术，在状态空间的等周特性（也称为传导度量限制或 Cheeger 不等式）方面取得了至今为止在总变化范数的混合时间上获得的最尖锐的边界，进而将 Lovasz 和 Kannan 得到的总变差混合时间界限推广到了一些更广泛的情形，同时仍然与等周不等式和热核界之间有着直接的联系。

    May, 2003

  • 马尔可夫链的马尔顿耦合和谱方法的集中不等式

    本文证明了 McDiarmid 不等式的一个版本适用于马尔可夫链，常数与链的混合时间成比例。我们还展示了马尔可夫链经验平均值的方差边界和伯恩斯坦型不等式。对于不可逆链，我们引入了一个名为 “伪谱间隙” 的新量，并显示它在不可逆链中发挥类似于谱间隙在可逆链中发挥的作用。我们用 Katalin Marton 的耦合构造和 Pascal Lezaud 的谱技术证明了这些结果。伪谱间隙推广了 Jim Fill 的乘法可逆化方法。

    Dec, 2012

  • 通过谱分布估计进行混合时间界限分析

    本文探讨了有限马尔科夫链的 Fabre-Krahn 不等式，证明了上下混合时间边界并获得更精细的混合时间收敛率估计，从而获得了可应用于多个模型的尖锐边界。

    May, 2005

  • 马尔可夫链的 Hoeffding 引理及其在统计学习中的应用

    本研究推广 Hoeffding 引理到一般状态空间和不一定可逆的马尔可夫链，并阐述了其在统计学和机器学习中的实用性。

    Feb, 2018

  • 马尔可夫链的 Chernoff-Hoeffding 界限：广义和简化

    该论文基于标准的 L_1 混合时间证明了一般性的非可逆有限状态马尔科夫链的 Chernoff-Hoeffding 边界。

    Jan, 2012

  • 从短轨迹中估计可逆 Markov 链的谱间隔

    该研究旨在探讨如何从观察到的 Markov Chain 中估计其谱隙，研究表明通过观察 $\tilde {O}(\frac {1}{\gamma \pi_\star})$ 步，就可以高概率地估计出其谱隙。

    Dec, 2016

  • 未调整的 Hamilton 蒙特卡罗混合时间保证

    该论文提出了一种上调和蒙特卡洛算法（uHMC），并提供了关于其马尔科夫链混合时间、总变差距离等指标的上限，证明了可在 log 级别的时间内实现精度为 ε 的近似目标分布，最终证明在两种模型下该算法的成功耦合可以实现这些上限。

    May, 2021

  • 大型随机可逆马尔可夫链的频谱：两个例子

    本文采用随机矩阵理论视角研究了随机环境下可逆马尔可夫链的频谱，针对两个简单模型的全局和边缘行为，包括所谓的谱间隙等进行了研究，两个模型均产生了具有非独立输入的随机矩阵。

    Nov, 2008

  • 几何平稳马尔可夫过程的谱理论和极限定理

    研究了一种具有几何遍历性质的马尔可夫链的部分和，包括其谱理论、乘法均值遍历定理、EdgeWorth 扩展、大偏差原理的限制和全局限制，以及与连续时间马尔可夫过程的拓展相关的内容。

    Sep, 2002