1st International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Strongly efficient estimators for light-tailed sums

  • @INPROCEEDINGS{10.1145/1190095.1190118,
        author={J. Blanchet and P. Glynn},
        title={Strongly efficient estimators for light-tailed sums},
        proceedings={1st International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ACM},
        proceedings_a={VALUETOOLS},
        year={2012},
        month={4},
        keywords={Importance sampling Rare-event Simulation Large Deviations Cramer’s theorem Lyapunov functions Markov chains.},
        doi={10.1145/1190095.1190118}
    }
    
  • J. Blanchet
    P. Glynn
    Year: 2012
    Strongly efficient estimators for light-tailed sums
    VALUETOOLS
    ACM
    DOI: 10.1145/1190095.1190118
J. Blanchet1, P. Glynn1
  • 1: Statistics Department, Harvard University, Management Sc. and Eng., Stanford University.

Abstract

Let (Sn : n ≥ 0) be a mean zero random walk (rw) with light-tailed increments. One of the most fundamental problems in rare-event simulation involves computing P (Sn > nβ) for β > 0 when n is large. It is well known that the optimal exponential tilting (OET), although logarithmically efficient, is not strongly efficient (the squared coefficient of variation of the estimator grows at rate n1/2). Our analysis of the zero-variance change-of-measure provides useful insights into why OET is not strongly efficient. In particular, the iid nature of OET induces an overshoot over the boundary nβ that is too big and causes the coefficient of variation to grow as [EQUATION]. We study techniques used to provide a state-dependent change-of-measure that yields a strongly efficient estimator. The application of our state-dependent algorithm to the Gaussian case reveals the fine structure of the zero-variance change-of-measure. We see how (Sn : n ≥ 0) transitions from a rw under OET to a process that looks "mean reverting" aroung βn, indicating that less bias is required as the process approaches the boundary βn.