Imprecise continuous-time Markov chains. (English) Zbl 1427.60164
Summary: Continuous-time Markov chains are mathematical models that are used to describe the state-evolution of dynamical systems under stochastic uncertainty, and have found widespread applications in various fields. In order to make these models computationally tractable, they rely on a number of assumptions that – as is well known – may not be realistic for the domain of application; in particular, the ability to provide exact numerical parameter assessments, and the applicability of time-homogeneity and the eponymous Markov property. In this work, we extend these models to imprecise continuous-time Markov chains (ICTMC’s), which are a robust generalisation that relaxes these assumptions while remaining computationally tractable.
More technically, an ICTMC is a set of “precise” continuous-time finite-state stochastic processes, and rather than computing expected values of functions, we seek to compute lower expectations, which are tight lower bounds on the expectations that correspond to such a set of “precise” models. Note that, in contrast to e.g. Bayesian methods, all the elements of such a set are treated on equal grounds; we do not consider a distribution over this set. Together with the conjugate notion of upper expectation, the bounds that we provide can then be intuitively interpreted as providing best- and worst-case scenarios with respect to all the models in our set of stochastic processes.
The first part of this paper develops a formalism for describing continuous-time finite-state stochastic processes that does not require the aforementioned simplifying assumptions. Next, this formalism is used to characterise ICTMC’s and to investigate their properties. The concept of lower expectation is then given an alternative operator-theoretic characterisation, by means of a lower transition operator, and the properties of this operator are investigated as well. Finally, we use this lower transition operator to derive tractable algorithms (with polynomial runtime complexity w.r.t. the maximum numerical error) for computing the lower expectation of functions that depend on the state at any finite number of time points.
More technically, an ICTMC is a set of “precise” continuous-time finite-state stochastic processes, and rather than computing expected values of functions, we seek to compute lower expectations, which are tight lower bounds on the expectations that correspond to such a set of “precise” models. Note that, in contrast to e.g. Bayesian methods, all the elements of such a set are treated on equal grounds; we do not consider a distribution over this set. Together with the conjugate notion of upper expectation, the bounds that we provide can then be intuitively interpreted as providing best- and worst-case scenarios with respect to all the models in our set of stochastic processes.
The first part of this paper develops a formalism for describing continuous-time finite-state stochastic processes that does not require the aforementioned simplifying assumptions. Next, this formalism is used to characterise ICTMC’s and to investigate their properties. The concept of lower expectation is then given an alternative operator-theoretic characterisation, by means of a lower transition operator, and the properties of this operator are investigated as well. Finally, we use this lower transition operator to derive tractable algorithms (with polynomial runtime complexity w.r.t. the maximum numerical error) for computing the lower expectation of functions that depend on the state at any finite number of time points.
MSC:
| 60J27 | Continuous-time Markov processes on discrete state spaces |
Keywords:
continuous-time Markov chain; imprecise probability; model uncertainty; lower and upper expectation; lower transition operatorReferences:
| [1] | Asmussen, S., Applied Probability and Queues (2008), Springer Science & Business Media |
| [2] | Bolch, G.; Greiner, S.; de Meer, H.; Trivedi, K. S., Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2006), John Wiley & Sons · Zbl 1099.60002 |
| [3] | Elliott, R. J.; van der Hoek, J., Default times in a continuous time Markov chain economy, Appl. Math. Finance, 20, 5, 450-460 (2013) · Zbl 1396.91821 |
| [4] | Rolski, T.; Schmidli, H.; Schmidt, V.; Teugels, J., Stochastic Processes for Insurance and Finance (2009), John Wiley & Sons |
| [5] | Sass, J.; Haussmann, U. G., Optimizing the terminal wealth under partial information: the drift process as a continuous time Markov chain, Finance Stoch., 8, 4, 553-577 (2004) · Zbl 1063.91040 |
| [6] | Duffy, S. W.; Chen, H.-H.; Tabar, L.; Day, N. E., Estimation of mean sojourn time in breast cancer screening using a Markov chain model of both entry to and exit from the preclinical detectable phase, Stat. Med., 14, 14, 1531-1543 (1995) |
| [7] | Jackson, C. H.; Sharples, L. D.; Thompson, S. G.; Duffy, S. W.; Couto, E., Multistate Markov models for disease progression with classification error, J. R. Stat. Soc., Ser. D, Stat., 52, 2, 193-209 (2003) |
| [8] | Lemey, P.; Suchard, M.; Rambaut, A., Reconstructing the initial global spread of a human influenza pandemic: a Bayesian spatial-temporal model for the global spread of H1N1pdm, PLoS Curr. Influenza (2009) |
| [9] | Besnard, F.; Bertling, L., An approach for condition-based maintenance optimization applied to wind turbine blades, IEEE Trans. Sustain. Energy, 1, 2, 77-83 (2010) |
| [10] | Gokhale, S. S.; Lyu, M. R.; Trivedi, K. S., Analysis of software fault removal policies using a non-homogeneous continuous time Markov chain, Softw. Qual. J., 12, 3, 211-230 (2004) |
| [11] | Wang, D.; Trivedi, K. S., Reliability analysis of phased-mission system with independent component repairs, IEEE Trans. Reliab., 56, 3, 540-551 (2007) |
| [12] | Yin, G.; Zhang, Q., Continuous-Time Markov Chains and Applications: A Two-Time-Scale Approach (2012), Springer Science & Business Media |
| [13] | Škulj, D., Efficient computation of the bounds of continuous time imprecise Markov chains, Appl. Math. Comput., 250, C, 165-180 (2015) · Zbl 1328.60180 |
| [14] | Troffaes, M. C.M.; Gledhill, J.; Škulj, D.; Blake, S., Using imprecise continuous time Markov chains for assessing the reliability of power networks with common cause failure and non-immediate repair, (ISIPTA ’15: Proceedings of the Ninth International Symposium on Imprecise Probability: Theories and Applications (2015)), 287-294 |
| [15] | Rindos, A.; Woolet, S.; Viniotis, I.; Trivedi, K., Exact methods for the transient analysis of nonhomogeneous continuous time Markov chains, (Computations with Markov Chains (1995), Springer), 121-133 · Zbl 0862.60060 |
| [16] | Aalen, O. O.; Johansen, S., An empirical transition matrix for non-homogeneous Markov chains based on censored observations, Scand. J. Stat., 5, 3, 141-150 (1978) · Zbl 0383.62058 |
| [17] | Johnson, J. T.; Luecke, G. R., Nonhomogeneous, continuous-time Markov chains defined by series of proportional intensity matrices, Stoch. Process. Appl., 32, 1, 171-181 (1989) · Zbl 0676.60065 |
| [18] | Harlamov, B., Continuous Semi-Markov Processes (2008), John Wiley & Sons: John Wiley & Sons New York · Zbl 1156.60004 |
| [19] | Insua, D.; Ruggeri, F.; Wiper, M., Bayesian Analysis of Stochastic Process Models (2012), John Wiley & Sons · Zbl 1273.62021 |
| [20] | Guo, X.; Hernández-Lerma, O., Continuous-Time Markov Decision Processes: Theory and Applications, Stochastic Modelling and Applied Probability, vol. 62 (2009), Springer: Springer Berlin · Zbl 1209.90002 |
| [21] | Guo, X.; Hernández-Lerma, O., Continuous-time controlled Markov chains, Ann. Appl. Probab., 13, 1, 363-388 (2003) · Zbl 1049.60067 |
| [22] | Walley, P., Statistical Reasoning with Imprecise Probabilities (1991), Chapman and Hall: Chapman and Hall London · Zbl 0732.62004 |
| [23] | Troffaes, M. C.M.; de Cooman, G., Lower Previsions (2014), Wiley · Zbl 1305.60007 |
| [24] | (Augustin, T.; Coolen, F. P.A.; de Cooman, G.; Troffaes, M. C.M., Introduction to Imprecise Probabilities (2014), John Wiley & Sons) · Zbl 1290.62003 |
| [25] | Rottondi, C.; Erreygers, A.; Verticale, G.; De Bock, J., Modelling spectrum assignment in a two-service flexi-grid optical link with imprecise continuous-time Markov chains, (Proceedings of DRCN 2017 (2017)), 39-46 |
| [26] | Krak, T.; De Bock, J.; Siebes, A., Imprecise continuous-time Markov chains, Extended ArXiv tech-report · Zbl 1427.60164 |
| [27] | De Bock, J., The limit behaviour of continuous-time imprecise Markov chains, J. Nonlinear Sci., 27, 1, 159-196 (2017) · Zbl 1373.60131 |
| [28] | Norris, J. R., Markov Chains (1998), Cambridge University Press · Zbl 0873.60043 |
| [29] | Van Loan, C. F., A Study of the Matrix Exponential (August 1975), University of Manchester: University of Manchester Manchester, UK, Reissued as MIMS EPrint 2006.397, Manchester Institute for Mathematical Sciences, The University of Manchester, UK |
| [30] | Dubins, L. E., Finitely additive conditional probabilities, conglomerability and disintegrations, Ann. Probab., 3, 1, 89-99 (1975) · Zbl 0302.60002 |
| [31] | Berti, P.; Regazzini, E.; Rigo, P., Coherent statistical inference and Bayes theorem, Ann. Stat., 19, 1, 366-381 (1991) · Zbl 0742.62003 |
| [32] | De Finetti, B., Theory of Probability (1974), John Wiley & Sons: John Wiley & Sons New York · Zbl 0328.60002 |
| [33] | Regazzini, E., Finitely additive conditional probabilities, Rend. Semin. Mat. Fis. Milano, 55, 1, 69-89 (1985) · Zbl 0631.60001 |
| [34] | Williams, P. M., Notes on Conditional Previsions (1975), School of Mathematical and Physical Science, University of Sussex, Tech. rep. · Zbl 1114.60005 |
| [35] | Williams, P. M., Notes on conditional previsions, Int. J. Approx. Reason., 44, 3, 366-383 (2007) · Zbl 1114.60005 |
| [36] | Berti, P.; Rigo, P., On coherent conditional probabilities and disintegrations, Ann. Math. Artif. Intell., 35, 1-4, 71-82 (2002) · Zbl 1005.60008 |
| [37] | Vicig, P.; Zaffalon, M.; Cozman, F. G., Notes on “Notes on conditional previsions”, Int. J. Approx. Reason., 44, 3, 358-365 (2007) · Zbl 1114.60004 |
| [38] | Rogers, L. C.G.; Williams, D., Diffusions, Markov Processes, and Martingales. Volume 1. Foundations, Cambridge Mathematical Library (2000), Cambridge University Press · Zbl 0949.60003 |
| [39] | Liggett, T. M., Continuous Time Markov Processes: An Introduction (2010), American Mathematical Society · Zbl 1205.60002 |
| [40] | Goldsztejn, A.; Neumaier, A., On the exponentiation of interval matrices, Reliab. Comput., 20, 52-72 (2014) |
| [41] | Oppenheimer, E. P.; Michel, A. N., Application of interval analysis techniques to linear systems. II. The interval matrix exponential function, IEEE Trans. Circuits Syst., 35, 10, 1230-1242 (1988) |
| [42] | Huber, P. J., Robust Statistics (1981), John Wiley & Sons: John Wiley & Sons New York · Zbl 0536.62025 |
| [43] | da Rocha, J. C.F.; Cozman, F. G., Inference with Separately Specified Sets of Probabilities in Credal Networks (2002), Morgan Kaufmann Publishers Inc. · Zbl 1031.68596 |
| [44] | Cozman, F. G., Credal networks, Artif. Intell., 120, 2, 199-233 (2000) · Zbl 0945.68163 |
| [45] | De Bock, J., Credal Networks Under Epistemic Irrelevance: Theory and Algorithms (2015), Ghent University, Ph.D. thesis |
| [46] | de Cooman, G.; Hermans, F.; Antonucci, A.; Zaffalon, M., Epistemic irrelevance in credal nets: the case of imprecise Markov trees, Int. J. Approx. Reason., 51, 9, 1029-1052 (2010) · Zbl 1348.68248 |
| [47] | Antonucci, A.; de Campos, C. P.; Zaffalon, M., Probabilistic graphical models, (Augustin, T.; Coolen, F. P.A.; de Cooman, G.; Troffaes, M. C.M., Introduction to Imprecise Probabilities (2014), John Wiley & Sons: John Wiley & Sons Chichester), 207-229 · Zbl 1298.68262 |
| [48] | Krak, T.; De Bock, J.; Siebes, A., Efficient computation of updated lower expectations for imprecise continuous-time hidden Markov chains, (ISIPTA ’17: Proceedings of the Tenth International Symposium on Imprecise Probability: Theory and Applications. ISIPTA ’17: Proceedings of the Tenth International Symposium on Imprecise Probability: Theory and Applications, PMLR: Proceedings of Machine Learning Research, vol. 62 (2017), SIPTA), 193-204 |
| [49] | Lopatatzidis, S.; De Bock, J.; de Cooman, G.; Vuyst, S.; Walraevens, J., Robust queueing theory: an initial study using imprecise probabilities, Queueing Syst., 82, 1, 75-101 (2015) · Zbl 1334.60199 |
| [50] | Benavoli, A.; Zaffalon, M.; Miranda, E., Robust filtering through coherent lower previsions, IEEE Trans. Autom. Control, 56, 7, 1567-1581 (2011) · Zbl 1368.93704 |
| [51] | De Bock, J.; de Cooman, G., An efficient algorithm for estimating state sequences in imprecise hidden Markov models, J. Artif. Intell. Res., 50, 189-233 (2014) · Zbl 1361.68256 |
| [52] | Royden, H. L.; Fitzpatrick, P. M., Real Analysis (2010), Prentice Hall · Zbl 1191.26002 |
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.
