Sensitivity analysis for finite Markov chains in discrete time
This work addresses uncertainty modeling in Markov chains for applications in fields like operations research or decision theory, representing a non-trivial theoretical extension.
The paper tackles the problem of performing sensitivity analysis for finite Markov chains with uncertain initial and transition probabilities by using credal sets, leading to the definition of imprecise Markov chains. It shows that the time evolution can be efficiently studied using lower and upper expectations, and under unrestrictive conditions, the inferred credal set converges to a uniquely invariant set, generalizing the Perron-Frobenius Theorem.
When the initial and transition probabilities of a finite Markov chain in discrete time are not well known, we should perform a sensitivity analysis. This is done by considering as basic uncertainty models the so-called credal sets that these probabilities are known or believed to belong to, and by allowing the probabilities to vary over such sets. This leads to the definition of an imprecise Markov chain. We show that the time evolution of such a system can be studied very efficiently using so-called lower and upper expectations. We also study how the inferred credal set about the state at time n evolves as n->infinity: under quite unrestrictive conditions, it converges to a uniquely invariant credal set, regardless of the credal set given for the initial state. This leads to a non-trivial generalisation of the classical Perron-Frobenius Theorem to imprecise Markov chains.