MAM 2006: Markov Anniversary Meeting  

TITLE: Polynomials of a Stochastic Matrix and Strong Stochastic Bounds  

AUTHORS: Tugrul Dayar, Jean-Michel Fourneau, Nihal Pekergin, and Jean-Marc Vincent  

ABSTRACT: Bounding by stochastic comparison is a promising technique for performance  
evaluation since it enables the verification of performance measures efficiently. To 
improve the accuracy of this technique, preprocessing of a stochastic matrix before 
computing a strong stochastic bound is considered. Using results from linear algebra, 
it is shown that some polynomials of the stochastic matrix give more accurate bounds. 
Numerical results are presented to illustrate the ideas, and a stochastic 
interpretation is provided.   

KEY WORDS: Polynomials of a stochastic matrix, stochastic comparison, strong  
stochastic order, bounding