Uniformly efficient importance sampling for the tail distribution of sums of random variables

• 成果类型: Article
• 署名作者: Glasserman, Paul; Juneja, Sandeep
• 署名单位: Columbia University; Tata Institute of Fundamental Research (TIFR)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1070.0276
• 发表日期: 2008
• 页码: 36-50
• 关键词: large deviations theory; monte-carlo; simulation

摘要

Successful efficient rare-event simulation typically involves using importance sampling tailored to a specific rare event. However, in applications one may be interested in simultaneous estimation of many probabilities or even an entire distribution. In this paper, we address this issue in a simple but fundamental setting. Specifically, we consider the problem of efficient estimation of the probabilities P(S-n >= na) for large n, for all a lying in an interval A, where S-n denotes the sum of n independent, identically distributed light-tailed random variables. Importance sampling based on exponential twisting is known to produce asymptotically efficient estimates when A reduces to a single point. We show, however, that this procedure fails to be asymptotically efficient throughout A when A contains more than one point. We analyze the best performance that can be achieved using a discrete mixture of exponentially twisted distributions, and then present a method using a continuous mixture. We show that a continuous mixture of exponentially twisted probabilities and a discrete mixture with a sufficiently large number of components produce asymptotically efficient estimates for all a is an element of A simultaneously.