Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-14T05:21:46.639Z Has data issue: false hasContentIssue false
  • English
  • Français

Regenerative rare events simulation via likelihood ratios

Part of: Special processes

Published online by Cambridge University Press:  14 July 2016

Søren Asmussen ,
Reuven Y. Rubinstein  and
Chia-Li Wang
Søren Asmussen*
Affiliation:
Aalborg University
Reuven Y. Rubinstein*
Affiliation:
Technion — Israel Institute of Technology
Chia-Li Wang*
Affiliation:
University of California, Berkeley
*
∗ Postal address: Institute of Electronic Systems, Aalborg University, Fr. Bajersvej 7, DK-9220 Aalborg, Denmark.
∗∗ Postal address: Faculty of Industrial Engineering and Management, Technion — Israel Institute of Technology, Haifa 32000, Israel.
∗∗∗ Postal address: Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we obtain some new theoretical and numerial results on estimation of small steady-state probabilities in regenerative queueing models by using the likelihood ratio (score function) method, which is based on a change of the probability measure. For simple GI/G/1 queues, this amounts to simulating the regenerative cycles by a suitable change of the interarrival and service time distribution, typically corresponding to a reference traffic intensity ρ0 which is < 1 but larger than the given one ρ. For the M/M/1 queue, the resulting gain of efficiency is calculated explicitly and shown to be considerable. Simulation results are presented indicating that similar conclusions hold for gradient estimates and in more general queueing models like queueing networks.

Keywords

QUEUEING THEORYQUEUEING NETWORKSREGENERATIVE QUEUEING MODELS

MSC classification

Primary: 60K25: Queueing theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 31 , Issue 3 , September 1994 , pp. 797 - 815
Copyright
Copyright © Applied Probability Trust 1994 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Research supported by the Technion V.P.R. Fund — B.R.L. Bloomfield Industrial Management R.F.

References

Asmussen, S. (1982) Conditioned limit theorems relating a random walk to its associate, with applications to risk reserve processes and the GI/G/1 queue. Adv. Appl. Prob. 14, 143–170.CrossRefGoogle Scholar
Asmussen, S. (1987) Applied Probability and Queues. Wiley, New York.Google Scholar
Asmussen, S. (1989) Risk theory in a Markovian environment. Scand. Actuarial J ., 69–100.CrossRefGoogle Scholar
Asmussen, S. and Rubinstein, R. Y. (1993) Response surface estimation and sensitivity analysis via efficient change of measure. Stoch. Models 9, 313–339.CrossRefGoogle Scholar
Bucklew, J. A. (1990) Large Deviation Techniques in Decision, Simulation, and Estimation . Wiley, New York.Google Scholar
Bucklew, J. A., Ney, P. and Sadowsky, J. S. (1990) Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Prob. 27, 44–59.CrossRefGoogle Scholar
Cottrell, M., Fort, J. C. and Malgouyres, C. (1983) Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Autom. Control. 28, 907–920.CrossRefGoogle Scholar
Frater, M. R., Lennon, T. M. and Anderson, B. D. O. (1989) Optimally efficient estimation of the statistics of rare events in queueing networks. Manuscript, Australian National University.Google Scholar
Glynn, P. W. and Iglehart, D. L. (1989) Importance sampling in stochastic simulations. Management Sci. 35, 1367–1392.CrossRefGoogle Scholar
Goyal, A., Shahabuddin, P., Heidelberger, P., Nicola, V. F. and Glynn, P. W. (1992) A unified framework for simulating Markovian models of highly dependable systems. IEEE Trans. Computers 41, 36–51.CrossRefGoogle Scholar
Parekh, S. and Walrand, J. (1988) Quick simulation of excessive backlogs in networks of queues. In Stochastic Differential Systems, Stochastic Control Theory and Applications , IMA Volume 10, ed. Fleming, W. and Lions, P. L., pp. 439–472. Springer-Verlag, New York.CrossRefGoogle Scholar
Rubinstein, R. Y. and Shapiro, A. (1993) Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization via the Score Function Method. Wiley, New York.Google Scholar
Shalmon, M. and Kaplan, M. A. (1984) A tandem network of queues with deterministic service and intermediate arrivals. Operat. Res. 32, 753–773.CrossRefGoogle Scholar
Shalmon, M. and Rubinstein, R. Y. (1990) The variance of the regenerative estimators with special references to sensitivity analysis of queueing systems with Poisson arrivals. First International Conference on Operations Research in Telecommunications, Boca Raton, Florida.Google Scholar
Siegmund, D. (1976) Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4, 673–684.CrossRefGoogle Scholar