  Given an infinitesimal perturbation of a discrete-time finite Markov chain,
we seek the states that are stable despite the perturbation, \textit{i.e.} the
states whose weights in the stationary distributions can be bounded away from
$0$ as the noise fades away. Chemists, economists, and computer scientists have
been studying irreducible perturbations built with exponential maps. Under
these assumptions, Young proved the existence of and computed the stable states
in cubic time. We fully drop these assumptions, generalize Young's technique,
and show that stability is decidable as long as $f\in O(g)$ is. Furthermore, if
the perturbation maps (and their multiplications) satisfy $f\in O(g)$ or $g\in
O(f)$, we prove the existence of and compute the stable states and the
metastable dynamics at all time scales where some states vanish. Conversely, if
the big-$O$ assumption does not hold, we build a perturbation with these maps
and no stable state. Our algorithm also runs in cubic time despite the general
assumptions and the additional work. Proving the correctness of the algorithm
relies on new or rephrased results in Markov chain theory, and on algebraic
abstractions thereof.
