Interval Markov chains: Performance
               measures and sensitivity analysis
                          Mingmei Teo
                     Thesis submitted for the degree of
                        Master of Philosophy
                              in
                        Applied Mathematics
                              at
                      The University of Adelaide
                     School of Mathematical Sciences
                          December 2013
                         Contents
                         Abstract                                                                              vii
                         Signed Statement                                                                       ix
                         Acknowledgements                                                                       xi
                         1 Introduction                                                                          1
                         2 Background                                                                            5
                            2.1   Markov chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      5
                                  2.1.1   Discrete-time Markov chains . . . . . . . . . . . . . . . . . .        6
                                  2.1.2   Continuous-time Markov chains . . . . . . . . . . . . . . . .         12
                            2.2   Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   20
                            2.3   Incorporating intervals into Markov chains . . . . . . . . . . . . . .        25
                            2.4   Literature review . . . . . . . . . . . . . . . . . . . . . . . . . . . .     28
                            2.5   Markov decision processes . . . . . . . . . . . . . . . . . . . . . . .       31
                                  2.5.1   Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . .     31
                            2.6   Optimisation essentials . . . . . . . . . . . . . . . . . . . . . . . . .     33
                         3 Markov chains: Analytic investigation                                               39
                            3.1   Description of problem . . . . . . . . . . . . . . . . . . . . . . . . .      40
                            3.2   Possible methods to obtain interval expected total costs . . . . . . .        42
                                  3.2.1   Optimisation problems . . . . . . . . . . . . . . . . . . . . .       46
                                                                    iii
                    3.3   Simplification of the optimisation problems . . . . . . . . . . . . . .       53
                          3.3.1   Minimisation problem . . . . . . . . . . . . . . . . . . . . .       55
                          3.3.2   Maximisation problem . . . . . . . . . . . . . . . . . . . . .       58
                    3.4   Development of an analytic solution for the mean hitting times . . .         62
                          3.4.1   Analyticsolutiontoathreestatediscrete-timeintervalMarkov
                                  chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  63
                          3.4.2   Counterexampleforafourstatediscrete-timeintervalMarkov
                                  chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  71
                    3.5   Markov decision processes . . . . . . . . . . . . . . . . . . . . . . .      75
                          3.5.1   Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    76
                    3.6   Continuous-time interval Markov chains        . . . . . . . . . . . . . . .  81
                          3.6.1   Uniformisation for continuous-time interval Markov chains .          83
                          3.6.2   Transformingdiscrete-timeexpectedtotalcoststocontinuous-
                                  time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   85
                4 Numerical Method                                                                     89
                    4.1   Pre-processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   90
                          4.1.1   Degeneracy . . . . . . . . . . . . . . . . . . . . . . . . . . .     91
                          4.1.2   Outward rounding . . . . . . . . . . . . . . . . . . . . . . .       94
                          4.1.3   Coherence . . . . . . . . . . . . . . . . . . . . . . . . . . . .    98
                          4.1.4   Pre-processing method . . . . . . . . . . . . . . . . . . . . .      99
                    4.2   Separation of minimisation and maximisation problems . . . . . . . 100
                    4.3   MATLABfmincon formulation . . . . . . . . . . . . . . . . . . . . 101
                          4.3.1   Choice of optimisation algorithm      . . . . . . . . . . . . . . . 101
                          4.3.2   Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
                          4.3.3   Hessian   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
                          4.3.4   Initial point . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
                          4.3.5   Removal of degenerate intervals from the problem . . . . . . 110
                    4.4   Tolerances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111