Under Interval and Fuzzy Uncertainty, Symmetric Markov Chains Are More Difficult to Predict

Abstract

Markov chains are an important tool for solving practical problems. In particular, Markov chains have been successfully applied in bioinformatics. Traditional statistical tools for processing Markov chains assume that we know the exact probabilities pij of a transition from the state i to the state j. In reality, we often only know these transition probabilities with interval (or fuzzy) uncertainty. We start the paper with a brief reminder of how the Markov chain formulas can be extended to the cases of such interval and fuzzy uncertainty. In some practical situations, there is another restriction on the Markov chainthat this Markov chain is symmetric in the sense that for every two states i and j, the probability of transitioning from i to j is the same as the probability of transitioning from j to i: pij = pji. In general, symmetry assumptions simplify computations. In this paper, we show that for Markov chains under interval and fuzzy uncertainty, symmetry has the opposite effect: it makes the computational problems more difficult.