论文标题
Markov链均衡分布具有可计算误差边界的新型截断算法
A New Truncation Algorithm for Markov Chain Equilibrium Distributions with Computable Error Bounds
论文作者
论文摘要
本文介绍了一种用于计算Markov链和Markov跳跃过程的新算法，用于计算数值平衡（即固定）分布，具有很大的有限状态空间或无数的无限状态空间。该算法基于平衡期望的比率表示，其中分子和分母对应于在给定返回集合集合$ k $内启动和结束的路径上定义的期望。当$ k $是单身人士时，这种表示是再生过程理论的众所周知的结果。对于计算障碍，我们忽略了对与给定截断集合$ a $ a $ a $ a $ a $ a $ a the the the Path期望的贡献。这产生了一种截断算法，该算法被证明是$ a $变大。此外，在存在合适的Lyapunov函数的情况下，我们可以绑定路径期望，从而为我们的数值过程提供可计算和收敛的误差界限。我们的论文还提供了与其他两种具有可计算误差界的截断方法的计算比较。结果与观察结果保持一致：我们的边界具有关联的计算复杂性，通常随着截断集变大，通常会更好地扩展。
This paper introduces a new algorithm for numerically computing equilibrium (i.e. stationary) distributions for Markov chains and Markov jump processes with either a very large finite state space or a countably infinite state space. The algorithm is based on a ratio representation for equilibrium expectations in which the numerator and denominator correspond to expectations defined over paths that start and end within a given return set $K$. When $K$ is a singleton, this representation is a well-known consequence of regenerative process theory. For computational tractability, we ignore contributions to the path expectations corresponding to excursions out of a given truncation set $A$. This yields a truncation algorithm that is provably convergent as $A$ gets large. Furthermore, in the presence of a suitable Lyapunov function, we can bound the path expectations, thereby providing computable and convergent error bounds for our numerical procedure. Our paper also provides a computational comparison with two other truncation methods that come with computable error bounds. The results are in alignment with the observation that our bounds have associated computational complexities that typically scale better as the truncation set gets bigger.
