  This paper generalizes the notion of stochastic order to a relation between
probability measures over arbitrary measurable spaces. This generalization is
motivated by the observation that for the stochastic ordering of two stationary
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: a functional
characterization of stochastic relations, necessary and sufficient conditions
for the preservation of stochastic relations, and an algorithm for finding
subrelations preserved by probability kernels. The theory is illustrated with
applications to hidden Markov processes, population processes, and queueing
systems.
