  We propose polynomial-time algorithms to minimise labelled Markov chains
whose transition probabilities are not known exactly, have been perturbed, or
can only be obtained by sampling. Our algorithms are based on a new notion of
an approximate bisimulation quotient, obtained by lumping together states that
are exactly bisimilar in a slightly perturbed system. We present experiments
that show that our algorithms are able to recover the structure of the
bisimulation quotient of the unperturbed system.
