Transforming stochastic matrices for stochastic comparison with the st-order

Tuğrul Dayar; Jean-Michel Fourneau; Nihal Pekergin

RAIRO - Operations Research - Recherche Opérationnelle (2003)

  • Volume: 37, Issue: 2, page 85-97
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Dayar, Tuğrul, Fourneau, Jean-Michel, and Pekergin, Nihal. "Transforming stochastic matrices for stochastic comparison with the st-order." RAIRO - Operations Research - Recherche Opérationnelle 37.2 (2003): 85-97. <http://eudml.org/doc/245002>.

@article{Dayar2003,
abstract = {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.},
author = {Dayar, Tuğrul, Fourneau, Jean-Michel, Pekergin, Nihal},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {Markov processes; probability distributions; stochastic ordering; st-order},
language = {eng},
number = {2},
pages = {85-97},
publisher = {EDP-Sciences},
title = {Transforming stochastic matrices for stochastic comparison with the st-order},
url = {http://eudml.org/doc/245002},
volume = {37},
year = {2003},
}

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
PB - EDP-Sciences
VL - 37
IS - 2
SP - 85
EP - 97
AB - 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.
LA - eng
KW - Markov processes; probability distributions; stochastic ordering; st-order
UR - http://eudml.org/doc/245002
ER -

References

top
  1. [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. [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. [3] J. Keilson and A. Kester, Monotone matrices and monotone Markov processes. Stochastic Process. Appl. 5 (1977) 231-241. Zbl0367.60078MR458596
  4. [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. Zbl1017.68502
  5. [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. [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). MR2066612
  7. [7] M. Kijima, Markov Processes for stochastic modeling. Chapman & Hall (1997). Zbl0866.60056MR1429618
  8. [8] W.A. Massey, Stochastic orderings for Markov processes on partially ordered spaces. Math. Oper. Res. 12 (1987) 350-367. Zbl0622.60098MR888982
  9. [9] N. Pekergin, Stochastic delay bounds on fair queueing algorithms, in Proc. of INFOCOM’99. New York (1999) 1212-1220. 
  10. [10] N. Pekergin, Stochastic performance bounds by state reduction. Performance Evaluation 36-37 (1999) 1-17. Zbl1051.68528
  11. [11] M. Shaked and J.G. Shantikumar, Stochastic Orders and their Applications. Academic Press, California (1994). Zbl0806.62009MR1278322
  12. [12] D. Stoyan, Comparison Methods for Queues and Other Stochastic Models. John Wiley & Sons, Berlin, Germany (1983). Zbl0536.60085MR754339
  13. [13] H.M. Taylor and S. Karlin, An Introduction to Stochastic Modeling. Academic Press, Florida (1984). Zbl0946.60002MR778728
  14. [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. [15] L. Truffet, Near complete decomposability: bounding the error by stochastic comparison method. Adv. Appl. Probab. 29 (1997) 830-855. Zbl0892.60101MR1462489

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.