×

Rate-tilting for fast simulation of level/phase processes. (English) Zbl 1050.65008

Efficient simulation methods for stochastic processes involving rarely occurring events is in the center of this work. The process considered is the so-called level/phase process, a Markov process in which the “level” and the “phase” are two state variables. Changes of “level” and “phase” are induced by events, which have rates that are independent of the level except at a “boundary”. If a system typically stays at lower levels, then reaching a high level \(n\) is a rare event, thus direct simulation is very inefficient.
The authors suggest to change the events rates in a level/phase process to accelerate simulation, and find the so-called hitting probability entering a rare event by simulation. This method is called “rate-tilting”. A proper construction of “rate-tilting” relates to a generalized eigenvalue problem involving the infinitesimal generator matrix \(Q\) of the process being considered. It is shown that the relative estimation error of the hitting probability resulting from the proposed simulation remains bounded as the level increases, provided that the boundary set of the state space satisfies certain conditions. They provide criteria when “rate-tilting” is advantageous. However, it may be noted that “rate-tilting” is not always increasing the efficiency of simulations.

MSC:

65C50 Other computational problems in probability (MSC2010)
60J22 Computational methods in Markov chains
65C40 Numerical analysis or methods applied to Markov chains
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asmussen, S.; Rubinstein, R., Steady state rare events simulation, (Dshalalow, J., Advances in Queueing: Theory, Methods and Open Problems (1995), CRC Press: CRC Press New York), 429-461 · Zbl 0848.60085
[2] D.A. Bini, B. Meini, Using displacement structure for solving Non-Skip-Free M/G/1 type Markov chains, in: A. Alfa, S. Chakravarthy, (Eds.), Proceedings of the 2nd International Conference on Matrix Analytic Methods, Winnepeg, Advances in Matrix Analytic Methods for Stochastic Models, 1998, pp. 13-37; D.A. Bini, B. Meini, Using displacement structure for solving Non-Skip-Free M/G/1 type Markov chains, in: A. Alfa, S. Chakravarthy, (Eds.), Proceedings of the 2nd International Conference on Matrix Analytic Methods, Winnepeg, Advances in Matrix Analytic Methods for Stochastic Models, 1998, pp. 13-37
[3] Chang, C.-S; Heidelberger, P.; Shahabuddin, P., Effective bandwidth and fast simulation of ATM intree networks, Perf. Eval., 20, 45-65 (1994)
[4] J.W. Cohen, The Single Server Queue, North-Holland Publishing Company, revised edition, 1982; J.W. Cohen, The Single Server Queue, North-Holland Publishing Company, revised edition, 1982 · Zbl 0481.60003
[5] A. Elwalid, D. Mitra, Markovian arrival and service communication systems: spectral expansions, separability and Kronecker-product forms, in: W.J. Stewart (Ed.), Proceedings of the 2nd International Workshop on the Numeric Solution of Markov Chains, Computations with Markov Chains, Kluwer Academic Publishers, 1995, pp. 507-546; A. Elwalid, D. Mitra, Markovian arrival and service communication systems: spectral expansions, separability and Kronecker-product forms, in: W.J. Stewart (Ed.), Proceedings of the 2nd International Workshop on the Numeric Solution of Markov Chains, Computations with Markov Chains, Kluwer Academic Publishers, 1995, pp. 507-546 · Zbl 0862.60089
[6] Gail, H. R.; Hantler, S. L.; Taylor, B. A., Non-skip-free M/G/1 and G/M/1 type Markov chains, Adv. Appl. Prob., 29, 733-758 (1997) · Zbl 0892.60091
[7] Glasserman, P.; Heidelberger, P.; Shahabuddin, P., Multilevel splitting for estimating rare event probabilities, Oper. Res., 47, 585-600 (1999) · Zbl 0985.65006
[8] Glynn, P. W.; Whitt, W., Logarithmic asymptotics for steady-state tail probabilities in a single server queue, J. Appl. Prob., 31A, 131-156 (1993) · Zbl 0805.60093
[9] Grassmann, W. K.; Drekic, S., An analytical solution for a tandem queue with blocking, Queueing Systems, 36, 221-235 (2000) · Zbl 0966.60090
[10] Grassmann, W. K.; Tavakoli, J., A tandem queue with a movable server: an eigenvalue approach, SIAM J. Matrix Anal. Appl., 24, 465-474 (2002) · Zbl 1018.60086
[11] Heidelberger, P., Fast simulation of rare events in queuing and reliability model, ACM Trans. Modell. Comput. Simulat., 5, 43-80 (1995) · Zbl 0843.62096
[12] Iscoe, I.; Ney, P.; Nummelin, E., Large deviations of uniformly recurrent Markov additive processes, Adv. Appl. Math., 6, 373-412 (1985) · Zbl 0602.60034
[13] Keilson, J., Markov Chain Models-Rarity and Exponentiality (1979), Springer Verlag · Zbl 0411.60068
[14] Kroese, D. P.; Nicola, V. F., Efficient simulation of a tandem Jackson network, ACM Trans. Modell. Comput. Simulat., 12, 119-141 (2002) · Zbl 1390.90231
[15] G. Latouche, V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, ASA-SIAM, 1999; G. Latouche, V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, ASA-SIAM, 1999 · Zbl 0922.60001
[16] Mitrani, I.; Chakka, R., Spectral expansion solution for a class of Markov models: application and comparison with the matrix-geometric method, Perf. Eval., 23, 241-260 (1995) · Zbl 0875.68103
[17] K. Nakagawa, On the exponential decay rate of the tail of a discrete probability distribution, in: Eleventh INFORMS Applied Prob. Conf., New York, NY, 2001. PaperFB03, online abstract at www.informs.org/Conf/AppliedProb2001/TALKS/FB03.html; K. Nakagawa, On the exponential decay rate of the tail of a discrete probability distribution, in: Eleventh INFORMS Applied Prob. Conf., New York, NY, 2001. PaperFB03, online abstract at www.informs.org/Conf/AppliedProb2001/TALKS/FB03.html
[18] Neuts, M. F., Matrix-Geometric Solutions in Stochastic Models (1981), Johns Hopkins University Press: Johns Hopkins University Press Baltimore · Zbl 0469.60002
[19] Neuts, M. F., Structured Stochastic Matrices of M/G/1 Type and their Applications (1989), Marcel Dekker: Marcel Dekker New York · Zbl 0683.60067
[20] Ney, P.; Nummelin, E., Markov additive process 1. Eigenvalue properties and limit theorems, Annals Prob., 15, 2, 561-592 (1987) · Zbl 0625.60027
[21] Parekh, S.; Walrand, J., A quick simulation method for excessive backlogs in networks of queue, IEEE Trans. Auto. Ctrl., 34, 54-66 (1989) · Zbl 0661.60110
[22] Seneta, E., Non-negative Matrices: An Introduction to Theory and Applications (1973), Wiley · Zbl 0278.15011
[23] Stewart, W. J., Introduction to the Numeric Solution of Markov Chains (1994), Princeton University Press
[24] Zhao, Y.; Grassmann, W., Queueing analysis of a jockeying model, Oper. Res., 43, 520-529 (1995) · Zbl 0839.90048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.