Computing 2-Step Predictions for Interval-Valued Finite Stationary Markov Chains

Abstract

Markov chains are a useful tool for solving practical problems. In many real-life situations, we do not know the exact values of initial and transition probabilities; instead, we only know the intervals of possible values of these probabilities. Such interval-valued Markov chains were considered and analyzed by I. O. Kozine and L. V. Utkin in their Reliable Computing paper. In their paper, they propose an efficient algorithm for computing interval-valued probabilities of the future states. For the general case of non-stationary Markov chains, their algorithm leads to the exact intervals for the probabilities of future states.\nIn the important case of stationary Markov chains, we can still apply their algorithm. For stationary chains, 1-step predictions are exact but 2-step predictions sometimes lead to intervals that are wider than desired. In this paper, we describe a modification of Kozine-Utkin algorithm that always produces exact 2-step predictions for stationary Markov chains.