Absorption in Time-Varying Markov Chains: Graph-Based Conditions

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number9165769
Pages (from-to)1127-1132
Number of pages6
JournalIEEE Control Systems Letters
Volume5
Issue number4
DOIs
StateSubmitted - Oct 1 2021

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

Keywords

  • Markov processes
  • stochastic systems
  • switched systems

Fingerprint

Dive into the research topics of 'Absorption in Time-Varying Markov Chains: Graph-Based Conditions'. Together they form a unique fingerprint.

Cite this