Interval Markov chains: performance measures and sensitivity analysis.

Abstract

There is a vast literature on Markov chains where point estimates of transition and initial probabilities are used to calculate various performance measures. However, using these point estimates does not account for the associated uncertainty in estimate. If these point estimates are used, then the best outcome possible would be an approximate solution. Hence, it would be beneficial if there was a way to allow for some uncertainty in the parameters and to carry this through the calculations. One method of incorporating variation is to place bounds on the parameters and use these intervals rather than a single point estimate. By considering the intervals that contain point estimates, it is possible to control the amount of variation allowed. When these intervals are used in calculations, the results obtained are also intervals containing the true solution. Hence, allowing for an approximation of the result as well as a margin of error to be obtained. One of the objectives of this thesis is to develop and investigate different methods of calculating intervals for various performance measures (for example, mean hitting times and expected total costs) for Markov chains when intervals are given for the parameters instead of point estimates. We develop a numerical method for obtaining intervals for the performance measures for general unstructured interval Markov chains through the use of optimisation techniques. During this development, we found a connection between interval Markov chains and Markov decision processes and exploited it to obtain a form for our solution. Further, we also considered structured interval Markov chains, such as interval birth and death processes, and obtained analytic results for the classes of processes considered. Following from the idea of structured Markov chains, we considered the Markovian SIR (susceptible-infectious-recovered) epidemic model and looked to extend the concepts developed for the unstructured interval Markov chains. Two important performance measures, namely the mean final epidemic size and mean epidemic duration, were of interest to us and we were able to prove analytic results for the mean final epidemic size. For the mean epidemic duration, we modified the numerical method for general unstructured interval Markov chains to calculate bounds on this performance measure. The other objective of this thesis was to investigate if it was possible to use interval analysis as an alternative to sensitivity analysis. We explored this in the context of the SIR model, where the true value of the parameters of the model may not be known. Hence, if one were to be careful when using point estimates, one would consider using sensitivity analysis which explores the parameter space around the chosen estimates. We considered a distribution on the parameter estimates and used the methods developed in the early chapters of the thesis, to calculate intervals for performance measures. Using these intervals, we developed a method to obtain an approximate cumulative distribution function of the performance measure. This approximate cumulative distribution function was found to very closely resemble the cumulative distribution function obtained from extensive simulations.