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