tailieunhanh - Rare-event Simulation Techniques: An Introduction and Recent Advances

The web in recent years has experienced an explosion in the number of devices users employ to access services. A single user may access a certain service using multiple devices. Most services allow clients to access the service through a broker. The client is then forced to interact with the service via this broker throughout the duration that it is using the service. If the broker fails, the client is denied servicing till such time that the failed broker recovers. In the event that this service is running on a fixed set of brokers the client, since it knows about this set of brokers, could then. | Rare-event Simulation Techniques An Introduction and Recent Advances S. Juneja Tata Institute of Fundamental Research India juneja@ P. Shahabuddin Columbia University perwez@ Abstract In this chapter we review some of the recent developments for efficient estimation of rare-events most of which involve application of importance sampling techniques to achieve variance reduction. The zero-variance importance sampling measure is well known and in many cases has a simple representation. Though not implementable it proves useful in selecting good and implementable importance sampling changes of measure that are in some sense close to it and thus provides a unifying framework for such selections. Specifically we consider rare events associated with 1 multi-dimensional light-tailed random walks 2 with certain events involving heavy-tailed random variables and 3 queues and queueing networks. In addition we review the recent literature on development of adaptive importance sampling techniques to quickly estimate common performance measures associated with finite-state Markov chains. We also discuss the application of rare-event simulation techniques to problems in financial engineering. The discussion in this chapter is non-measure theoretic and kept sufficiently simple so that the key ideas are accessible to beginners. References are provided for more advanced treatments. Keywords Importance sampling rare-event simulation Markov processes adaptive importance sampling random walks queueing systems heavy-tailed distributions value-at-risk credit risk insurance risk. 1 Introduction Rare-event simulation involves estimating extremely small but important probabilities. Such probabilities are of importance in various applications In modern packet-switched telecommunications networks in-order to reduce delay variation in carrying real-time video traffic the buffers within the switches are of limited size. This creates the possibility of packet loss if