Efficient computation of the bounds of continuous time imprecise Markov chains. (English) Zbl 1328.60180
Summary: When the initial distribution and transition rates for a continuous time Markov chain are not known precisely, robust methods are needed to study the evolution of the process in time to avoid judgements based on unwarranted precision. We follow the ideas successfully applied in the study of discrete time model to build a framework of imprecise Markov chains in continuous time. The imprecision in the distributions over the set of states is modelled with upper and lower expectation functionals, which equivalently represent sets of probability distributions. Uncertainty in transitions is modelled with sets of transition rates compatible with available information. The Kolmogorov’s backward equation is then generalised into the form of a generalised differential equation, with generalised derivatives and set valued maps. The upper and lower expectation functionals corresponding to imprecise distributions at given times are determined by the maximal and minimal solutions of these equations. The second part of the paper is devoted to numerical methods for approximating the boundary solutions. The methods are based on discretisation of the time interval. A uniform and adaptive grid discretisations are examined. The latter is computationally much more efficient than the former one, but is not applicable on every interval. Therefore, to achieve maximal efficiency a combination of the methods is used.
MSC:
| 60J27 | Continuous-time Markov processes on discrete state spaces |
| 65C40 | Numerical analysis or methods applied to Markov chains |
| 34A40 | Differential inequalities involving functions of a single real variable |
| 34C11 | Growth and boundedness of solutions to ordinary differential equations |
References:
| [1] | Baier, C.; Haverkort, B.; Hermanns, H.; Katoen, J. P., Model-checking algorithms for continuous-time Markov chains, IEEE Trans. Softw. Eng., 29, 7, 2003 (2003) |
| [2] | Baier, C.; Hermanns, H.; Katoen, J. P.; Haverkort, B. R., Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes, Theor. Comput. Sci., 345, 1, 2-26 (2005) · Zbl 1081.90066 |
| [3] | Beyn, W. J.; Rieger, J., Numerical fixed grid methods for differential inclusions, Computing, 81, 1, 91-106 (Oct. 2007) · Zbl 1151.65060 |
| [4] | Crossman, R. J.; Škulj, D., Imprecise Markov chains with absorption, Int. J. Approximate Reasoning, 51, 1085-1099 (2010) · Zbl 1211.60029 |
| [5] | DaCunha, J., Transition matrix and generalized matrix exponential via the Peano-Baker series, J. Difference Equ. Appl., 11, 15, 1245-1264 (2005) · Zbl 1093.39017 |
| [6] | de Cooman, G.; Hermans, F.; Quaeghebeur, E., Imprecise Markov chains and their limit behavior, Probab. Eng. Inf. Sci., 23, 4, 597-635 (2009) · Zbl 1183.60026 |
| [7] | Dontchev, A.; Lempio, F., Difference methods for differential inclusions: a survey, SIAM Rev., 34, 2, 263-294 (1992) · Zbl 0757.34018 |
| [8] | Grammel, G., Towards fully discretized differential inclusions, Set Valued Anal., 11, 1, 1-8 (2003) · Zbl 1024.34007 |
| [9] | Hartfiel, D., On the solutions to \(x^\prime(t) = a(t) x(t)\) over all \(a(t)\), where \(p \leq a(t) \leq q\), J. Math. Anal. Appl., 108, 1, 230-240 (1985) · Zbl 0579.34042 |
| [10] | Hartfiel, D. J., Markov Set-Chains (1998), Springer-Verlag: Springer-Verlag Berlin · Zbl 0904.60003 |
| [11] | Katoen, J. P.; Klink, D.; Leucker, M.; Wolf, V., Three-valued abstraction for probabilistic systems, J. Algebr. Logic Program. (JLAP), 81, 34 (2012) · Zbl 1277.68219 |
| [12] | Leela, S., Differential and Integral Inequalities Theory and Applications: Functional, Partial (1969), Abstract and Complex Differential Equations. Academic Press: Abstract and Complex Differential Equations. Academic Press New York · Zbl 0177.12403 |
| [13] | Miranda, E., A survey of the theory of coherent lower previsions, Int. J. Approximate Reasoning, 48, 2, 628-658 (2008), In Memory of Philippe Smets-2005 · Zbl 1184.68519 |
| [14] | Smirnov, G. V., Introduction to The Theory of Differential Inclusions. Introduction to The Theory of Differential Inclusions, Crm Proceedings & Lecture Notes (2002), American Mathematical Society · Zbl 0992.34001 |
| [15] | Škulj, D., Discrete time Markov chains with interval probabilities, Int. J. Approximate Reasoning, 50, 8, 1314-1329 (2009) · Zbl 1195.60100 |
| [16] | Škulj, D., A classification of invariant distributions and convergence of imprecise Markov chains, Linear Algebra Appl., 439, 9, 2542-2561 (2013) · Zbl 1287.60087 |
| [17] | Škulj, D.; Hable, R., Coefficients of ergodicity for Markov chains with uncertain parameters, Metrika, 76, 1, 107-133 (2013) · Zbl 1272.60052 |
| [18] | Walley, P., Statistical Reasoning with Imprecise Probabilities (1991), Chapman and Hall: Chapman and Hall London, New York · Zbl 0732.62004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
