Analysis of Markov jump processes under terminal constraints

Abstract

Many probabilistic inference problems such as stochastic filtering or the computation of rare event probabilities require model analysis under initial and terminal constraints. We propose a solution to this bridging problem for the widely used class of population-structured Markov jump processes. The method is based on a state-space lumping scheme that aggregates states in a grid structure. The resulting approximate bridging distribution is used to iteratively refine relevant and truncate irrelevant parts of the state-space. This way, the algorithm learns a well-justified finite-state projection yielding guaranteed lower bounds for the system behavior under endpoint constraints. We demonstrate the method’s applicability to a wide range of problems such as Bayesian inference and the analysis of rare events.

Publication
Tools and Algorithms for the Construction and Analysis of Systems. International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS-2021), 27th International Conference, TACAS 2021, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2021, March 27 - April 1, Luxembourg City, Luxembourg

Cite

@inproceedings{backenkohlerAnalysisOfMarkovJump2021,
 author = {Michael Backenköhler and Luca Bortolussi and Gerrit Großmann and Verena Wolf},
 booktitle = {Tools and Algorithms for the Construction and Analysis of Systems. International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS-2021), 27th International Conference, TACAS 2021, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2021, March 27 - April 1, Luxembourg City, Luxembourg},
 doi = {10.1007/978-3-030-72016-2_12},
 edition = {1st},
 editor = {Jan Friso Groote and Kim Guldstrand Larsen and },
 isbn = {978-3-030-72016-2},
 month = {3},
 pages = {210-229},
 publisher = {Springer, Switzerland},
 title = {Analysis of Markov jump processes under terminal constraints},
 volume = {12651},
 year = {2021}
}