Correspondence

Abstract: Order-preserving couplings are elegant tools for obtaining robust estimates of the time-dependent and stationary distributions of Markov pro-cesses 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 gen-eralizations of stochastic orders. This generalization is motivated by the ob-servation 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