Transforming stochastic matrices for stochastic comparison with the st-order
RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 2, pp. 85-97.

We present a transformation for stochastic matrices and analyze the effects of using it in stochastic comparison with the strong stochastic (st) order. We show that unless the given stochastic matrix is row diagonally dominant, the transformed matrix provides better st bounds on the steady state probability distribution.

DOI: 10.1051/ro:2003015
Keywords: Markov processes, probability distributions, stochastic ordering, st-order
@article{RO_2003__37_2_85_0,
     author = {Dayar, Tu\u{g}rul and Fourneau, Jean-Michel and Pekergin, Nihal},
     title = {Transforming stochastic matrices for stochastic comparison with the st-order},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {85--97},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {2},
     year = {2003},
     doi = {10.1051/ro:2003015},
     mrnumber = {2010414},
     zbl = {1036.60063},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2003015/}
}
TY  - JOUR
AU  - Dayar, Tuğrul
AU  - Fourneau, Jean-Michel
AU  - Pekergin, Nihal
TI  - Transforming stochastic matrices for stochastic comparison with the st-order
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2003
SP  - 85
EP  - 97
VL  - 37
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2003015/
DO  - 10.1051/ro:2003015
LA  - en
ID  - RO_2003__37_2_85_0
ER  - 
%0 Journal Article
%A Dayar, Tuğrul
%A Fourneau, Jean-Michel
%A Pekergin, Nihal
%T Transforming stochastic matrices for stochastic comparison with the st-order
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2003
%P 85-97
%V 37
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2003015/
%R 10.1051/ro:2003015
%G en
%F RO_2003__37_2_85_0
Dayar, Tuğrul; Fourneau, Jean-Michel; Pekergin, Nihal. Transforming stochastic matrices for stochastic comparison with the st-order. RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 2, pp. 85-97. doi : 10.1051/ro:2003015. http://archive.numdam.org/articles/10.1051/ro:2003015/

[1] O. Abu-Amsha and J.-M. Vincent, An algorithm to bound functionals of Markov chains with large state space, in 4th INFORMS Conference on Telecommunications. Boca Raton, Florida (1998). Available as Rapport de recherche MAI No. 25. IMAG, Grenoble, France (1996).

[2] M. Benmammoun, J.M. Fourneau, N. Pekergin and A. Troubnikoff, An algorithmic and numerical approach to bound the performance of high speed networks, IEEE MASCOTS 2002. Fort Worth, USA (2002) 375-382.

[3] J. Keilson and A. Kester, Monotone matrices and monotone Markov processes. Stochastic Process. Appl. 5 (1977) 231-241. | MR | Zbl

[4] J.M. Fourneau and N. Pekergin, An algorithmic approach to stochastic bounds, Performance evaluation of complex systems: Techniques and Tools. Springer, Lecture Notes in Comput. Sci. 2459 (2002) 64-88. | Zbl

[5] J.M. Fourneau, M. Le Coz, N. Pekergin and F. Quessette, An open tool to compute stochastic bounds on steady-state distributions and rewards, IEEE Mascots 03. USA (2003).

[6] J.M. Fourneau, M. Le Coz and F. Quessette, Algorithms for an irreducible and lumpable strong stochastic bound, Numerical Solution of Markov Chains. USA (2003). | MR | Zbl

[7] M. Kijima, Markov Processes for stochastic modeling. Chapman & Hall (1997). | MR | Zbl

[8] W.A. Massey, Stochastic orderings for Markov processes on partially ordered spaces. Math. Oper. Res. 12 (1987) 350-367. | MR | Zbl

[9] N. Pekergin, Stochastic delay bounds on fair queueing algorithms, in Proc. of INFOCOM'99. New York (1999) 1212-1220.

[10] N. Pekergin, Stochastic performance bounds by state reduction. Performance Evaluation 36-37 (1999) 1-17. | Zbl

[11] M. Shaked and J.G. Shantikumar, Stochastic Orders and their Applications. Academic Press, California (1994). | MR | Zbl

[12] D. Stoyan, Comparison Methods for Queues and Other Stochastic Models. John Wiley & Sons, Berlin, Germany (1983). | MR | Zbl

[13] H.M. Taylor and S. Karlin, An Introduction to Stochastic Modeling. Academic Press, Florida (1984). | MR | Zbl

[14] M. Tremolieres, J.-M. Vincent and B. Plateau, Determination of the optimal upper bound of a Markovian generator, Technical Report 106. LGI-IMAG, Grenoble, France (1992).

[15] L. Truffet, Near complete decomposability: bounding the error by stochastic comparison method. Adv. Appl. Probab. 29 (1997) 830-855. | MR | Zbl

Cited by Sources: