Efficient computation of the bounds of continuous time imprecise Markov chains

• Published in: Applied mathematics and computation 2015-01, Vol.250, p.165-180
• Main Author: Skulj, Damjan
• Format: Article
• Language: English
• Subjects: Computational efficiency; Construction; Derivatives; Differential equations; Differential inequalities; Discretisation; Functionals; Intervals; Markov chains; Markov processes; Mathematical analysis; Mathematical models; Uncertainty modelling
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2014.10.092

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.