Computational methods for stochastic relations and Markovian couplings
- Proc. 4th International Workshop on Tools for Solving Structured Markov Chains (SMCTools), Pisa, Italy, 19 Oct 2009. doi:10.4108/ICST.VALUETOOLS2009.7607.
- Preprint: TKK Mathematics Research Report A571, 2009, arXiv:0906.0153.
Abstract
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.
Keywords: Markovian coupling, stochastic comparison, stochastic order, stochastic relation
AMS subject classification: 60B99, 60E15, 60J25