  Order-preserving couplings are elegant tools for obtaining robust estimates
of the time-dependent and stationary distributions of Markov processes that are
too complex to be analyzed exactly. The starting point of this paper is to
study stochastic relations, which may be viewed as natural generalizations of
stochastic orders. This generalization is motivated by the observation that for
the stochastic ordering of two Markov processes, it suffices that the
generators of the processes preserve some, not necessarily reflexive or
transitive, subrelation of the order relation. The main contributions of the
paper are an algorithmic characterization of stochastic relations between
finite spaces, and a truncation approach for comparing infinite-state Markov
processes. The methods are illustrated with applications to loss networks and
parallel queues.
