2022/08/30 by Alex Infanger, Peter W. Glynn, Infanger, Alex +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #60J10 #60J22 #60J27 #60J45 #60J74 #65C40 #90C05 #90C90 #Bayesian Modeling and Causal Inference #FOS: Biological sciences #FOS: Mathematics #Gene Regulatory Network Analysis #Markov Chains and Monte Carlo Methods #Numerical Analysis (math.NA) #Probability (math.PR) #Quantitative Methods (q-bio.QM)
paper · pdf · doi:10.48550/arxiv.2208.14406
openalex publication_date 2022/08/30 · openalex created_date 2022/09/01 · openalex updated_date 2026/07/28
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.