  In this paper we propose augmented interval Markov chains (AIMCs): a
generalisation of the familiar interval Markov chains (IMCs) where uncertain
transition probabilities are in addition allowed to depend on one another. This
new model preserves the flexibility afforded by IMCs for describing stochastic
systems where the parameters are unclear, for example due to measurement error,
but also allows us to specify transitions with probabilities known to be
identical, thereby lending further expressivity.
  The focus of this paper is reachability in AIMCs. We study the qualitative,
exact quantitative and approximate reachability problem, as well as natural
subproblems thereof, and establish several upper and lower bounds for their
complexity. We prove the exact reachability problem is at least as hard as the
famous square-root sum problem, but, encouragingly, the approximate version
lies in $\mathbf{NP}$ if the underlying graph is known, whilst the restriction
of the exact problem to a constant number of uncertain edges is in
$\mathbf{P}$. Finally, we show that uncertainty in the graph structure affects
complexity by proving $\mathbf{NP}$-completeness for the qualitative
subproblem, in contrast with an easily-obtained upper bound of $\mathbf{P}$ for
the same subproblem with known graph structure.
