Perfect simulation and monotone stochastic bounds

ABSTRACT

We combine monotone bounds of Markov chains and the coupling from the past to obtain an exact sampling of a strong stochastic bound of the steady-state distribution for a Markov chain. Stochastic bounds are sufficient to bound any positive increasing rewards on the steady-state such as the loss rates and the average size or delay. We show the equivalence between st-monotonicity and event monotonicity when the state space is endowed with a total ordering and we provide several algorithms to transform a system into a set of monotone events. As we deal with monotone systems, the coupling technique requires less computational efforts for each iteration. Numerical examples show that we can obtain very important speedups.

REFERENCES

• 1: O. Abu Amsha and J.-M. Vincent. An algorithm to bound functionals of markov chains with large state space. In INFORMS, Boca Raton, 1998.
• 2: A. Borovkov and S. Foss. Two ergodicity criteria for stochastically recursive sequences. Acta Appl. Math., 34, 1994.
• 3: P. Brémaud. Markov Chains: Gibbs fields, Monte Carlo Simulation and Queues. Springer-Verlag, 1999.
• 4: A. Busic and J.-M. Fourneau. Bounds for point and steady-state availability: An algorithmic approach based on lumpability and stochastic ordering. In M. Bravetti, L. Kloul, and G. Zavattaro, editors, Formal Techniques for Computer Systems and Business Processes, European Performance Engineering Workshop, EPEW 2005 and International Workshop on Web Services and Formal Methods, WS-FM 2005, Versailles, France, September 1-3, 2005, Proceedings, volume 3670 of Lecture Notes in Computer Science, pages 94--108. Springer, 2005.
• 5: A. Busic , J. M. Fourneau, A Matrix Pattern Compliant Strong Stochastic Bound, Proceedings of the 2005 Symposium on Applications and the Internet Workshops, p.256-259, January 31-February 04, 2005
• 6: T. Dayar, J.-M. Fourneau, N. Pekergin, and J.-M. Vincent. Polynomials of a stochastic matrix and strong stochastic bounds. In Markov Anniversary Meeting, pages 211--228, Charleston, 2006. Celebration of the 100th anniversary of Markov.
• 7: Persi Diaconis , David Freedman, Iterated Random Functions, SIAM Review, v.41 n.1, p.45-76, March 1999 [doi>10.1137/S0036144598338446]
• 8: J. Dopper, B. Gaujal, and J.-M. Vincent. Bounds for the coupling time in queueing networks perfect simulation. In Numerical Solutions for Markov Chain (NSMC06), pages 117--136, Charleston, 2006. Celebration of the 100th anniversary of Markov.
• 9: Jean-Michel Fourneau , Nihal Pekergin, An Algorithmic Approach to Stochastic Bounds, Performance Evaluation of Complex Systems: Techniques and Tools, Performance 2002, Tutorial Lectures, p.64-88, January 2002
• 10: J.-M. Fourneau, M. L. Coz, F. QuessettD., J. Fourneau, and D. Nott. Algorithms for an irreducible and lumpable strong stochastic bound. Special Issue on the Conference on the Numerical Solution of Markov Chains 2003, Linear Algebra and its Applications, 386:167--185, 2004.
• 11: Paul Glasserman , David D. Yao, Monotone structure in discrete-event systems, John Wiley & Sons, Inc., New York, NY, 1994
• 12: S. Haddad and P. Moreaux. Sub-stochastic matrix analysis for bounds computation: Theoretical results. European Journal of Operational Research, In Press.
• 13: J. Ledoux and L. Truffet. Markovian bounds on functions of finite Markov chains. Advances in Applied Probability, 33(2):505--519, 2001.
• 14: A. Muller and D. Stoyan. Comparison Methods for Stochastic Models and Risks. 2002. Wiley, New York.
• 15: N. Pekergin. Stochastic bounds on delays of fair queueing algorithms. In Proceedings of INFOCOM'99, pages 1212--1219, New York, NY, 1999.
• 16: James Gary Propp , David Bruce Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures & Algorithms, v.9 n.1-2, p.223-252, Aug./Sept. 1996
• 17: F. Quessette. Couplage depuis le passé, Feb. 2003. ROADEF'2003, Avignon.
• 18: O. Stenflo. Ergodic theorems fory Iterated Function Systems controlled by stochastic sequences. Doctoral thesis n. 14, Umea university, 1998.
• 19: O. Stenflo. Ergodic theorems for markov chains represented by iterated function systems. Bull. Polish Acad. Sci. Math, 2001.
• 20: J.-M. Vincent and C. Marchand. On the exact simulation of functionals of stationary markov chains. Linear Algebra and its Applications, 386:285--310, 2004.
• 21: J.-M. Vincent and J. Vienne. Perfect simulation of monotone systems with variance reduction. In Proceedings of the 6th Int. Workshop on Rare Event Simulation, pages 275--285, Bamberg, Oct. 2006.

INDEX TERMS

Keywords:
coupling from the past, monotone Markov chains, perfect simulation, stochastic bounds