A New Truncation Algorithm for Markov Chain Equilibrium Distributions with Computable Error Bounds

arXiv2208.14406MaRDI QIDQ6409276FDOQ6409276

Publication date: 30 August 2022

Abstract: 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.

Has companion code repository: https://github.com/alexinfanger/truncationalgorithmsformarkovchains

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Linear programming (90C05) Applications of mathematical programming (90C90) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Continuous-time Markov processes on discrete state spaces (60J27) Probabilistic potential theory (60J45) Jump processes on discrete state spaces (60J74)

This page was built for publication: A New Truncation Algorithm for Markov Chain Equilibrium Distributions with Computable Error Bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409276)