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.
@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] 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).
and ,[2] An algorithmic and numerical approach to bound the performance of high speed networks, IEEE MASCOTS 2002. Fort Worth, USA (2002) 375-382.
, , and ,[3] Monotone matrices and monotone Markov processes. Stochastic Process. Appl. 5 (1977) 231-241. | MR | Zbl
and ,[4] 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
and ,[5] An open tool to compute stochastic bounds on steady-state distributions and rewards, IEEE Mascots 03. USA (2003).
, , and ,[6] Algorithms for an irreducible and lumpable strong stochastic bound, Numerical Solution of Markov Chains. USA (2003). | MR | Zbl
, and ,[7] Markov Processes for stochastic modeling. Chapman & Hall (1997). | MR | Zbl
,[8] Stochastic orderings for Markov processes on partially ordered spaces. Math. Oper. Res. 12 (1987) 350-367. | MR | Zbl
,[9] Stochastic delay bounds on fair queueing algorithms, in Proc. of INFOCOM'99. New York (1999) 1212-1220.
,[10] Stochastic performance bounds by state reduction. Performance Evaluation 36-37 (1999) 1-17. | Zbl
,[11] Stochastic Orders and their Applications. Academic Press, California (1994). | MR | Zbl
and ,[12] Comparison Methods for Queues and Other Stochastic Models. John Wiley & Sons, Berlin, Germany (1983). | MR | Zbl
,[13] An Introduction to Stochastic Modeling. Academic Press, Florida (1984). | MR | Zbl
and ,[14] Determination of the optimal upper bound of a Markovian generator, Technical Report 106. LGI-IMAG, Grenoble, France (1992).
, and ,[15] Near complete decomposability: bounding the error by stochastic comparison method. Adv. Appl. Probab. 29 (1997) 830-855. | MR | Zbl
,Cited by Sources: