论文标题
随时间变化的马尔可夫链的吸收：基于图的条件
Absorption in Time-Varying Markov Chains: Graph-Based Conditions
论文作者
论文摘要
我们研究吸收，即几乎确定在具有有限状态空间的时变（非均匀）离散时间马尔可夫链中，几乎可以确保收敛到吸收状态。我们考虑可以在有限的过渡矩阵中切换的系统，我们称之为模式。我们的分析集中在两个属性上：1）几乎确定在任何切换下融合了吸收状态，以及2）几乎可以通过适当的切换策略确定收敛到所需的一组吸收状态。我们根据模式过渡图的结构得出必要和充分的条件。更具体地说，我们表明，当且仅当可从任何最初的状态中，当这些吸收状态与简化过渡图的结合中达到任何状态时，可以确保几乎确定从任何初始状态的所需吸收状态收敛的切换策略。然后，我们显示了三个足够的条件，可以在任意切换下吸收。虽然前两个条件取决于简化过渡图的联合（相交）的无环（弱环），但第三条件基于每个模式中每个状态与吸收状态的距离。这些图理论条件只能基于每种模式下过渡的可行性来验证吸收状态的稳定性和稳定性。
We investigate absorption, i.e., almost sure convergence to an absorbing state, in time-varying (non-homogeneous) discrete-time Markov chains with finite state space. We consider systems that can switch among a finite set of transition matrices, which we call the modes. Our analysis is focused on two properties: 1) almost sure convergence to an absorbing state under any switching, and 2) almost sure convergence to a desired set of absorbing states via a proper switching policy. We derive necessary and sufficient conditions based on the structures of the transition graphs of modes. More specifically, we show that a switching policy that ensures almost sure convergence to a desired set of absorbing states from any initial state exists if and only if those absorbing states are reachable from any state on the union of simplified transition graphs. We then show three sufficient conditions for absorption under arbitrary switching. While the first two conditions depend on the acyclicity (weak acyclicity) of the union (intersection) of simplified transition graphs, the third condition is based on the distances of each state to the absorbing states in all the modes. These graph theoretic conditions can verify the stability and stabilizability of absorbing states based only on the feasibility of transitions in each mode.
