Strongly Efficient Algorithms for Light-tailed Random Walks: An Old Folk Song Sung to a Faster new Tune… (with P. Glynn and K. Leder)

Summary:

This paper revisits the classical problem of estimating large deviations for empirical means of light-tailed random variables. It might be surprising that one can say anything more on this problem. However, we are able to show that a state-dependent algorithm (closely related to the solution to the Isaacs equation of Dupuis-Wang) is strongly efficient. The title is borrowed from a paper of my former colleague Xiaoli Meng.

Bibtex:

@InProceedings{BlaGlyLed09,

author = {J. Blanchet and P. Glynn and K. Leder},

title = {Strongly efficient algorithms for light-tailed random walks: An old folk song sung to a faster new tune…},

booktitle = {MCQMC 2008},

pages = {227-248},

year = {2008},

editor = {Pierre L’Ecuyer and Art Owen},

OPTaddress = {},

publisher = {Springer},

OPTannote = {}

}