[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/1351542.1351622acmconferencesArticle/Chapter ViewAbstractPublication PageswscConference Proceedingsconference-collections
research-article

Path-sampling for state-dependent importance sampling

Published: 09 December 2007 Publication History

Abstract

State-dependent importance sampling (SDIS) has proved to be particularly useful in simulation (specially in rare event analysis of stochastic systems). One approach for designing SDIS is to mimic the zero-variance change-of-measure by using a likelihood ratio that is proportional to an asymptotic approximation that may be available for the problem at hand. Using such approximation poses the problem of computing the corresponding normalizing constants at each step. In this paper, we propose the use of path-sampling, which allows to estimate such normalizing constants in terms of one dimensional integrals. We apply path-sampling to estimate the tail of the delay in a G/G/1 queue with regularly varying input. We argue that such tail estimation can be performed with good relative precision in quadratic complexity (in terms of the tail parameter) - assuming that path-sampling is combined with an appropriate change-of-measure proposed by Blanchet and Glynn (2007a).

References

[1]
Asmussen, S. (2003) Applied Probability and Queues. Springer-Verlag. New York.
[2]
Awad, H., Glynn, P., and Rubinstein, R. (2007) Importance sampling for Markov process expectations. Preprint.
[3]
Bennett, C. H. (1976). Efficient estimation of free energy differences from Monte Carlo data. J. Comput. Phys. No. 22, p. 245--268.
[4]
Blanchet, J. (2007) Efficient importance sampling for counting. Submitted.
[5]
Blanchet, J. and Glynn, P. (2007a) Efficient rare event simulation for the maximum of heavy-tailed random walks. Submitted.
[6]
Blanchet, J. and Glynn, P. (2007b) Efficient simulation of light-tailed sums: an old-folk song sung to a faster new tune. Preprint.
[7]
Blanchet, J., Glynn, P., and Liu, J. C. (2007) Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed G/G/1 queue. Submitted.
[8]
Dupuis, P., Leder, K., and Wang, H. (2006) Notes on importance sampling for random variables with regularly varying tails. Preprint.
[9]
Durrett, R. (2004) Probability: Theory and Examples. Duxbury. Belmont, California.
[10]
Embrechts, P., Klüppelberg, C., and Mikosch, T. (1997) Modelling Extremal Events for Insurance and Finance. Springer-Verlag. New York.
[11]
Gelman, A. and Meng, X. (1998). Simulating normalizing constants: From importance sampling to bridge sampling to path sampling. Statist. Sci. No. 13 p. 163--185.
[12]
Johansen, A., Del Moral, P. and Doucet, A. (2006) Sequential Monte Carlo samplers for rare events. Proceedings of the 6th International Workshop on Rare Event Simulation.
[13]
Liu, J. (2001) Monte Carlo Strategies in Scientific Computing. Springer-Verlag, New York.
[14]
Ogata, Y. (1989). A Monte Carlo method for high dimensional integration. Numer. Math. No. 55, p. 137--157.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
WSC '07: Proceedings of the 39th conference on Winter simulation: 40 years! The best is yet to come
December 2007
2659 pages
ISBN:1424413060

Sponsors

  • IIE: Institute of Industrial Engineers
  • INFORMS-SIM: Institute for Operations Research and the Management Sciences: Simulation Society
  • ASA: American Statistical Association
  • IEEE/SMC: Institute of Electrical and Electronics Engineers: Systems, Man, and Cybernetics Society
  • SIGSIM: ACM Special Interest Group on Simulation and Modeling
  • NIST: National Institute of Standards and Technology
  • (SCS): The Society for Modeling and Simulation International

Publisher

IEEE Press

Publication History

Published: 09 December 2007

Check for updates

Qualifiers

  • Research-article

Conference

WSC07
Sponsor:
  • IIE
  • INFORMS-SIM
  • ASA
  • IEEE/SMC
  • SIGSIM
  • NIST
  • (SCS)
WSC07: Winter Simulation Conference
December 9 - 12, 2007
Washington D.C.

Acceptance Rates

WSC '07 Paper Acceptance Rate 152 of 244 submissions, 62%;
Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 92
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media